Решение задач исследования операций (стр. 2 из 2)

Δ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