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

Задание 1
Решение задач линейного программирования графическим методом
Цель задания: приобрести практические навыки решения задач линейного программирования графическим методом.
Индивидуальное задание
Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).
Таблица 1
Номер варианта Целевая функция Ограничения задачи линейного программирования
6
Решение задачи
Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x 1 +4x 2 =8, 2 x 1 - x 2 =4, x 1 + x 2 ­=1, x 1 =0, x 2 =0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).


Рисунок 1. Графическое решение задачи ЛП
В данной задаче она составляет многоугольник ABCD . Для нахождения экстремума функции Z =-2 x 1 +4 x 2 , строим разрешающую прямую, приравнивая линейную форму нулю:Z =0. Строим градиент целевой функции C(2;4).
Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.
Анализ решения задачи линейного программирования
В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области.

Задание 2
Решение задач ЛП симплексным методом с использованием симплекс-таблиц
Цель задания : закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.
Индивидуальное задание
Найти максимум линейной формы
Z = c 1 x 1 + c 2 x 2
при условиях:
Данные представлены в таблице 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 = -7x1 -4x2
при ограничениях
x3 , x4 , x5 — дополнительные переменные.
Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.
Постановка задачи в виде матрицы системы ограничений
Решение задачи ЛП с составленными симплекс-таблицами
Единичные векторы A 3 , A 4 , A 5 образуют базис трехмерного пространства (m =3 ). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x 3 , x 4 , x 5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x 3 , x 4 , x 5 – базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:
X 0 =(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 0 не является оптимальным решением. Строим новое базисное решение.
.
Выводим из базиса вектор A 3 ,так как
.
Разрешающий элемент таблицы x 12 выделим кругом, а разрешающий столбец и строку стрелками.

Таблица 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 ,так как
.
Таблица 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
Анализ оптимального плана.
Использование переменной x1 нецелесообразно.
Задание 3
Моделирование и решение задач ЛП на ЭВМ
Цель задания: приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.
Индивидуальное задание
Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.
Найти программу максимального выпуска продукции.
Таблица 5.
факторы Способ производства
Ресурсы,
грн
1 2 3 4 5
Сырье 12 15 10 12 11 1300
Эл.энергия 0,2 0,1 0,2 0,25 0,3 30
Зарплата 3 4 5 4 2 400
Накладные расходы 6 5 4 6 4 800
Математическая интерпретация задачи
Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC
5
4
12.000 15.000 10.000 12.000 11.000 < 1300.000
0.200 0.100 0.200 0.250 0.300 < 30.000
3.000 4.000 5.000 4.000 2.000 < 400.000
6.000 5.000 4.000 6.000 4.000 < 800.000
300.000 260.000 320.000 400.000 450.000

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию