Студопедия Главная Случайная страница Обратная связь

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

Двойственные задачи линейного программирования





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

Решение. Обозначим через y1 - двойственную оценку дефицитности трудовых ресурсов, через y2 – ресурсов сырья, y3 - оборудования. Тогда прямая и двойственная задачи формулируются:

прямая задача

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

Решение прямой задачи дает оптимальный план производства продукции П1, П2, П3, П4, а решение двойственной задачи - оптимальную систему оценок ресурсов, используемых для производства этой продукции:

Двойственные оценки ресурсов yi * – это оценочные коэффициенты Dj дополнительных переменных х5, х6, х7 в последней симплексной таблице (таблица 2.9).

Исходя из анализа оптимальных двойственных оценок, можно сделать следующие выводы.

Трудовые ресурсы и оборудование используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки y1, y3, отличные от нуля. Значит, ресурсы сырья недоиспользуются (на х6 =26 ед.).

Увеличение количества трудовых ресурсов на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства продукции, при котором общая прибыль возрастет на 20 д. е. и станет равной 1320 + 20 = 1340 д. е. Анализ полученных оптимальных значений новой прямой задачи показывает, что это увеличение общей прибыли достигается за счет увеличения производства продукции П1 на 1, 67 ед. (5/3) и сокращения выпуска продукции П3 на 0, 67 ед. (2/3) (таблица 2.9). Вследствие этого использование ресурса сырья увеличивается на 7, 33 ед. (22/3).

Точно так же увеличение на 1 ед. количества оборудования позволит перейти к новому оптимальному плану производства, при котором прибыль возрастет на 10 д. е. и составит 1330 д. е., что достигается за счет уменьшения выпуска продукции П1 на 0, 17 ед. и увеличения выпуска продукции П3 на 0, 17 ед., причем объем используемого ресурса сырья уменьшается на 0, 33 ед.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем:

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

2.4. Симплексный метод с искусственным базисом
(М-метод)

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

Домножив неравенство на (-1), получим: .

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

Для нахождения исходного опорного плана переходим к М-задаче:

Дальнейшее решение проводим в симплексных таблицах (таблица 2.10).

Таблица 2.10

ci БП - 10         - M - M bi
x1 x2 x3 x4 x5 z1 z2
- M z1   - 1 - 1          
- M z2       - 1        
  x5 - 1 - 2            
  Dj -3M+10 - 5 M M       - 5M
- 10 х1   -1/2 -1/2         3/2
- M z2   3/2 1/2 -1       1/2
  x5   -5/2 -1/2         5/2
  Dj   -3М/2 -М/2+5 М       -М/2-15
- 10 х1     -1/3 -1/3       5/3
- 5 х2     1/3 -2/3       1/3
  x5       -5/3       10/3
  Dj               -15

В третьей симплекс-таблице получен опорный план исходной задачи ЛП.

Поскольку все оценки , то это решение является и оптимальным, т.е. х1 =5/3, х2 =1/3 (основные переменные), х3 =0, х4 =0, х5 =10/3 (дополнительные переменные), при этом

 







Дата добавления: 2014-11-10; просмотров: 789. Нарушение авторских прав; Мы поможем в написании вашей работы!




Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...


Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Шов первичный, первично отсроченный, вторичный (показания) В зависимости от времени и условий наложения выделяют швы: 1) первичные...

Схема рефлекторной дуги условного слюноотделительного рефлекса При неоднократном сочетании действия предупреждающего сигнала и безусловного пищевого раздражителя формируются...

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Studopedia.info - Студопедия - 2014-2025 год . (0.013 сек.) русская версия | украинская версия