Контрольная работа: Решение задач исследования операций
В итоге получим:
bi | x5 | x3 | |
L | 14 | 5 | 4 |
x2 | 3 | 1 | 1 |
x4 | -5 | -1 | 0 |
x1 | 4 | 2 | 1 |
Коэффициенты при свободных переменных в целевой функции положительны, значит, найденное решение является оптимальным.
Ответ:
x1=4
x2=3
x3=0
x4=-5
x5=0
L=14
2.3 Решение задачи 3
Условие задачи задано в виде транспортной таблицы:
ПН ПО |
B1 | B2 | B3 | запасы |
A1 | 50 | 15 | 10 | 300 |
A2 | 21 | 30 | 20 | 100 |
A3 | 18 | 40 | 25 | 200 |
A4 | 23 | 22 | 12 | 800 |
A5 | 25 | 32 | 45 | 200 |
заявки | 500 | 300 | 800 |
Применим к задаче метод «Северо-Западного угла». Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок:
ПН ПО |
B1 | B2 | B3 | запасы |
A1 | 300 | 300 | ||
A2 | 100 | 100 | ||
A3 | 100 | 100 | 200 | |
A4 | 200 | 600 | 800 | |
A5 | 200 | 200 | ||
заявки | 500 | 300 | 800 |
В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна.
ПН ПО |
B1 | B2 | B3 | запасы |
A1 |
50 300 |
15 | 10 | 300 |
A2 |
21 100 |
30 | 20 | 100 |
A3 |
18 100 |
40 100 |
25 |
200 |
A4 | 23 |
22 200 |
12 600 |
800 |
A5 | 25 | 32 |
45 200 |
200 |
заявки | 500 | 300 | 800 |
В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл γ1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки:
ΔL1=-5*100=-500
Транспортная таблица примет следующий вид:
ПН ПО |
B1 | B2 | B3 | запасы |
A1 |
50 300 |
15 | 10 | 300 |
A2 |
21 100 |
30 | 20 | 100 |
A3 |
18 100 |
40 |
25 100 |
200 |
A4 | 23 |
22 300 |
12 500 |
800 |
A5 | 25 |
32 |
45 200 |
200 |
заявки | 500 | 300 | 800 |
γ2=12+32-45-22=-23 k2=200 ΔL2=-23*200=-4600
ПН ПО |
B1 | B2 | B3 | запасы |
A1 |
50 300 |
15 |
10 |
300 |
A2 |
21 100 |
30 | 20 | 100 |
A3 |
18 100 |
40 |
25 100 |
200 |
A4 | 23 |
22 100 |
12 700 |
800 |
A5 | 25 |
32 200 |
45 | 200 |
заявки | 500 | 300 | 800 |
γ3=10+18-50-25=-47 k3=100 ΔL3=-47*100=-4700
ПН ПО |
B1 | B2 | B3 | запасы |
A1 |
50 200 |
15 |
10 100 |
300 |
A2 |
21 100 |
30 | 20 | 100 |
A3 |
18 200 |
40 | 25 | 200 |
A4 |
23 |
22 100 |
12 700 |
800 |
A5 | 25 |
32 200 |
45 | 200 |
заявки | 500 | 300 | 800 |
γ4=10+23-12-50=-29 k4=200 ΔL4=-29*200=-6800
ПН ПО |
B1 | B2 | B3 | запасы |
A1 | 50 | 15 |
10 300 |
300 |
A2 |
21 100 |
30 | 20 | 100 |
A3 |
18 200 |
40 | 25 | 200 |
A4 |
23 200 |
22 100 |
12 500 |
800 |
A5 | 25 |
32 200 |
45 | 200 |
заявки | 500 | 300 | 800 |
Отрицательных циклов в транспортной таблице больше нет. Следовательно, можно предположить, что найденное решение является оптимальным. Для проверки применим метод потенциалов.
Составим систему:
Положим β2=0, тогда α4=-22
β1=1, α2=-20
β3=-10, α2=-22
α1=-20, α5=-32
Все коэффициенты α отрицательны, значит, найденный план перевозок является оптимальным.
Ответ:
x21=100;
x31=200;
x41=200;
x42=100;
x52=200;
x13=300;
x43=500.
2.4 Решение задачи 4
Составим математическую модель поставленной задачи.
Найти минимум функции f(x1,x2)
При ограничениях
Заменив знак функции f(x1,x2) на противоположный, перейдем к поиску максимума функции:
Теперь задача приведена к стандартному виду задачи квадратичного программирования. Приступим к решению.
1) Определим стационарную точку
Решив систему, получим:
x1=10
x2=7
Очевидно, что данные координаты не удовлетворяют условиям ограничений. Поэтому проверять стационарную точку на относительный максимум нет необходимости.
2) Составим функцию Лагранжа:
Применив к функции Лагранжа теорему Куна-Таккера, будем иметь систему:
3) Преобразуем полученную систему:
Из уравнения 3 системы следует, что x2=6-x1:
Для обращения неравенств системы в равенства введём V1, V2, W и преобразуем систему:
4) Запишем условия дополняющей нежесткости:
5) Введем в систему уравнений искусственные переменные z1,z2:
Поставим задачу максимизации функции .
Для решения этой задачи воспользуемся Симплекс-методом. Примем переменные z1 и z2 в качестве базисных:
Составим Симплекс таблицу:
bi | x1 | U1 | U2 | V1 | V2 | |
φ |
-17M 0 |
-5M 0 |
0 0 |
M 0 |
M 0 |
-M 0 |
z1 |
9 8 |
2 3 |
-1 1 |
2 -3 |
-1 0 |
0 1 |
z2 |
8 8 |
3 3 |
1 1 |
-3 -3 |
0 0 |
1 1 |
W |
0 0 |
-1 0 |
0 0 |
0 0 |
0 0 |
0 0 |
bi | x1 | z2 | U2 | V1 | V2 | |
φ |
-17M 17M |
-5M M |
0 M |
M -M |
M -M |
-M M |
z1 |
17 17/5 |
5 1/5 |
1 1/5 |
-1 -1/5 |
-1 -1/5 |
1 1/5 |
U1 |
8 -51/5 |
3 -3/5 |
1 -3/5 |
-3 3/5 |
0 3/5 |
1 -3/5 |
W |
0 17/5 |
-1 1/5 |
0 1/5 |
0 -1/5 |
0 -1/5 |
0 1/5 |
bi | z1 | z2 | U2 | V1 | V2 | |
φ | 0 | M | M | 0 | 0 | 0 |
x1 | 17/5 | 1/5 | 1/5 | -1/5 | -1/5 | 1/5 |
U1 | -11/5 | -3/5 | -2/5 | 1/2 | 3/5 | -2/5 |
W | 17/5 | 1/5 | 1/5 | -1/5 | -1/5 | 1/5 |
В итоге получим
x1=17/5
x2=6-x1=13/5
Как видно, координаты стационарной точки сильно отличаются от координат, полученных в качестве ответа. Это можно объяснить тем, что стационарная точка не удовлетворяет условиям ограничений.
Условия дополняющей нежесткости
выполняются.
Следовательно, найденное решение является оптимальным.
Найдем значения целевой функции:
=- 51/5 - 52/5 + 289/50 – 221/25 + 169/25 =
= -16.9
Ответ:
x1 = 17/5
x2 = 13/5
f(x1,x2) = -16.9