Решение задач исследования операций
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?тоге получим:
bix5x3L1454x2311x4-5-10x1421
Коэффициенты при свободных переменных в целевой функции положительны, значит, найденное решение является оптимальным.
Ответ:
x1=4
x2=3
x3=0
x4=-5
x5=0
L=14
2.3 Решение задачи 3
Условие задачи задано в виде транспортной таблицы:
ПН
ПОB1B2B3запасыA1501510300A2213020100A3184025200A4232212800A5253245200заявки500300800
Применим к задаче метод Северо-Западного угла. Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок:
ПН
ПОB1B2B3запасыA1300300A2100100A3100100200A4200600800A5200200заявки500300800
В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна.
ПН
ПОB1B2B3запасы A1 50
300 15 10300A2 21
100 30 20100A3 18
100 40
100 25200A4 23
22
200 12
600800A5 25
32 45
200200заявки500300800
В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл ?1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки:
?L1=-5*100=-500
Транспортная таблица примет следующий вид:
ПН
ПОB1B2B3запасы A1 50
300 15 10300A2 21
100 30 20100A3 18
100 40
25
100200A4 23
22
300 12
500800A5 25
32 45
200200заявки500300800
?2=12+32-45-22=-23 k2=200 ?L2=-23*200=-4600
ПН
ПОB1B2B3запасы A1 50
300 15 10300A2 21
100 30 20100A3 18
100 40
25
100200A4 23
22
100 12
700800A5 25
32
200 45
200заявки500300800
?3=10+18-50-25=-47 k3=100 ?L3=-47*100=-4700
ПН
ПОB1B2B3запасы A1 50
200 15 10
100300A2 21
100 30 20100A3 18
200 40
25
200A4 23
22
100 12
700800A5 25
32
200 45
200заявки500300800?4=10+23-12-50=-29 k4=200 ?L4=-29*200=-6800
ПН
ПОB1B2B3запасы A1 50
15 10
300300A2 21
100 30 20100A3 18
200 40
25
200A4 23
200 22
100 12
500800A5 25
32
200 45
200заявки500300800
Отрицательных циклов в транспортной таблице больше нет. Следовательно, можно предположить, что найденное решение является оптимальным. Для проверки применим метод потенциалов.
Составим систему:
Положим ?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 в качестве базисных:
Составим Симплекс таблицу:
bix1U1U2V1V2?-17M
0-5M
00
0 M
0M
0 -M
0z19
82
3-1
1 2
-3-1
00
1z28
8 3
3 1
1-3
-30
01
1W0
0-1
00
00
00
00
0
bix1z2U2V1V2?-17M
17M-5M
M0
M M
-MM
-M-M
Mz117
17/55
1/51
1/5 -1
-1/5 -1
-1/51
1/5 U18
-51/5 3
-3/51
-3/5 -3
3/50
3/5 1
-3/5 W0
17/5-1
1/50
1/50
-1/5 0
-1/50
1/5
biz1z2U2V1V2?0MM000x117/51/51/5-1/5-1/51/5U1-11/5-3/5-2/51/23/5-2/5W17/51/51/5-1/5-1/51/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