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

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

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

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

«МИСиС»

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

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

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

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

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

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

МЭ-13-5

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

Москва 2015 г.

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

Требуется:

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

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

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

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

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

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

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

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

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

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)_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₁

…………………………… …………,,,,,,,,,,,,,……, (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) <#"876957.files/image005.gif">

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

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

х1 + 4х2 ≤ 270

х1 + 4х2 ≤ 108

х1 + 12х2 ≤ 252

хi ≥ 0= 30x1 + 40x2 → max

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

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

у1 + 4у2 + 3у3 ≥ 30

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

у1, у2, у3≥0= 270у1 + 108у2 + 252у3 → min

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

у2 + 3у3= 30

у2 +12 у3=40,= 270*0 + 108*(20/3) + 252*(10/9)=1000

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

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

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

Вывод

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

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

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

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