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

5,5x₁=27 

x₁== 4  

x₂=10-∙===5 

L = 10∙+9∙==102 
 

    2.3. Прямая задача: 

L=10x₁+9x₂→max

10x₁+12x₂ ≤ 120

13x₁+9x₂ ≤ 117

x₁≥0, x₂ ≥0 

    Двойственная  задача: 

L׳ = 120y₁+117y₂→min

    Далее мы составляем матрицу из коэффициентов  при переменных в неравенствах-ограничениях и транспонируем её:

( )         ( ) 

10y₁+13y₂≥10

12y₁+9y₂≥9 
 
 

    2.4. Двойственная задача: 

L׳ = 120y₁+117y₂→min

Выразим y₂ через y_1:

y₂=_=1- y₁ 

y₂=_=1- y₁

y₂=1- y₁ 

Рисунок 2.

 
 
 
 
 
 
 
 

 
 
 
 

               Цел. Ф. 
 
 
 

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

10y₁+13(1- y₁) =10

10y₁+13- y₁=10 

_=-3

22 y₁=9

y₁=

y₂=1-=

 

L`= 120∙+117∙==102 

    2.5. Прямой и двойственный симплекс-методы.

Симплекс-метод для прямой задачи.

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

10x₁+9x₂→max

10x₁+12x₂ ≤ 120

13x₁+9x₂ ≤ 117

x₁≥0, x₂ ≥0 

Приводим  к канонической форме:

10x₁+12x₂ +х₃=120

13x₁+9x₂+х₄=117 

Таблица 19. 

 

    Смотрим на второй столбец, смотрим на соотношения -11700/169 и 9/13. Получаем -69,2 и 0,69 => 9/13 – самое наименьшее соотношение во втором столбце, берём 13 за разрешающий элемент, обозначим его красным цветом.

    Выделяем  столбец и строку, где находится разрешающий элемент. Теперь находим , записываем значение λ в правый нижний угол ячейки с разрешающим элементом.

    Теперь  все элементы разрешающей строки умножаем на λ, а все элементы разрешающего столбца умножаем на λ с противоположным  знаком.

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

    Строим  ещё одну таблицу, в ней мы меняем местами y₂ и x₁; в строке и столбце, которые были разрешающими, в новой таблице мы записываем в левом верхнем углу то, что было в предыдущей таблице в нижнем правом углу; в остальных ячейках мы записываем сумму элементов этих же ячеек в нижнем правом и в верхнем левом углу, эту сумму мы записываем в левый верхний угол.

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

Таблица 20.

 
 
 
 

Таблица 21.

 

  Так как в строке L в ячейках все значения отрицательны, то достигнуто оптимальное решение.

  Проделав  симплекс-метод, сравниваем результаты с графическим решением:

x₁=4 , x₂=5, L = 102, y₁=, y₂= → все данные сходятся, результаты получены правильно. 
 

Симплекс  метод для двойственной задачи. 

L’=120 Y₁+117 Y₂→min

10y₁+13y₂≥10

12y₁+9y₂≥9

y₁,y_2≥0 

Приводим  к канонической форме:

10y₁+13y₂+y₃=10

12y₁+9y₂+y₄=9 

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

Таблица 25.

 
 
 

Таблица 26.