Контрольная работа №2
Задание 1
Решение задач линейного программирования графическим методом
Цель задания: приобрести практические навыки решения задач линейного программирования графическим методом.
Индивидуальное задание
Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).
Таблица 1
Номер варианта Целевая функция Ограничения задачи линейного программирования 6
Решение задачи
Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x1+4x2=8, 2x1-x2=4, x1+x2=1,x1=0,x2=0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).
Рисунок 1. Графическое решение задачи ЛП
В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции Z=-2x1+4x2 , строим разрешающую прямую, приравнивая линейную форму нулю:Z=0. Строим градиент целевой функции C(2;4).
Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.
Анализ решения задачи линейного программирования
В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области.
Задание 2
Решение задач ЛП симплексным методом с использованием симплекс-таблиц
Цель задания: закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.
Индивидуальное задание
Найти максимум линейной формы
Z=c1x1+c2x2
при условиях:
Данные представлены в таблице 2.
Номер варианта
A11
A12
A21
A22
A31
A32
B1
B2
B3
C1
C2
6 4 1 3 6 8 7 43 74 76 7 4
Приведем задачу ЛП к каноническому виду:
-Z’= -Z = -7x1 -4x2
при ограничениях
x3, x4, x5 — дополнительные переменные.
Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.
Постановка задачи в виде матрицы системы ограничений
Решение задачи ЛП с составленными симплекс-таблицами
Единичные векторы A3, A4, A5 образуют базис трехмерного пространства (m=3). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x3, x4, x5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x3, x4, x5 – базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:
X0=(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 76 -8 7 0 0 1 4 0 7 4 0 0 0
Так как среди разностей есть положительные, то X0 не является оптимальным решением. Строим новое базисное решение.
.
Выводим из базиса вектор A3,так как
.
Разрешающий элемент таблицы x12 выделим кругом, а разрешающий столбец и строку стрелками.
Таблица 3. ............
