Задача линейного программирования. Проверка оптимальности текущего плана, страница 23

Заполняем, например, клетки (1, 2) и (1, 3) (табл. 6).

Таблица 5                                                Таблица 6

5) Заполняем клетку (2, 1), где стоит минимальный элемент в оставшейся табл. 6 по формуле: х21 =

6) Закроем первый столбец (где нет остатка).

7) Находим остатки второй строки   = а2 – х21 = 20 – 10 = 10  (табл. 7).

8)Заполняем последнюю свободную клетку(2,2) Х22= (табл. 8).


Таблица 7                                             Таблица 8

9) Проверяем правильность построения первоначального решения.

В табл. 8 m+n-1 = 3+3-1=5 занятых клеток.

10) Первоначальный план методом минимального элемента равен

.                                                                           (8)

11)Вычислим первоначальную стоимость перевозок (см. табл. 8)

Z(X2) = 2·0* + 2·20 + 3·10 + 4·10 + 1·10 = 120.

Поиск оптимального плана. Проверим оптимальность первоначального плана Х1 методом потенциалов следующим образом.

Первый способ

1) Каждой строке из табл. 4 сопоставим переменную Ui, называемую потенциалом поставщика.

2) Каждому столбцу из табл. 4 сопоставим переменную Vj, называемую потенциалом потребителя.

3) Оценкой клетки (i;j) назовем число ∆ij= Ui+ Vjij, (10), где сij – стоимость перевозки, соответствующая данной клетке.

4) Потребуем, чтобы для заполненных клеток оценка равнялась нулю, т.е.

11= U1+V111= U1+V1-9=0 => U1+V1=9, ∆12= U1+V212= U1+V2-2=0 => U1+V2=2,

22= U2+V222= U2+V2-4=0 => U2+V2=4, ∆23= U2+V323= U2+V3-5=0 => U2+V3=5,

33= U3+V333= U3+V3-1=0 => U3+V3=1.

5) Полагаем U1=0, находим V1=9; V2=2; U2=+2; V3=3; U3=-2.

Аналогично можно проверить оптимальность  методом потенциалов.

6) Находим оценки для свободных клеток таблицы 4 и проверим оптимальность текущего плана X1 по значения этих оценках. Если для всех свободных клеток ∆ij≤0, то текущий план оптимален. Если хотя бы одна из оценок положительна (∆ij>0), то план можно улучшить.

13= U1+V313=0+3-2=1>0, ∆21= U2+V121=2+9-3=8>0,∆31= U3+V131=-2+9-8=-1<0,

32= U3+V232=-2+2-7=-7<0. Так как ∆13=1>0, ∆21=8>0, то план X1 не оптимален.

7) Находим свободную клетку в таблице 4 с максимальной положительной оценкой: max {∆13=1, ∆21=8} =8.

8) Для клетки (2,1), которой соответствует наибольшая оценка, ставим знак «+» и строим цикл (закрытый путь), начинающийся и заканчивающийся в этой клетке (см. табл.9).

Примеры некоторых циклов:

Рис. 1

Таблица 9                                         Таблица 10

                  

Следуя этому циклу, расставим чередующиеся знаки + и – в его вершинах, начиная с того знака +, что уже стоит в вершине (2,1).

9) Из объемов перевозок в тех клетках, что отмечены знаком «-», то есть из величин x11=10 и x22=0٭, выбираем меньший объём: θ1= {x11=10, x22=0٭} =0٭.

10) Вычитаем 0٭ в тех клетках, что помечены минусом, а прибавляем 0٭ в тех клетках, что помечены плюсом.

Получаем новый план. Клетка (2,1) стала занятой, а клетка (2,2) – свободной (см. табл. 10).

11) Проверим оптимальность нового плана. Определим оценки свободных клеток, исходя из системы:

11= U1+V111= U1+V1-9=0 => U1+V1=9,  ∆12= U1+V212= U1+V2-2=0 => U1+V2=2,

21= U2+V121= U2+V1-3=0 => U2+V1=3, ∆23= U2+V323= U2+V3-5=0 => U2+V3=5,

33= U3+V333= U3+V3-1=0 => U3+V3=1.

Положим U1=0, находим V1=9; V2=2; U2=-6; V3=11; U3=-10.

Теперь находим оценки свободных клеток.∆13= U1+V313=0+11-2=9>0,

22= U2+V222=-6+2-4=-8<0, ∆31= U3+V131=-10+9-8=-9<0,∆32= U3+V232=-10+2-1=-9<0.

Так как ∆13=9>0, то текущий план не оптимален.

12) Делаем занятой клетку (1,3), отмечая её знаком «+».

13) Находим в таблице 12 цикл: (1,3)→(2,3)→(2,1)→(1,1)→(1,3).

14) Расставляем знаки, начиная с уже поставленного знака«+».

15) Находим минимальный объём перевозки для клеток, отмеченных знаком «-».