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

Контрольная работа

Задание 1

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

Цель задания: приобрести практические навыки решения задач линейного программирования графическим методом.

Индивидуальное задание

Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).

Таблица 1

Решение задачи

Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:

x ₁ +4x ₂ =8, 2 x ₁ - x ₂ =4, x ₁ + x ₂ ­=1, x ₁ =0, x ₂ =0.

Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).

Рисунок 1. Графическое решение задачи ЛП

В данной задаче она составляет многоугольник ABCD . Для нахождения экстремума функции Z =-2 x ₁ +4 x ₂ , строим разрешающую прямую, приравнивая линейную форму нулю:Z =0. Строим градиент целевой функции C(2;4).

Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.

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

В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области.

Задание 2

Решение задач ЛП симплексным методом с использованием симплекс-таблиц

Цель задания : закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.

Индивидуальное задание

Найти максимум линейной формы

Z = c ₁ x ₁ + c ₂ x ₂

при условиях:

Данные представлены в таблице 2.

Приведем задачу ЛП к каноническому виду:

-Z’= -Z = -7x₁ -4x₂

при ограничениях

x₃ , x₄ , x₅ — дополнительные переменные.

Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.

Постановка задачи в виде матрицы системы ограничений

Решение задачи ЛП с составленными симплекс-таблицами

Единичные векторы A ₃ , A ₄ , A ₅ образуют базис трехмерного пространства (m =3 ). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x ₃ , x ₄ , x ₅ входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x ₃ , x ₄ , x ₅ – базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:

X ₀ =(0,0,43,-74,76).

Заполняем исходную симплекс-таблицу (таблица 2)

Таблица 2. Нулевая симплекс-таблица

Так как среди разностей есть положительные, то X ₀ не является оптимальным решением. Строим новое базисное решение.

.

Выводим из базиса вектор A ₃ ,так как

.

Разрешающий элемент таблицы x ₁₂ выделим кругом, а разрешающий столбец и строку стрелками.

Таблица 3. Первая симплекс-таблица

Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.

.

Выводим из базиса вектор A ₄ ,так как

.

Таблица 4. Втораясимплекс-таблица

Так как все разности во второй таблице (таблица 4) неположительны: , т получено оптимальное решение:

min (- Z )= -225.

Тогда max ( Z ) = - min (- Z ) = 225

Анализ оптимального плана.

Использование переменной x₁ нецелесообразно.

Задание 3

Моделирование и решение задач ЛП на ЭВМ

Цель задания: приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.

Индивидуальное задание

Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.

Найти программу максимального выпуска продукции.

Таблица 5.

Математическая интерпретация задачи

Исходные массивы, записанные в виде, пригодном для решения задачи по программе 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 вариант транспортной задачи

Математическая формулировка транспортной задачи

Пусть x_ij – количество единиц работы, выполненной механизмом вида a_i , на участке работы b_j .Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:

при ограничениях:

1) ; - все механизмы должны быть задействованы;

2) ; - все участки должны быть загружены;

3) ; - количество единиц работы не может быть отрицательным

Условие разрешимости задачи выполняется:

25+20+10+5=15+10+35; 60=60.

Исходный опорный план, составленный по методу северо-западного угла

Таблица 7

Решение транспортной задачи методом потенциалов

Итак, видно что в число занятых клеток следует ввести клетку (2,1).

Получим новый улучшенный план – таблица 8.

Таблица 8

Введём в число занятых клетку (1,4) . Получим новый улучшенный план – Таблица 9.

Таблица 9

Так как, - то данный план является оптимальным и значение себестоимости по данному плану.

x ₁₂ =15; x _­21 =5; x ₂₂ =5; x _­31 =20; x ₃₃ =10; x _­34 =5.

Z =15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ оптимального плана

Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы.

Задание 5

Решение транспортной задачи на ЭВМ

Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.

Индивидуальное задание:

Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.

Таблица 10. 06 вариант транспортной задачи

Исходные массивы для решения транспортной задачи по программе TRAN 2

Распечатка с ЭВМ с результатом решения

Оптимальный план транспортной задачи

x ₁₂ =15; x _­21 =5; x ₂₂ =5; x ₃₁ =20; x ₃₃ =10; x _­34 =5.

Z =15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ результатов и выводы

Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.

Задание 6

Решение многоэтапных задач методом динамического программирования

Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.

Индивидуальное задание.

В таблице 11 приведены значения g_i ( x ) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x .

Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f ₄ (100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр.

Таблица 11

Функциональное уравнение Беллмана для рассматриваемой задачи

f ₁ ( x )= max [ g ₁ ( x )]= g ₁ ( x ) – для пер в ого предприятия;

- для остальн ых предприятий.

Решение задачи оптимального распределения средств между предприятиями методом динамического программирования

Таблица 12

Таблица 13

Таблица 14

Таблица 15

Таблица 16