Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Задачи математического программирования.



Задача определения оптимальной производственной программы предприятия. Пусть предприятие выпускает найменований изделий ( ). Для их изготовления используется найменований ресурсов в количестве каждого. Известна норма расхода го ресурса на единицу го изделия - . Задана прибыль от продажи единицы го изделия- . Необходимо составить план производства так, чтобы используя только имеющиеся ресурсы получить максимальную прибыль.

Обозначим через - объем выпуска го изделия. Тогда математическая модель запишется следующим образом:

 

 

Приведем пример:Изделия 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-ая переменная двойственной задачи неотрицательна; ограничениям равенствам отвечает переменная без ограничений в знаке.

 

Пример:Построить задачу, двойственную к данной:

 

Перепишем задачу изменяя ограничения типа на ограничения типа . Получим задачу:

 

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

 

 

ЛЕКЦИЯ 6.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.