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

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

Задание 1

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

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

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

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

Таблица 1

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

Построим область 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.

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

-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. Нулевая симплекс-таблица

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

.

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

.

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

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

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

.

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

.

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

Страницы: 1, 2, 3