Пример решения транспортной задачи



Исходная постановка задачи

В пунктах A и B находятся соответственно 150 и 190 тонн горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 тонн горючего. Стоимость перевозки 1 т горючего из пункта A в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта B в пункты 1, 2, 3 – 120, 20, 80 тыс. руб. за 1 т соответственно.

Составьте план перевозок горючего, минимизирующий общую сумму транспортных расходов.

 

Составим таблицу исходных данных.

 

Поставщики

Потребители

Запасы

1 2 3
A 60 10 40 150
B 120 20 80 190
Потребность 60 70 110  

 

Важно отметить, что данная задача сбалансирована, то есть запасы горючего и потребность в нем равны. В этом случае не нужно учитывать издержки, связанные как со складированием, так и с недопоставками. В противном случае в модель нужно ввести:

· в случае превышения объема запасов - фиктивного потребителя; стоимость перевозок единицы продукции этому фиктивному потребителю полагается равной стоимости складирования, а объемы перевозок этому потребителю равны объемам складирования излишек продукции у поставщиков;

· в случае дефицита - фиктивного поставщика; стоимость перевозок единицы продукции от фиктивного поставщика полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок от этого поставщика равны объемам недопоставок продукции потребителям.

 

Формальная математическая постановка задачи

Константы

1. Обозначим через сij стоимость перевозки единицы продукции от i-того поставщика j-тому потребителю, где i=1,2; j=1,2,3.

 

С =

60 10 40
120 20 80

2. Пусть Zi – запас горючего на i-м пункте, где i=1,2.
Z1=150 тонн, Z2=190 тонн горючего.

3. bj- потребности пунктов 1,2 и 3 в горючем, j=1,2,3, то есть
b1=60 – потребность в горючем пункта 1;
b2=70 – потребность в горючем пункта 2;
b3=110– потребность в горючем пункта 3.

Переменные

1. Пусть xij - объем перевозок от i-того поставщика j-му потребителю.

2.ai - расход горючего для i-го поставщика, где i=1,2.

3. S - cуммарные транспортные расходы
      
      

Решение

1.Зададим математическую модель расхода горючего i-го поставщика

   ,  где i=1,2.

       

2. Математическая модель потребностей в горючем j-х потребителей

          ,  где j=1,2,3.

 

3. Функцией цели являются суммарные транспортные расходы, то есть:

 

Ограничения

Неизвестные должны удовлетворять следующим ограничениям:

1. неотрицательность объема перевозок, то есть xij≥0, (i=1,2; j=1,2,3);

2. в силу сбалансированности задачи, вся продукция должна быть вывезена от поставщиков и потребности всех потребителей должны быть удовлетворены.

Методика выполнения в Microsoft Excel

В табличном процессоре Microsoft Excel для решения подобных задач предусмотрена надстройка Поиск решения. Если в меню Сервис отсутствует команда Поиск решения, для ее установки нужно выбрать команду Сервис > Надстройки, в появившемся диалоговом окне выбрать Поиск решения и нажать кнопку Ok.

Выполните следующую подготовительную работу для решения транспортной задачи с помощью средства Поиск решения в табличном процессоре Microsoft Excel.

1. Введите в ячейки диапазона B4:D5 стоимости перевозок.

2. Отведите ячейки диапазона B8:D9 под значения неизвестных (объемов перевозок). Ячейки должны быть пустыми!

3. Введите в ячейки диапазона F8:F9 объемы запасов горючего у поставщиков.

4. Введите в ячейки диапазона B11:D11 потребность в горючем у потребителей.

5. В ячейку B14 введите функцию цели: =СУММПРОИЗВ(B4:D5;B8:D9). Сделать это можно при помощи мастера функций выбрав в разделе Математические функцию СУММПРОИЗВи указав необходимый диапазон.

6. В ячейки диапазонов E8:E9 введите формулы вычисляющие объемы запасов у поставщиков, в ячейки диапазона B10:D10 – формулы расчета объемов доставляемого топлива к потребителям.

А именно:

 

Ячейка Формула Ячейка Формула
E8 =СУММ(B8:D8) C10 =СУММ(C8:C9)
E9 =СУММ(B9:D9) D10 =СУММ(D8:D9)
B10 =СУММ(B8:B9)    

При этом на экране должно отображаться следующее:

7. Выберите в меню Сервис команду Поиск решения и заполните диалоговое окно Поиск решения, как показано на рисунке.

8. Нажмите кнопку Выполнить. Средство Поиск решения найдет оптимальный план поставок горючего и соответствующие ему транспортные расходы

В результате получаем следующее распределение горючего между поставщиками и потребителями:

 

Поставщики

Потребители

1 2 3
A 60 0 90
B 0 70 20

 

Значение целевой функции составило 10200 денежных единиц.

При этом, экономическая интерпретация результатов будет следующая. Поставщик A перевозит потребителям 1 и 3 - 60 и 90 т горючего соответственно, поставщик В - потребителям 2 и 3 - 70 и 20 т горючего соответственно. При этом затраты на перевозку продукции будут минимальными и составят 10200 денежных единиц.

 

 

Оптимальный раскрой

Цели

В данном разделе показаны возможности использования модели линейного программирования для решения задач раскроя. Эта область приложения модели линейного программирования хорошо изучена. Благодаря работам в области оптимального раскроя основоположника теории линейного программирования лауреата Нобелевской премии академика Л.В. Канторовича задачу оптимального раскроя можно назвать классической прикладной оптимизационной задачей.

Студент должен уметь формулировать и использовать для эконо­мического анализа следующие понятия:

• материал;

• заготовка;

• отходы;

• способ раскроя (рациональный и оптимальный);

• интенсивность использования рациональных способов раскроя.

Модели

Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосредственное использование таких материалов, как правило, невозможно. Предварительно их разделяют на заготовки необходимых размеров. Это можно сделать, используя различные способы раскроя материала.

Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько способов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных способов.

Задачи такого типа возникают в металлургии и машиностроении, лесной, лесообрабатывающей, легкой промышленности.

Выделяют два этапа решения задачи оптимального раскроя.

На первом этапе определяются рациональные способы раскроя материала.

На втором этапе решается задача линейного программирования для определения интенсивности использования рациональных способов раскроя.

 


Дата добавления: 2018-02-15; просмотров: 42;