Методы решения задач транспортного типа

 

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

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

Таблица 12.

 

Q_2min= {5, 19, 24}

Проделываем те же действия до тех пор, пока все  невязки не станут нулевыми.

Таблица 13.

 

Q_3min= {5, 19, 24} 

Таблица 14.

 

Q_4min= {5, 19, 24} 

Таблица 15.

 

Q_5min= {5, 5} 

Таблица 16.

 

Q_6min= {5, 5} 

Таблица 17.

 

Заносим стоимости в исходную таблицу.

Таблица 18.

 

W_вен. = 17∙11+14∙1+21∙2+19∙26+5∙21+2∙3+17∙4 = 916 

Вывод: решив задачу транспортного типа пятью методами, можно сделать вывод, что оптимальным методом по стоимости является - метод минимального элемента (W=916), следующий за ним -  метод потенциалов (W=1052), самый не выгодный - метод северо-западного угла (W=1098). 
 
 
 
 
 
 
 
 
 
 
 
 

Задание № 2

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

  2.1. Привести математическую постановку задачи линейного программирования (ЛП).

  2.2. Дать графическую интерпретацию задачи ЛП и решить ее графическим способом.

  2.3. Записать задачу ЛП в двойственной формулировке.

  2.4. Привести графическую интерпретацию двойственной задачи ЛП. Найти графический способ решения двойственной задачи ЛП.

  2.5. Решить задачу ЛП с помощью прямого и двойственного симплекс-методов. Сравнить полученные решения с графическими решениями.

  2.6. Привести математическую постановку задачи линейного целочисленного программирования (ЛП).

  2.7. Дать графическую интерпретацию задачи ЛЦП. Выделить множество допустимых точек. Решить графическим способом задачи ЛЦП.

  2.8. Найти решение задачи ЛПЦ с помощью алгоритма Гомори. Сравнить полученное решение с графическим решением.

  2.9. Найти решение задачи ЛПЦ с помощью алгоритма ветвей и границ. 

    2.1. Математическая постановка: требуется найти максимум или минимум линейной функции n-переменных L=L(x₁, x₂, … ,x_n) = при ограничениях следующего вида:

     , где  ,

     , где  ,

     , где  , . 

    2.2. Графический метод. 

Исходные  данные:

10x₁+9x₂→max

10x₁+12x₂ ≤ 120

13x₁+9x₂ ≤ 117

x₁≥0, x₂ ≥0 

10x₁= -9x₂

    Выразим x₂ через x₁: 

x₂ = _=10- x₁ 

x₂ = _=13- x₁ 

Рисунок 1. 

                                                                  10 
 
 

                                                                                                           A

                                          Цел. Ф.           5                                      

 
 
 

                                                                                                  5                                 10

                                                                                   
 
 
 
 
 
 

Подставим х₂: 

13x₁+9(10- x₁) = 117

13x₁+90-15/2x₁ = 117