4 Алгоритм решения задачи
4.1 Вводятся А,В,С
4.2 Заполняется симплексная таблица
4.3 Вычисляется базис
4.4 Находится опорный план и Z0
4.5 Проверяется условие в (m+1)- строки Zj-Cj<=0 на min
4.6 Если условие выполняется, то выполняется переход на пункт 4.10
4.7 Выбирается вектор Pk по max(Zj-Cj)=Zk-Ck>0
4.8 Выбирается вектор Pl, подлежащий исключению из базиса для которого: для всех xik>0
4.9 Таблица преобразуется продолжением полного исключения и переход на пункт 4.4
4.10 Печать Xopt и Zopt
5 Вычислительная схема
Находится первоначальный опорный план методом двойного предпочтения.
Таблица 4
10 0 |
16 0 |
3 14 |
8 0 |
15 0 |
14 |
3 0 |
14 0 |
12 0 |
9 0 |
1 25 |
25 |
2 40 |
20 16 |
4 0 |
11 0 |
5 0 |
56 |
7 0 |
17 24 |
13 6 |
8 10 |
15 5 |
45 |
40 |
40 |
20 |
10 |
30 |
140 |
.
Решение данной задачи осуществляется методом потенциалов.
Таблица 5
Шаг 1 |
|||||||
Строки |
Ui |
Столбцы |
ai |
||||
1 |
2 |
3 |
4 |
5 |
|||
Vj |
|||||||
3 |
7 |
-2 |
5 |
-11 |
|||
1 |
0 |
10 0 |
16 0 |
3 14 |
8 0 |
15 0 |
14 |
2 |
10 |
3 0 |
14 0 |
12 0 |
9 0 |
1 25 |
25 |
3 |
13 |
2 40 |
20 11 |
4 0 |
11 0 |
5 5 |
56 |
4 |
-4 |
7 0 |
17 29 |
13 6 |
8 10 |
15 0 |
45 |
bj |
40 |
40 |
20 |
10 |
30 |
140 |
|
.
Таблица 6
Шаг 2 |
|||||||
Строки |
Ui |
Столбцы |
ai |
||||
1 |
2 |
3 |
4 |
5 |
|||
Vj |
|||||||
-11 |
7 |
3 |
-2 |
-8 |
|||
1 |
0 |
10 0 |
16 0 |
3 14 |
8 0 |
15 0 |
14 |
2 |
9 |
3 0 |
14 0 |
12 0 |
9 0 |
1 25 |
25 |
3 |
13 |
2 40 |
20 5 |
4 6 |
11 0 |
5 5 |
56 |
4 |
10 |
7 0 |
17 35 |
13 0 |
8 10 |
15 0 |
45 |
bj |
40 |
40 |
20 |
10 |
30 |
140 |
|
.
Таблица 7
Шаг 3 |
|||||||
Строки |
Ui |
Столбцы |
ai |
||||
1 |
2 |
3 |
4 |
5 |
|||
Vj |
|||||||
1 |
19 |
3 |
10 |
4 |
|||
1 |
0 |
10 0 |
16 5 |
3 9 |
8 0 |
15 0 |
14 |
2 |
-3 |
3 0 |
14 0 |
12 0 |
9 0 |
1 25 |
25 |
3 |
1 |
2 40 |
20 0 |
4 11 |
11 0 |
5 5 |
56 |
4 |
-2 |
7 0 |
17 35 |
13 0 |
8 10 |
15 0 |
45 |
bj |
40 |
40 |
20 |
10 |
30 |
140 |
|
Так как
,
то получается оптимальный план на
третьем шаге.
.