Решение задач линейного программирования различными методами (стр. 1 из 3)
Контрольная работа
Задание 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. Первая симплекс-таблица
| i | Бx | Cб | A0 | -7 | -4 | 0 | 0 | 0 | T |
| A1 | A2 | A3 | A4 | A5 |  | ||||
 1 | A1 | -7 |  | 1 |   | | 0 | 0 | |
| 2 | A4 | 0 |  | 0 |  |  | 1 | 0 | |
| 3 | A5 | 0 | 162 | 0 | 9 | 2 | 0 | 1 | |
| 4 |  | 0 |  |  | 0 | 0 |
Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.
.Выводим из базиса вектор A4,так как
.Таблица 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 | A4 | 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.