Математическая постановка транспортной задачи линейного программирования и решение её различными методами

     Если  минимальная стоимость одинакова  для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

Пример 

     Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

(Здесь  мы перенесли потребности в  верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента

Решение:

Опорный план имеет вид:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.5. Метод потенциалов

     Метод потенциалов является модификацией симплекс-метода решения задачи линейного  программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

 

vj[k] –  ui[k]  Cij, i  1, ..., m; j 1, …, п.

 

     Если  разность предварительных потенциалов  для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается  способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

 
 
 
 
 
 
 
 
 
 
 
 

Приложение

Задача 1.

   Решить  следующую задачу на минимизацию  транспортных затрат предприятия с  использованием надстройки «Поиск решения» электронной таблицы Excel.

   Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции из i-го пункта производства в j-ый центр потребления Cij приведена в таблице, где под строкой понимается пункт производства, а под столбцом -пункт потребления. Кроме того, в таблицах в i-й строке указан объем производства в i-м пункте, а в j-м столбце указан спрос в j-м центре потребления. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задачи взять из представленной ниже таблицы.                                                                                                                                  Таблица1

I. Математическая модель задачи.

   1) Переменные задачи. Обозначим количество продукции, которые будут перевозиться из n пунктов производства в m пункты потребления как X_ij (i=1,2,3,4,5,6; j=1,2,3,4,5). Это переменные задачи, значения которых должны быть определены в процессе решения.

   В задаче содержится 6*5=30 переменных.

   2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные, т.е.

                        X_ij 0,

                        где i=1, 2, 3,4,5,; j=1, 2, 3, 4.

 

   Обычно  транспортная задача представляется в  виде таблицы, где в ячейках помещаются переменные задачи ( X_ij ), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j ( C_ij ). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи .

   Транспортная  задача, для которой суммы чисел  в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.

   Для нашего примера транспортная задача не сбалансирована. Сумма чисел в  последнем столбце равна: 14+30+20+32+16=112, а нижней строке равна: 60+10+20+10=100. Чтобы  сбалансировать задачу  вводим пятый столбец и добавляем туда 12. Таблица в этом случае имеет вид:

 
 
 
 
 
 

   3) Целевая функция. Транспортные расходы на перевозку по доставке требуемой продукции вычисляются по формуле:

   Z = C_ijX_ij = 7,3X₁₁ + 9X₁₂ + 3X₁₃ + ... +5X₅₄  (1)

   II. Решение транспортной задачи в процедуре EXCEL “Поиск решения”

   1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL.

   В ячейках B4 : E7 введены стоимости перевозок (табл. 1).

В  ячейках  G4: G8 находится объемы производства. А в ячейках B9: F12 находится объемы потребления. Ячейки B11 : F15 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи X_ij.

   В ячейках G11 : G15 нужно записать формулы для вычисления левых частей ограничений:

   в G11 должна быть сумма ячеек B11 : F11;

   в G12 должна быть сумма ячеек B12 : F12;

   в G13 должна быть сумма ячеек B13 : F13;

   в G14 должна быть сумма ячеек B14 : F14;

   в G15 должна быть сумма ячеек B15 : F15.  .

     Формулы для вычисления левых частей ограничений  введем в ячейки B16 : F16:

   в C16 должна быть сумма ячеек C11 : C15;

   в D16 должна быть сумма ячеек D11: D15;

   в E16 должна быть сумма ячеек E11: E15;

   в F16 должна быть сумма ячеек F11 : F15;

   Целевую функцию поместим в ячейку H9:

   H9: СУММПРОИЗВ (B4 : F8; B12: F16).

   Таблица исходных данных имеет вид :

   2) Заполнение окна процедуры «Поиск решения».

         целевая функция  H9;

         значение целевой  функции : min;

         изменяемые ячейки : B12:F16;

         ограничения задачи :

               G12:G16=G4:G8

               B12:F16 = B4:F8

               B12 : F16 0 (1)

 

       3) Выполнив процедуру «Поиск решения» получим следующие результаты: