Лабораторные работы по Основам теории систем

Лабораторная работа № 2

Телешовой Елизаветы, гр. 726,

Цель работы: Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования.

1 вариант.

1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы ВлЧайфВ», захватив пиво 2 сортов: ВлРусичВ» и ВлПремьерВ». Определить план распития напитков для получения максимального суммарного опьянения (в ). Исходные данные даны в таблице:

Студент	Норма выпитого		Запасы (в литрах)
	ВлРусичВ»	ВлПремьерВ»
Иванов	2	2	1.5
Петров	3,5	1	1,5
Сидоров	10	4	4,5
Васильев	тАУ	1	0,7
Крепость напитка	16 %	10 %

2. Математическая модель.

2.1 Управляемые параметры

x₁[л] тАУ количество выпитого пива ВлРусичВ».

x₂[л] тАУ количество выпитого пива ВлПремьерВ».

тАУ решение.

2.2 Ограничения

тАУ количество пива ВлРусичВ», выпитого Ивановым.

тАУ количество пива ВлПремьерВ», выпитого Ивановым.

тАУ общее количество пива, выпитого Ивановым.

Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:

(л).

Аналогично строим другие ограничения:

(л).

(л).

(л).

3. Постановка задачи.

Найти ^*, где достигается максимальное значение функции цели:

4. Решение.

при:

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

Определим начальный опорный план: .

Это решение является опорным, т.к. вектора условий при положительных компонентах решения линейно независимы, также , где , но не все оценки положительны (, где )

Опорный план является оптимальным, если для задачи максимизации все его оценки неотрицательны. не является оптимальным, значит критерий можно улучшить, если увеличить одну их отрицательных свободных переменных. Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели.

Предположим, что , тогда:

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

=>

При увеличении , первой перестает выполнять условие неотрицательности переменная , т.к. она первая обращается в ноль. Значит выведем из базиса . Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новые переменные.

Из ограничения (2) имеем: .

Подставляя в функцию цели: получаем:

Оформим данный этап задачи в виде симплекс-таблицы:

Начальная симплекс-таблица:

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X3	2	2	1	0	0	0	1,5
0	X4	3,5	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

;

Пересчитаем элементы исходной таблицы по правилу четырехугольника:

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,428	1	-0,572	0	0	0,642
16	X1	1	0,286	0	0,286	0	0	0,428
0	X5	0	1,14	0	-2,86	1	0	0,214
0	X6	0	1	0	0	0	1	0,7
	F	0	-5,424	0	4,576	0	0	6,857

;

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (2) и (3): . Тогда: ;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	0	1	3	-1,25	0	0,375
16	X1	1	0	0	1	-0,25	0	0,375
10	X2	0	1	0	-2,5	0,875	0	0,1875
0	X6	0	0	0	2,5	-0,875	1	0,5125
	F	0	0	0	-9	4,75	0	7,875

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (1) и (2): . Тогда: ;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X4	0	0	0,333	1	-0,416	0	0,125
16	X1	1	0	-0,333	0	0,166	0	0,25
10	X2	0	1	1,833	0	-0,166	0	0,5
0	X6	0	0	-0,833	0	0,166	1	0,2
	F	0	0	3	0	1	0	9

Видим, что все оценки положительны, значит любое увеличение какой-либо свободной переменной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:

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

2 вариант.

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

Функция цели: .

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

=>

Решаем симплекс-методом:

		16	6,4	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	2	2	1	0	0	0	1,5
0	X4	3,5	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

,

		16	6,4	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,428	1	-0,571	0	0	0,642
16	X1	1	1,286	0	0,286	0	0	0,428
0	X5	0	1,142	0	-2,85	1	0	0,214
0	X6	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	0	1	3	-1,25	0	0,375
16	X1	1	0	0	1	-0,25	0	0,375
6,4	X2	0	1	0	-2,5	0,875	0	0,1875
0	X6	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X4	0	0	0,333	1	-0,416	0	0,125
16	X1	1	0	-0,333	0	0,166	0	0,25
10	X2	0	1	1,833	0	-0,166	0	0,5
0	X6	0	0	-0,833	0	0,166	1	0,2
	F	0	0	0	0	1	0	7,2

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

;

;

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

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

3 вариант.

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

Функция цели:.

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

=>

Решим задачу симплекс-методом.

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X3	2	2	1	0	0	0	1,5
0	X4	4	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

, .

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,5	1	-0,5	0	0	0,75
16	X1	1	0,25	0	0,25	0	0	0,375
0	X5	0	1,5	0	-2,5	1	0	0,75
0	X6	0	1	0	0	0	1	0,7
	F	0	-6	0	4	0	0	6

, .

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
10	X2	0	1	1,666	-0,333	0	0	0,5
16	X1	1	0	-0,166	0,333	0	0	0,25
0	X5	0	0	-1	-2	1	0	0
0	X6	0	0	-0,666	0,333	0	1	0,2
	F	0	0	4	2	0	0	9

,

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

В случае вырожденного решения симплекс-таблица может зацикливаться. Существует 2 способа предупреждения зацикливания:

а) тАУ изменение хода ограничения на некоторые величины . Они должны быть малы, чтобы изменения были несущественны.

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

4 вариант.

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

Функция цели: .

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

=>

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

, при этом .

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

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	2	2	-1	0	0	0	1	0	0	0	1,5
1	X8	3.5	1	0	-1	0	0	0	1	0	0	1,5
1	X9	10	4	0	0	-1	0	0	0	1	0	4,5
1	X10	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	0	1,428	-1	0,571	0	0	1	-0,571	0	0	0,642
0	X1	1	0,285	0	-0,285	0	0	0	0,285	0	0	0,428
1	X9	0	1,142	0	2,857	-1	0	0	-2,85	1	0	0,214
1	X10	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	0	0	-1	-3	1,25	0	1	3	-1,25	0	0,375
0	X1	1	0	0	-1	0,25	0	0	1	-0,25	0	0,375
0	X2	0	1	0	2,5	-0,875	0	0	-2,5	0,875	0	0,187
1	X10	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X8	0	0	-0,333	-1	0,416	0	0,333	1	-0,416	0	0,125
0	X1	1	0	0,333	0	-0,166	0	-,333	0	0,166	0	0,25
0	X2	0	1	-0,833	0	0,166	0	0,833	0	-0,166	0	0,5
1	X10	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X8	0	0	0	-1	0,35	-0,4	0	1	-0,35	0,4	0,205
0	X1	1	0	0	0	-0,1	0,4	0	0	0,1	-0,4	0,17
0	X2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X3	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
0	X5	0	0	0	-2,85	1	-1,14	0	2,857	-1	-1,142	0,585
0	X1	1	0	0	-0,285	0	0,285	0	0,285	0	-0,285	0,228
0	X2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X3	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
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X5	0	0	0	-2,85	1	-1,14	0,585
16	X1	1	0	0	-0,285	0	0,285	0,228
10	X2	0	1	0	0	0	-1	0,7
0	X3	0	0	1	-0,571	0	-1,42	0,357
	F	0	0	0	-4,576	0	-5,424	3,648

Критерий можно улучшить, т.к. , , но нельзя найти такое , при котором базисные переменные обращаются в 0. Значит задача неразрешима из-за неограниченности критерия.

5 вариант.

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

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

=>

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

;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X5	0	0	0	-2,85	1	-1,14	0,585
16	X1	1	0	0	-0,285	0	0,285	0,228
10	X2	0	1	0	0	0	-1	0,7
0	X3	0	0	1	-0,571	0	-1,42	0,357
	F	0	0	0	-4,576	0	-5,424	3,648

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

; F = 3,648.

Делаем вывод: оптимальное решение может существовать и при неограниченности области.

Область не ограничена, но существует оптимальное решение , причем единственное, которое достигается в угловой точке.

11

Вместе с этим смотрят:

"Инкарнация" кватернионов

* Алгебры и их применение

*-Алгебры и их применение

10 способов решения квадратных уравнений

Cпособы преобразования комплексного чертежа, применение при изображении предметов