Контрольная работа: Исследование операций
Количество заполненных ячеек 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. Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
2. Составить функцию Лагранжа.
3. Получить систему неравенств в соответствии с теоремой Куна-Таккера.
4. Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
5. Дать ответ с учетом условий дополняющей нежесткости.
| № | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 |
Знаки огр. 1 2 |
|
| 59 | 4.5 | 1.5 | –5 | –2 | –1 | max | 2 | –3 | 5 | 4 | 9 | 13 | ³ | ³ |
Решение:
Целевая функция: F=-5x12-x22-2x1x2+4.5x1+1.5x2
Ограничения g1(x) и g2(x): 
→
1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):
→ 
→ 
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции
F11 (х10, х20) = -10 < 0
F12 (х10, х20) = -2
F21 (х10, х20) = -2
F22 (х10, х20) = -2
Т.к. условие выполняется, то целевая функция является строго вогнутой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F(x)+u1g1(x)+u2g2(x)=
=-5x12-x22-2x1x2+4.5x1+1.5x2+u1(2x1-3x2-9)+u2(5x1+4x2-13)
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
i=1;2
Объединим неравенства в систему А, а равенства в систему В:
