Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Данное решение является оптимальным.

Изобразим это решение на графике:

(2)

(4)

(1)

(3)

X ( оп)

X ( 2)

X ( 3)

X (4 )

Видим, что

единственное и достигается в угловой точке области допустимых решений. 2 вариант.

Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива «Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в Функция цели: Приводим ограничения к каноническому виду: = > Решаем симплекс-методом:

	16	6,4	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	В
0	X 3	2	2	1	0	0	0	1,5
0	X 4	3,5	1	0	1	0	0	1,5
0	X 5	10	4	0	0	1	0	4,5
0	X 6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

	16	6,4	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	В
0	X 3	0	1,428	1	-0,571	0	0	0,642
16	X 1	1	1,286	0	0,286	0	0	0,428
0	X 5	0	1,142	0	-2,85	1	0	0,214
0	X 6	0	1	0	0	0	1	0,7
	F	0	-1,82	0	4,571	0	0	6,857

	16	6,4	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	В
0	X 3	0	0	1	3	-1,25	0	0,375
16	X 1	1	0	0	1	-0,25	0	0,375
6,4	X 2	0	1	0	-2,5	0,875	0	0,1875
0	X 6	0	0	0	2,5	-0,875	1	0,5125
	F	0	0	0	0	1,6	0	7,2

Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных (

	16	10	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	в
0	X 4	0	0	0,333	1	-0,416	0	0,125
16	X 1	1	0	-0,333	0	0,166	0	0,25
10	X 2	0	1	1,833	0	-0,166	0	0,5
0	X 6	0	0	-0,833	0	0,166	1	0,2
	F	0	0	0	0	1	0	7,2

Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле:

;

(2)

F,(3)

(4)

(1)

X ( оп)

X ( 2)

X ( 3)

X (4 )

На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным.

Вектор градиента целевой функции ( F) параллелен радиус-вектору ограничения ( 3 ). Это ограничение образует все множество оптимальных решений. Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных переменных равна 0. 3 вариант.

Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.

Функция цели: Приводим ограничения к каноническому виду: = > Решим задачу симплекс-методом.

	16	10	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	в
0	X 3	2	2	1	0	0	0	1,5
0	X 4	4	1	0	1	0	0	1,5
0	X 5	10	4	0	0	1	0	4,5
0	X 6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

	16	10	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	В
0	X 3	0	1,5	1	-0,5	0	0	0,75
16	X 1	1	0,25	0	0,25	0	0	0,375
0	X 5	0	1,5	0	-2,5	1	0	0,75
0	X 6	0	1	0	0	0	1	0,7
	F	0	-6	0	4	0	0	6

	16	10	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	в
10	X 2	0	1	1,666	-0,333	0	0	0,5
16	X 1	1	0	-0,166	0,333	0	0	0,25
0	X 5	0	0	-1	-2	1	0	0
0	X 6	0	0	-0,666	0,333	0	1	0,2
	F	0	0	4	2	0	0	9

Данное оптимальное решение является вырожденным, т.к. положительных компонентов меньше числа ограничений. На существование вырожденного оптимального решения указывает наличие в симплекс-таблице нулевого свободного члена при найденном оптимальном решении. В случае вырожденного решения симплекс-таблица может зацикливаться.

Существует 2 способа предупреждения зацикливания: а) – изменение хода ограничения на некоторые величины б) Если минимальное отношение свободных коэффициентов к положительным членам разрешающего столбца определяется неоднозначно, то выбирается отношение любого другого столбца к положительным коэффициентам данного столбца, пока строка не определится однозначно.

(1)

(4)

(2)

(3)

X (оп )

X ( 1)

X ( 2)

4 вариант. В связи с неожиданно полученной стипендией, запасы пива резко увеличились.

Функция цели: Приводим ограничения к каноническому виду: = > В матрице условий нет единичной подматрицы, поэтому используем метод искусственного базиса.

Построим вспомогательную задачу. Решаем вспомогательную задачу симплекс-методом:

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
1	X 7	2	2	-1	0	0	0	1	0	0	0	1,5
1	X 8	3.5	1	0	-1	0	0	0	1	0	0	1,5
1	X 9	10	4	0	0	-1	0	0	0	1	0	4,5
1	X 10	0	1	0	0	0	-1	0	0	0	1	0,7
	F	15,5	8	-1	-1	-1	-1	0	0	0	0	0

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
1	X 7	0	1,428	-1	0,571	0	0	1	-0,571	0	0	0,642
0	X 1	1	0,285	0	-0,285	0	0	0	0,285	0	0	0,428
1	X 9	0	1,142	0	2,857	-1	0	0	-2,85	1	0	0,214
1	X 10	0	1	0	0	0	-1	0	0	0	1	0,7
	F	0	3.571	-1	3,428	-1	-1	0	-4,42	0	0	1,557

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
1	X 7	0	0	-1	-3	1,25	0	1	3	-1,25	0	0,375
0	X 1	1	0	0	-1	0,25	0	0	1	-0,25	0	0,375
0	X 2	0	1	0	2,5	-0,875	0	0	-2,5	0,875	0	0,187
1	X 10	0	0	0	-2,5	0,875	-1	0	2,5	-0,875	1	0,512
	F	0	0	-1	-5,5	2,125	-1	0	4,5	-3,12	0	0,887

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
1	X 8	0	0	-0,333	-1	0,416	0	0,333	1	-0,416	0	0,125
0	X 1	1	0	0,333	0	-0,166	0	-,333	0	0,166	0	0,25
0	X 2	0	1	-0,833	0	0,166	0	0,833	0	-0,166	0	0,5
1	X 10	0	0	0,833	0	-0,166	-1	-0,833	0	0,166	1	0,2
	F	0	0	0,5	-1	0,25	-1	-1,5	0	-1,25	0	0,325

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
1	X 8	0	0	0	-1	0,35	-0,4	0	1	-0,35	0,4	0,205
0	X 1	1	0	0	0	-0,1	0,4	0	0	0,1	-0,4	0,17
0	X 2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X 3	0	0	1	0	-0,2	-1,2	-1	0	0,2	1,2	0,24
	F	0	0	0	-1	0,35	-0,4	-1	0	-1,35	-0,6	0,205

	0	0	0	0	0	0	1	1	1	1
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	в
0	X 5	0	0	0	-2,85	1	-1,14	0	2,857	-1	-1,142	0,585
0	X 1	1	0	0	-0,285	0	0,285	0	0,285	0	-0,285	0,228
0	X 2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X 3	0	0	1	-0,571	0	-1,42	-1	-1,571	0	1,428	0,357
	F	0	0	0	0	0	0	-1	-1	-1	-1	0

оптимальное решение вспомогательной задачи.

Искусственные переменные являются свободными и равны нулю. Т.о. это решение является опорным планом исходной задачи. Решим исходную задачу:

	16	10	0	0	0	0
С в	Б.П.	X 1	X 2	X 3	X 4	X 5	X 6	в
0	X 5	0	0	0	-2,85	1	-1,14	0,585
16	X 1	1	0	0	-0,285	0	0,285	0,228
10	X 2	0	1	0	0	0	-1	0,7
0	X 3	0	0	1	-0,571	0	-1,42	0,357
	F	0	0	0	-4,576	0	-5,424	3,648

(1)

(4)

(2)

(3)

X (оп )

5 вариант. После отмеченного таким образом праздника обязательно наступает похмелье. Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор, т.е. функция цели:

Приводим ограничения к каноническому виду:

= >

Эта задача решается методом искусственного базиса, т.к. в ней нет единичной подматрицы.

Категории

Разное