Линейное и динамическое программирование
Категория реферата: Рефераты по математике
Теги реферата: шпоры по гражданскому, рефераты
Добавил(а) на сайт: Dudin.
Предыдущая страница реферата | 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 | Следующая страница реферата