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

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

На предприятии ОАО «Электросигнал» имеется 4 транзитных склада А_i , на которых хранятся сборочные узлы и 5 цехов B_j , занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из А_i в B_j . Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.

Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки

В данном случае Σa_i =225 >Σb_j =220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B₆ с потребностью b₅ =225-220=5 и стоимостью перевозок с_{i 6} =0.Имеем таблицу 3. :

Таблица 3. -

Математическая модель: обозначим x_ij – количество товара, перевозимого из А_i в B_j . Тогда

x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆

x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₂₆

X = x₃₁ x₃₂ x₃₃ x₃₄ x₃₅ x₃₆ - матрица перевозок.

x₄₁ x₄₂ x₄₃ x₄₄ x₄₅ x₄₆

min(x₁₁ +2x₁₂ +3x₁₃ +2,5x₁₄ +3,5x₁₅ +0,4x₂₁ +3x₂₂ +x₂₃ +2x₂₄ +3x₂₅ +0,7x₃₁ +x₃₂ +x₃₃ +0,8x₃₄ +1,5x₃₅ ++1,2x₄₁ +2x₄₂ +2x₄₃ +1,5x₄₄ +2,5x₄₅ ) (3. )

x₁₁ +x₁₂ +x₁₃ +x₁₄ +x₁₅ +x₁₆ =50

x₂₁ +x₂₂ +x₂₃ +x₂₄ +x₂₅ +x₂₆ =20

x₃₁ +x₃₂ +x₃₃ +x₃₄ +x₃₅ +x₃₆ =75

x₄₁ +x₄₂ +x₄₃ +x₄₄ +x₄₅ +x₄₆ =80

x₁₂ +x₂₂ +x₃₂ +x₄₂ =50

x₁₃ +x₂₃ +x₃₃ +x₄₃ =15

x₁₄ +x₂₄ +x₃₄ +x₄₄ =75

x₁₅ +x₂₅ +x₃₅ +x₄₅ =40

x₁₆ +x₂₆ +x₃₆ +x₄₆ =5

x_ij ≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3. )

ДвойственнаяЗЛП:

max(50u₁ +20u₂ +75u₃ +80u₄ +40v₁ +50v₂ +15v₃ +75v₄ +40v₅ +5v₆ ) (3. )

u₁ +v₁ ≤1

u₁ +v₂ ≤2

u₁ +v₃ ≤3 (3. )

u₁ +v₄ ≤2,5

u₁ +v₅ ≤3,5

u₁ +v₆ ≤0

u_i ,v_j – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )

Будем искать первоначальный план по методу наименьшей стоимости:

1) x₂₁ =20и 2-ую строку исключаем;

2) x₃₁ =20и 1-ый столбец исключаем;

3) x₃₄ =55и 3-ю строку исключаем;

4) x₄₄ =20и 4-ый столбец исключаем;

5) x₁₂ =50 и 1-ю строку и 2-ой столбец исключаем и x₃₂ =0;

6) x₄₃ =150 и 3-ий столбец исключаем;

7) x₄₅ =40 и 5-ый столбец исключаем и x₄₆ =5.

Составим таблицу 3. . Здесь и далее в нижнем правом углу записываем значение перевозки.

Таблица 3. – Проведение итераций

Стоимость 1-ого плана:

D₁ =2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Будем улучшать этот план методом потенциалов: u_i - потенциал А_i ,v_j - потенциал B_j . Тогда u₁ +v₂ =2,u₂ +v₁ =0,4, u₃ +v₁ =0,7, u₃ +v₂ =1, u₃ +v₄ =0,8, u₄ +v₃ =2, u₄ +v₄ =1,5, u₄ +v₅ =2,5 ,u₄ +v₆ =0.Положим u₁ =0,тогда v₂ =2,u₃ =-1,v₁ =1,7,v₄ =1,8, u₂ =-1,3,u₄ =-0,3, v₃ =2,3,v₅ =2,8,v₆ =0,3.Составим таблицу 3. :

Таблица 3. - Проведение итераций

В верхнем левом углу здесь и далее записываем значение u_i +v_j -c_ij . Имеем: u₁ +v₁ --c₁₁ =0,7>0, u₁ +v₆ -c₁₆ =0,3>0, u₃ +v₃ -c₃₃ =0,3>0, u₃ +v₅ -c₃₅ =0,3>0,

u₄ +v₁ -c₄₁ =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А₁ В₁ ,сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u₁ +v₁ =1,u₁ +v₂ =2,u₂ +v₁ =0,4,u₃ +v₂ =1, u₃ +v₄ =0,8, u₄ +v₃ =2, u₄ +v₄ =1,5, u₄ +v₅ =2,5 , u₄ +v₆ =0. Положим u₁ =0,тогда v₁ =1,u₂ =-0,6,v₂ =2,v₄ =1,8, u₃ =-1, u₄ =-0,3,v₃ =2,3,v₅ =2,8,v₆ =0,3. Составим таблицу 3. :

Таблица 3. - Проведение итераций

Стоимость 2-ого плана:

D₂ =1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.

Имеем:u₁ +v₆ -c₁₆ =0,3>0, u₂ +v₃ -c₂₃ =0,7>0, u₃ +v₃ -c₃₃ =0,3>0, u₃ +v₅ -c₃₅ =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А₂ В₃ ,сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u₁ +v₁ =1,u₁ +v₂ =2,u₂ +v₁ =0,4,u₃ +v₂ =1, u₃ +v₄ =0,8, u₂ +v₃ =1, u₄ +v₄ =1,5, u₄ +v₅ =2,5 , u₄ +v₆ =0. Положим u₁ =0,тогда v₁ =1,u₂ =-0,6,v₂ =2,v₄ =1,8, u₃ =-1, u₄ =-0,3,v₃ =1,6, v₅ =2,8, v₆ =0,3. Составим таблицу 3.:

Таблица 3. - Проведение итераций

Стоимость 3-его плана:

D₃ =1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.

Имеем:u₁ +v₆ -c₁₆ =0,3>0,u₃ +v₅ -c₃₅ =0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А₃ В₅ ,сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А₄ В₅ нулевую перевозку. Найдем потенциалы: u₁ +v₁ =1,u₁ +v₂ =2,u₂ +v₁ =0,4,u₃ +v₂ =1, u₄ +v₅ =2,5, u₂ +v₃ =1, u₄ +v₄ =1,5, u₃ +v₅ =1,5 , u₄ +v₆ =0. Положим u₁ =0,тогда v₁ =1,u₂ =-0,6,v₂ =2,v₄ =1,5, u₃ =-1,u₄ =0, v₃ =1,6, v₅ =2,5, v₆ =0. Составим таблицу 3. :

Таблица 3. - Проведение итераций

Стоимость 4-ого плана:

D₄ =1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.

Для всех клеток последней таблицы выполнены условия оптимальности:

1) u_i +v_j -с_ij =0 для клеток, занятых перевозками;

2) u_i +v_j -с_ij ≤0 для свободных клеток.

Несодержательные ответы:

Прямой ЗЛП:

35 15 0 0 0 0

5 0 15 0 0 0

X = 0 35 0 0 40 0

0 0 0 75 0 5

min=289,5.

Двойственной ЗЛП:

U₁ =0 ; U₂ =-0,6 ; U₃ =-1 ; U₄ =0 ; V₁ =1 ; V₂ =2 ; V₃ =1,6 ; V₄ =1,5 ; V₅ =2,5 ; V₆ =0.

max=289,5.

Так как min=max, то по критерию оптимальности найдены оптимальные решения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозить так:

Из А₁ вB₁ – 35 сборочных агрегатов;

Из А₁ вB₂ – 15 сборочных агрегатов;

Из А₂ вB₁ – 5 сборочных агрегатов;

Из А₂ вB₃ – 15 сборочных агрегатов;

Из А₃ вB₂ – 35 сборочных агрегатов;

Из А₃ вB₅ – 40 сборочных агрегатов;

Из А₄ вB₄ – 75 сборочных агрегатов.

При этом стоимость минимальна и составит D_min =289,5. 5 сборочных агрегатов необходимо оставить на складе А₄ для их последующей перевозки в другие Цеха.

Список использованной литературы

1. Е.Г. Гольштейн, Д.Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 2007.

2. И.Л. Акулич, В.Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2006.

3. Астафуров В.Г., Колодникова Н. - Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощью двойственной задачи”, Томск-2004.

4. Алесинская Т.В. - Задачи по исследованию операций с решениями. Москва, 2008.

5. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие. Воронеж, 2009