Оптимизация плана выпуска продукции методом линейного программирования

Министерство образования и науки РФ

ФГАОУ Национальный исследовательский технологический университет

«МИСиС»

Институт экономики и управления промышленными предприятиями

Кафедра Бизнес-информатики и систем управления предприятиями

МАТЕМАТИЧЕСКИЕ МЕТОДЫ МОДЕЛИРОВАНИЯ, ОПТИМИЗАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ

ПРАКТИЧЕСКАЯ РАБОТА

ОПТИМИЗАЦИЯ ПЛАНА ВЫПУСКА ПРОДУКЦИИ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Выполнил студент группы:

МЭ-13-5

Ким Дмитрий Игоревич

Москва 2015 г.

Дана задача: Менеджеру производственной фирмы требуется составить оптимальный по прибыли план выпуска запчастей двух видов, используя для этого ресурсы трех типов. Их запасы ограничены значениями в₁, в₂, в₃ соответственно. Пусть а₁₁, а₁₂ количество ресурсов первого типа, расходуемых на запчасти каждого вида, соответственно. Аналогичный смысл имеют символы а₂₁, а₂₂ и а₃₁, а₃₂. Ожидаемая прибыль от реализации одной запчасти каждого вида составляет с₁, с₂ условных единиц, соответственно.

Требуется:

а) записать условия задачи в таблицу стандартной формы;

б) решить задачу табличным симплекс- методом

в) решить задачу в среде EXCEL

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

Исходные данные:

в₁ = 300 - 5V, в₂ = 120-2V, в₃ = 252, с₁= 30, с₂ = 40, а₁₁= 12, а₁₂= 4,

а₂₁ = 4, а₂₂ = 4 , а₃₁ =3, а₃₂= 12

Краткое описание метода

Линейное программирование (ЛП), изучает методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:

целевая функция:

F = c₁х₁ + c₂х₂+……c_nх_n > max (min) (2.1)

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

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n {? = ?} b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n {? = ?} b₂,

………………………………. (2.2)

a_m1x₁ + a_m2x₂ + ... + a_mnx_n {? = ?} b_m;

требование неотрицательности:

x_i ? 0, i = 1,n (2.3)

При этом a_ij, b_i, c_j ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным. Матричная запись задачи ЛП имеет вид:

Ах {? = ?} в

х ? 0

F = c x > max (min)

Здесь А - матрица коэффициентов, х - столбец переменных,

в- столбец правых частей, с - строка коэффициентов целевой функции.

С каждой задачей линейного программирования тесно связана другая задача линейного программирования - двойственная задача (их так и называют - пара двойственных задач):

Прямая задача Двойственная задача

а₁₁х₁ + а₁₂х₂+……а_1nх_n ? в₁ а₁₁у₁ + а₂₁у₂+……а_m1y_m ? c₁

а₂₁х₁ + а₂₂х₂+……а_2nх_n ? в₂ а₁₂y₁ + а₂₂y₂+……а_m2y_m ? c₂

…………………………… …………,,,,,,,,,,,,,……, (2.4)

а_m1х₁ + а_m2х₂+……а_mnх_n ? в_m а_1ny₁ + а_2ny₂+……а_mny_n ? c_n

x_i ? 0, i = 1,n y_i ? 0, i = 1,m

F = c₁х₁ + c₂х₂+……c_nх_n > max G = b₁y₁ + b₂y₂+……b_m> min

Как было сказано выше, вектор х, удовлетворяющий ограничениям задачи, называют планом и совокупность таких векторов - множеством планов. План называется опорным , если он обращает в равенство хотя бы n независимых ограничений (2.2)-(2.3) (в вершине пересекаются хотя бы n граничных гиперплоскостей). Понятие опорного плана в задаче ЛП является очень важным поскольку как следует из теории оптимальный план всегда является опорным. На этом свойстве основан основной метод решения задачи ЛП - симплексный метод. Суть его состоит в упорядоченном переборе опорных планов. Алгоритм сводится к следующему:

· выбирается первоначальное опорное решение;

· выбранный план проверяется на оптимальность;

· если план не оптимален, осуществляется переход к лучшему плану;

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

Алгоритм симплекс-метода реализован в среде Microsoft Excel, меню Сервис-Поиск решения. В соответствующих ячейках задаются коэффициенты целевой функции, ограничений и указывается, какая задача решается (max или min).

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

Симплекс метод

Начинаем с построения математической модели:

Пусть х1, х2 количество изделий каждого вида, соответственно.

12х1 + 4х2 ? 270

4х1 + 4х2 ? 108

3х1 + 12х2 ? 252

х1, х2 ? 0

F = 30x1 + 40x2 > max

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

12х1 + 4х2+х3 =270

4х1 + 4х2+х4 = 108

3х1 + 12х2+х5=252

х1, х2,х3 ? 0

F = 30x1 + 40x2 > max

Составляем исходную симплекс-таблицу.

Таблица 1.

Х1=(0,0,270,108,252)-решение не оптимально.

Таблица 2

Х2=(0,21,186,24,0)-решение вновь не оптимально.

Таблица 3

Получили итоговую таблицу. Х3=(8,19,98,0,0) F_max=1000.

Итак, Х3 оптимальное решение. Следуя ему, нужно выпускать 8 единиц 1-го изделия и 19 единиц 2-го. Ожидаемая максимальная прибыль 1000 у.е.

EXCEL:

Двойственная задача:

Построение математической модели:

12х1 + 4х2 ? 270

4х1 + 4х2 ? 108

3х1 + 12х2 ? 252

хi ? 0

F = 30x1 + 40x2 > max

Решение исходной оптимизационной задачи X_опт=(8,19).

Составление двойственной задачи:

12у1 + 4у2 + 3у3 ? 30

4у1 + 4у2 +12 у3 ? 40

у1, у2, у3?0

G = 270у1 + 108у2 + 252у3 > min

Одна из двойственных задач решена табличным симплекс методом, то оптимальное решение симметричной двойственной задачи легко находится по последней симплекс - таблице, достаточно найти абсолютные значения балансовых переменных. Так, оптимальное решение двойственной задачи (0, 20/3, 10/9).

4у2 + 3у3= 30

4у2 +12 у3=40,

G = 270*0 + 108*(20/3) + 252*(10/9)=1000

Уопт = (0, 20/3, 10/9)

у1 = 0 означает не дефицитность первого ресурса, у2 =20/3, у3 =10/9 - дефицитность последних двух ресурсов.

у2?у3, дополнительные средства выгоднее вложить в закупку сырья 2. При этом, увеличение запаса этого сырья на 5 ед. приведет к увеличению максимальной прибыли на 33 у.е.

план симплекс прибыль математический

Вывод

- Записаны условия задачи в таблицу стандартной формы.

- Задача решена табличным симплекс-методом.

- Задача решена в среде EXCEL.

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