48793 (Решение задач линейного программирования)
Описание файла
Документ из архива "Решение задач линейного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48793"
Текст из документа "48793"
Контрольная работа №2
Задание 1
Решение задач линейного программирования графическим методом
Цель задания: приобрести практические навыки решения задач линейного программирования графическим методом.
Индивидуальное задание
Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).
Таблица 1
| Номер варианта | Целевая функция | Ограничения задачи линейного программирования |
| 6 | | |
Решение задачи
Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x1+4x2=8, 2x1-x2=4, x1+x2=1,x1=0,x2=0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).
L
Рисунок 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.
Найти программу максимального выпуска продукции.
Таблица 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
1
Рисунок 2. Исходные массивы для решения задачи
