Индивидуальное задание

Контрольная работа

Задание 1

Решение задач линейного программирования графическим методом

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

Индивидуальное задание

Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).

Таблица 1

Номер варианта	Целевая функция	Ограничения задачи линейного программирования
6

Решение задачи

Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:

x₁+4x ₂ =8, 2 x ₁ - x ₂ =4, x ₁ + x ₂ ­=1, x ₁ =0, x ₂ =0.

Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).

 

Рисунок 1. Графическое решение задачи ЛП

 

В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции Z =-2 x ₁ +4 x ₂ , строим разрешающую прямую, приравнивая линейную форму нулю:Z =0. Строим градиент целевой функции C(2;4).

Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.

Анализ решения задачи линейного программирования

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

Задание 2

Решение задач ЛП симплексным методом с использованием симплекс-таблиц

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

Индивидуальное задание

Найти максимум линейной формы

Z = c ₁ x ₁ + c ₂ x ₂

при условиях:

Данные представлены в таблице 2.

Номер варианта	A11	A12	A21	A22	A31	A32	B1	B2	B3	C1	C 2
6	4	1	3	6	8	7	43	74	76	7	4

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

-Z’= -Z = -7x₁ -4x₂

при ограничениях

 

x₃, x₄, x₅ — дополнительные переменные.

Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.

Постановка задачи в виде матрицы системы ограничений

Решение задачи ЛП с составленными симплекс-таблицами

Единичные векторы A ₃ , A ₄ , A ₅ образуют базис трехмерного пространства (m =3). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x ₃ , x ₄ , x ₅ входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x ₃ , x ₄ , x ₅ – базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:

X ₀ =(0,0,43,-74,76).

Заполняем исходную симплекс-таблицу (таблица 2)

Таблица 2. Нулевая симплекс-таблица

i	Б x	Сб	A0	- 7	-4	0	0	0	T
				A1	A2	A3	A4	A5
1	A3	0	43	4	1	1	0	0
2	A4	0	74	-3	-6	0	1	0
3	A5	0	7 6	-8	7	0	0	1
4			0	7	4	0	0	0

 

Так как среди разностей есть положительные, то X ₀ не является оптимальным решением. Строим новое базисное решение.

.

Выводим из базиса вектор A ₃,так как

.

Разрешающий элемент таблицы x ₁₂ выделим кругом, а разрешающий столбец и строку стрелками.

Таблица 3. Первая симплекс-таблица

i	Б x	C б	A0	-7	-4	0	0	0	T
				A1	A2	A3	A4	A5
1	A 1	-7		1			0	0
2	A4	0		0			1	0
3	A5	0	162	0	9	2	0	1
4				0			0	0

Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.

.

Выводим из базиса вектор A ₄,так как

.

 

Таблица 4. Вторая симплекс-таблица

i	Б x	C б	A0	-7	- 4	0	0	0	T
				A1	A2	A3	A4	A5
1	A2	- 4	43	4	1	4	0	0
2	A 4	0	736	21	0		1	0
3	A5	0	-225	-36	0	-34	0	1
4				-9	0		0	0

 

Так как все разности во второй таблице (таблица 4) неположительны: , т получено оптимальное решение:

min (- Z )= -225.

Тогда max ( Z )= - min (- Z )= 225

Анализ оптимального плана.

Использование переменной x₁ нецелесообразно.

 

Задание 3