Решение задач линейного программирования
Контрольная работа №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 | |||||
|
|
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 |
1
Так как среди разностей есть положительные, то X0 не является оптимальным решением. Строим новое базисное решение.
.
Выводим из базиса вектор A3,так как
.
Разрешающий элемент таблицы x12 выделим кругом, а разрешающий столбец и строку стрелками.
Таблица 3. Первая симплекс-таблица
| i | Бx | Cб | A0 | -7 | -4 | 0 | 0 | 0 | T |
| A1 | A2 | A3 | A4 | A5 |
|
||||
|
|
A1 | -7 |
|
1 |
|
|
0 | 0 | |
| 2 | A4 | 0 |
|
0 |
|
|
1 | 0 | |
| 3 | A5 | 0 | 162 | 0 | 9 | 2 | 0 | 1 | |
| 4 |
|
0 |
|
|
0 | 0 |
1
Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.
.
Выводим из базиса вектор 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. Исходные массивы для решения задачи
Распечатка ЭВМ с результатом решения
ИТЕРАЦИЯ N=1 РЕШЕНИЕ НАЙДЕНО !!!
ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 5
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 300.000 260.000 320.000 400.000 450.000
КОД ОШИБКИ=0
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 0.0000
ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 5
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 -300.000 -260.000 -320.000 -400.000 -450.000
В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ
ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ
ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 7
6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667
5 450.000 100.000 0.667 0.333 0.667 0.833 3.333
8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667
9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333
45000.000 -0.000 -110.000 -20.000 -25.000 1500.000
В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ
ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ
ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 3 4 6 7
2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235
5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412
8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118
9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471
46941.176 45.294 5.882 2.500 9.706 1144.118
КОД ОШИБКИ=0
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
X2=17.6471
X5=94.1176
ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765
РЕШЕНИЕ НАЙДЕНО !!!
Оптимальный план. Экономическая интерпретация оптимального решения.
В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен.
Задание 4
Моделирование транспортных задач и их решение методом потенциалов
Цель задания: приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.
Индивидуальное задание
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 6. 06 вариант транспортной задачи
| Вид механизма | Себестоимость выполнения единицы работы механизма ,гр. | Количество единиц ai механизмов | |||
| B1 | B2 | B3 | B4 | ||
| A1 | 11 | 4 | 3 | 1 | 15 |
| A2 | 6 | 8 | 9 | 7 | 10 |
| A3 | 4 | 8 | 4 | 2 | 35 |
| Потребности bj участков в механизмах | 25 | 20 | 10 | 5 | |
Математическая формулировка транспортной задачи
Пусть xij – количество единиц работы, выполненной механизмом вида ai, на участке работы bj.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:
при ограничениях:
1)
;
- все механизмы
должны быть
задействованы;
2)
;
- все участки
должны быть
загружены;
3)
;
- количество
единиц работы
не может быть
отрицательным
Условие разрешимости задачи выполняется:
25+20+10+5=15+10+35; 60=60.
Исходный опорный план, составленный по методу северо-западного угла
Таблица 7
| I | ai | ||||
| B1 | B2 | B3 | B4 | ||
| A1 | 11 |
4 15 |
3 | 1 | 15 |
| A2 |
6 5 |
8 5 |
9 |
7 |
10 |
| A3 |
4 20 |
8 |
4 10 |
2 5 |
35 |
| bj | 25 | 20 | 10 | 5 | |
Решение транспортной задачи методом потенциалов
Итак, видно что в число занятых клеток следует ввести клетку (2,1).
Получим новый улучшенный план – таблица 8.
Таблица 8
| I | ai | ||||
| B1 | B2 | B3 | B4 | ||
| A1 |
11 |
4 15 |
3 |
1 |
15 |
| A2 |
6 5 |
8 5 |
9 |
7 |
10 |
| A3 |
4 20 |
8 |
4 10 |
5 5 |
35 |
| bj | 25 | 20 | 10 | 5 | |
Введём в число занятых клетку (1,4) . Получим новый улучшенный план – Таблица 9.
Таблица 9
| I | ai | ||||
| B1 | B2 | B3 | B4 | ||
| A1 |
11 |
4 10 |
3 5 |
1 |
15 |
| A2 |
6 |
8 10 |
9 |
7 |
10 |
| A3 |
4 25 |
8 |
4 5 |
2 5 |
35 |
| bj | 25 | 20 | 10 | 5 | |
Так как,
- то данный план
является оптимальным
и значение
себестоимости
по данному
плану.
x12=15; x21=5; x22=5; x31=20;x33=10; x34=5.
Z=15*4+5*6+5*8+20*4+10*4+5*2=260.
Анализ оптимального плана
Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы.
Задание 5
Решение транспортной задачи на ЭВМ
Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.
Индивидуальное задание:
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 10. 06 вариант транспортной задачи
| Вид механизма |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |