Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

(21=0, p2+q1-c21=0, p2+3-2=0, p2= -1

(23=0, p2+q3-c23=0, -1+q3-1=0, q3=2 аналогично, получим: q2=4, р3=-1, q4=5, q5=1.

Затем вычисляем оценки всех свободных клеток:

(12=p1+q2-c12=0+4-6= -2

(13=p1+q3-c13=0+2-4=-2

(14=2; (15=1; (24=1; (25=0; (31= -4; (32= -2

Находим наибольшую положительную оценку: mах((ij >0)=2=(14,

Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-
23-21-11. Производим перераспределение поставок вдоль цикла пересчета:

|40 | | |* | |40-( | | |( | |33 | | |7 |
|8 |30 |7 | |( |8+( | |7-( | |( |15 |30 | | |
| | |22 |40 | | | |22+( |40-( | | | |29 |33 |

(max=7

Получаем второе базисное допустимое решение:

Таблица 2

| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | |
|Потребл | | | | | | |
|Произв | | | | | | |
|a1=40 |33 |6 | |7 | |p1=0 |
| |3 | |4 |3 |0 | |
|a2=45 |15 |30 |1 | | |p2=-1 |
| |2 |3 | |3 |0 | |
|a3=70 | |* |29 |33 |8 0|p3=1 |
| |6 |5 |1 |4 | | |
| |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |

Находим новые потенциалы. Новые оценки:

(12= -2; (13= -4; (15= -1; (23= -2; (24= -1; (25= -2; (31= -2; (32=0.
Поскольку все (ij(0 решение является оптимальным:

33 0 0 7

Xоpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки (32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:

Таблица 3

| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | |
|Потребл | | | | | | |
|Произв | | | | | | |
|a1=40 |3 3|6 | |37 | |p1=0 |
| | | |4 |3 |0 | |
|a2=45 |45 |3 |1 | | |p2=-1 |
| |2 | | |3 |0 | |
|a3=70 | |30 |29 |3 4|8 0|p3=1 |
| |6 |5 |1 | | | |
| |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |

Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого (max=(32, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

Xоpt2 = 45 0 0 0

0 30 29 3

Рекомендуем скачать другие рефераты по теме: шпаргалки по гражданскому, організація реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата