Решение задач линейного программирования различными методами Контрольная работа Задание 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 Распечатка ЭВМ в результатом решения ИТЕРАЦИЯ 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 механизмов B 1 B 2 B 3 B 4 A 1 11 4 3 1 15 A 2 6 8 9 7 10 A 3 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 3 5 bj 25 20 1 0 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 3 5 bj 25 20 1 0 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 3 5 bj 25 20 1 0 5 Так как, - то данный план является оптимальным и значение себестоимости по данному плану. x 12 =15; x ­21 =5; x 22 =5; x ­31 =20; x 33 =10; x ­34 =5. Z =15*4+5*6+5*8+20*4+10*4+5*2=260. Анализ оптимального плана Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы. Задание 5 Решение транспортной задачи на ЭВМ Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2. Индивидуальное задание: Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6. Таблица 10. 06 вариант транспортной задачи Вид механизма Себестоимость выполнения единицы работы механизма ,гр. Количество единиц ai механизмов B1 B2 B3 B4 A1 11 4 3 1 15 A2 6 8 9 7 10 A 3 4 8 4 2 35 Потребности bj участков в механизмах 25 20 10 5 Исходные массивы для решения транспортной задачи по программе TRAN 2 Распечатка с ЭВМ с результатом решения Оптимальный план транспортной задачи x 12 =15; x ­21 =5; x 22 =5; x 31 =20; x 33 =10; x ­34 =5. Z =15*4+5*6+5*8+20*4+10*4+5*2=260. Анализ результатов и выводы Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении. Задание 6 Решение многоэтапных задач методом динамического программирования Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования. Индивидуальное задание. В таблице 11 приведены значения gi ( x ) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x . Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f 4 (100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр. Таблица 11 Предприятие Прирост выпуска продукции, тыс. гр. Средства c , тыс. гр. Номер варианта 20 40 60 80 100 1 G1 (x) 11 21 40 54 62 6 2 G2 (x) 13 20 42 45 61 3 G3 (x) 12 22 34 55 60 4 G 4 ( x ) 10 27 33 57 69 Функциональное уравнение Беллмана для рассматриваемой задачи f 1 ( x )= max [ g 1 ( x )]= g 1 ( x ) – для пер в ого предприятия; - для остальн ых предприятий. Решение задачи оптимального распределения средств между предприятиями методом динамического программирования Таблица 12 Средства с, тыс. гр. Предприятие 1 2 3 4 G1 (x) G2 (x) G3 (x) G 4 ( x ) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57 100 62 62 60 69 Таблица 13 X1 * (c) 20 40 60 80 100 F1 (c) 11 21 40 54 62 Таблица 14 x С 0 20 40 60 80 100 F2 (c) X2 * (c) 20 0+13 12+0 13 0 40