Контрольная работа: Исследование операций 4
4. Проверить решение задачи методом потенциалов.
| №вар. | а1 | а2 | а3 | b1 | b2 | b3 | b4 | b5 | с11 | с12 | с13 |
| 14 | 90 | 50 | 30 | 15 | 45 | 45 | 50 | 15 | 45 | 60 | 40 |
| с14 | с15 | с21 | с22 | с23 | с24 | с25 | с31 | с32 | с33 | с34 | с35 |
| 60 | 95 | 35 | 30 | 55 | 30 | 40 | 50 | 40 | 35 | 30 | 100 |
Решение:
Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:
| B1 | B2 | B3 | B4 | B5 | a | ||||||
| A1 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 45 | 30 | |||||||||
| A2 | 35 | 30 | 55 | 30 | 40 | 50 | |||||
| 15 | 35 | ||||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 15 | 15 | ||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Это будет опорный план.
Количество заполненных ячеек r=m+n-1=6.
1) Рассмотрим цикл (1,2)-(1,3)-(2,3)-(3,2):
с1,2+с2,3>c1.3+c3.2 (60+55>30+40)
Количество единиц товара, перемещаемых по циклу: min (с1,2 ; с2,3)=15
2) Рассмотрим цикл (2,4)-(2,5)-(3,5)-(3,4):
c2,4+с3,5>c2.5+c3.4 (30+40>30+100)
Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15
В результате получится следующий план:
| B1 | B2 | B3 | B4 | B5 | a | ||||||
| A1 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 30 | 45 | |||||||||
| A2 | 35 | 30 | 55 | 30 | 40 | 50 | |||||
| 15 | 20 | 15 | |||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 30 | |||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
| β1=45 | β2=60 | β3=40 | β4=60 | β5=70 | ||||||
| α1=0 | 45 | 60 | 40 | 60 | 95 | 90 | ||||
| 15 | 30 | 45 | 0 | + | ||||||
| α2= -30 | 35 | 30 | 55 | 30 | 40 | 50 | ||||
| + | 15 | + | 20 | 15 | ||||||
| α3= -30 | 50 | 40 | 35 | 30 | 100 | 30 | ||||
| + | + | + | 30 | + | ||||||
| 15 | 45 | 45 | 50 | 15 | 170 | |||||
Δ1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.
Таким образом, решение верное, т.к. Δij ≥0.
ОТВЕТ:
| B1 | B2 | B3 | B4 | B5 | a | ||||||
| A1 | 45 | 60 | 40 | 60 | 95 | 90 | |||||
| 15 | 30 | 45 | |||||||||
| A2 | 35 | 30 | 55 | 30 | 40 | 50 | |||||
| 15 | 20 | 15 | |||||||||
| A3 | 50 | 40 | 35 | 30 | 100 | 30 | |||||
| 30 | |||||||||||
| b | 15 | 45 | 45 | 50 | 15 | 170 | |||||
Задача 4
№59
Условие:
Определить экстремум целевой функции вида
F = c11x12+c22x22+c12x1x2+b1x1+b2x2
при условиях
a11x1+a12x2<=>p1
a21x1+a22x2<=>p2 .
1. Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.