Задача определения оптимальной производственной программы предприятия. Пусть предприятие выпускает найменований изделий ( ). Для их изготовления используется найменований ресурсов в количестве каждого. Известна норма расхода го ресурса на единицу го изделия - . Задана прибыль от продажи единицы го изделия- . Необходимо составить план производства так, чтобы используя только имеющиеся ресурсы получить максимальную прибыль.
Обозначим через - объем выпуска го изделия. Тогда математическая модель запишется следующим образом:
Приведем пример:Изделия N1 и N2 изготовляются на фрезерных станках. Для их изготовления есть 100 кг металла. Затрата металла на изготовление одного изделия N1 составляет 2 кг, а на N2-4кг. Трудоемкость изготовления 100 и 120 станкогодин соответственно для изделий N1 и N2. Мощность фрезерных станков 2000 станкогодин на период, который рассматривается. Составить план производства, которое обеспечивает получение наибольшей выручки от продажи изделий, если отпускная цена одного изделия N1 установлена 3 грн, а изделию N2-2 грн, причем , причем изделий N1 нужно изготовить не больше 40 штук, а изделий N2-не больше 20 штук.
Построим модель данной задачи: Обозначим через х1- объем выпуска изделия №1, а через х2 –объем выпуска изделия №2. Тогда модель имеет вид:
Задача распределения изделий по видам взаимозаменяемого оборудования:
Пусть предприятие выпускает найменований изделий . В объеме ( ) каждого. Для их изготовления используется видов взаимозаменяемого оборудования. Известен фонд полезного времени для каждого типа оборудования . Трудоемкость и себестоимость изготовления изделия зависит от типа оборудования . не обходимо выполнить план предприятия с минимальной суммарной себестоимостью.
Обозначим через - объем выпуска -го изделия на ом оборудовании.
Тогда модель задачи имеет вид:
Приведем пример:
/
25/8
12/4
16/5
23/8
14/7
23/8
15/7
17/6
-
16/6
19/8
17/6
13/4
14/5
24/8
14/5
-
15/5
10/3
13/6
12/4
25/8
16/7
10/4
24/8
12/6
-
19/6
16/8
13/5
bj
Обозначим через - объем выпуска -го изделия на -ом типе оборудования. Тогда модель имеет вид:
( ; )
Решив эту задачу получим следующее решение.
остальные
Проанализируем решение:
1) Распределение изделий по видам оборудования:
На 1-ом типе оборудования изготавливаются изделия 2- го типа в объеме 180 ед и изделия 5 типа в объеме 160 ед.( )
На 2 –ом типе оборудования изделия не изготавливаются.
На 3-ем типе оборудования изготавливаются изделия 4- го типа в объеме 170 ед ( )
На 4-ом типе оборудования изготавливаются изделия 1- го типа в объеме 240 ед, изделия 3 типа в объеме 260 ед., изделия 6-го типа в объеме 60 ед.( ).
На 5-ом типе оборудования изготавливаются изделия 6- го типа в объеме 140 ед ( ).
2) Коэффициент загрузки оборудования, вычисляется по формуле:
3) Оптимальный парк оборудования, вычисляется по формуле:
; ; ; ;
4) Оптимальная себестоимость. Вычисляется как значение целевой функции.
Двойственность в ЛП.
Каждой задаче ЛП с любым типом ограничений можно поставить в соответствие другую задачу, которая называется двойственной по отношению к первой. Совместное рассмотрение таких пар задач позволяет исследовать влияние изменения переменных системы на значение целевой функции, проводить экономический анализ результатов расчета.
Правила построения двойственной задачи:
1. Если прямая задача была задачей максимума, то двойственная будет задачей минимума, и на оборот;
2. Число переменных двойственной задачи равно числу ограничений прямой, и наоборот;
3. Коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;
4. Свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;
5. Матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой, и наоборот;
6. Взаимно однозначное соответствие между переменными исходной задачи и ограничениями двойственной удовлетворяет следующему положению:
А) если J-ая переменная неотрицательна в прямой задаче, то J-ое ограничение в двойственной задаче это неравенство типа ; переменным не имеющих ограничений в знаке соответствует ограничение равенство;
Б) если I-ое ограничение прямой задачи неравенство типа , то
I-ая переменная двойственной задачи неотрицательна; ограничениям равенствам отвечает переменная без ограничений в знаке.
Пример:Построить задачу, двойственную к данной:
Перепишем задачу изменяя ограничения типа на ограничения типа . Получим задачу: