Здавалка
Главная | Обратная связь

Двойственные задачи

Отчет

по лабораторной работе №4

по дисциплине « Математическое программирование»

Руководитель работы

____________Раменская А.В.

«___»_______________2012 г .

Исполнитель

Студент группы 10 Нэк

_________________Зозуля О.В,

«___»_______________2012г.

 

 

Оренбург 2012


Двойственные задачи

 

Для производства четырех видов изделий (А, В, С) предприятие использует три вида сырья: металл, пластмассу, резину. Запасы сырья, технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) представлены в таблице 2 (варианты 1…20). В ней же указана прибыль от реализации одного изделия каждого вида. Требуется составить такой план выпуска указанных изделий, чтобы обеспечить максимальную прибыль.

 

Сырье Технологические коэффициенты Запасы
А В С Д
Металл
Пластмасса
Резина
Прибыль(руб)  

 

Решение:

Обозначим:

x1 – план выпуска изделия вида А;

x2 – план выпуска изделия вида В;

x4 – план выпуска изделия вида С;

x3 – план выпуска изделия вида Д;

Составим экономико-математическую модель задачи оптимального использования ресурсов на максимум прибыли.

Прямая задача имеет вид:

 

 

Найдем оценку из каждого вида сырья, используемого при каждом виде продукции. Оценки, приписываемые каждому из видов сырья должны быть такими, чтобы суммарная оценка всего используемого сырья была бы минимальной, а суммарные оценки сырья, используемые для производства одной единицы продукции каждого вида были не менее прибыли, полученной от ее реализации.

Обозначим:

y1 – теневая цена сырья «Металл»;

y2 – теневая цена сырья «Пластмасса»;

y3 – теневая цена сырья «Резина».

Тогда экономико-математическая модель двойственной задачи будет иметь вид:

 

 

В результате получим симметричную пару двойственных задач.

Решим прямую задачу. Для этого запишем ее в канонической общей форме:

 

 

Последняя оптимальная симплекс-таблица имеет вид:

 

Продолжение таблицы:

 

 

Таким образом, оптимальное решение прямой задачи имеет вид: x*=(0,0,450,0,400,0,1080), при этом значение целевой функции составит: f*=2250 ед.

 

Способ.

Найдем решение двойственной задачи с использованием второй теоремы двойственности. Согласно первому условию имеем:

 

 

Первая скобка не равна нулю, из чего следует что: =0.

Вторая скобка равна нулю, из чего следует что: - любое.

Третья скобка не равна нулю, из чего следует что: =0.

 

Далее, согласно второму условию имеем:

 

 

Поскольку , то . Решая его, находим .

Таким образом, получили: , у1* =0 и =0.

Аналогичные результаты получены с использованием программы:

 

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

Условие первой теоремы двойственности выполняется.

 

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

 

 

Второе ограничение выполнилось как равенство, следовательно, второй вид сырья используется полностью при оптимальном плане выпуска продукции и является дефицитным, его остаток х6*=0, его оценка равна >0.

Первое и третье ограничения выполнились как строгое неравенство. Это означает, что сырье первого и третьего вида не используются полностью при оптимальном плане и являются недефицитными, а остатки этих видов сырья =400, а =1080. Оценки сырья равны нулю: =0, =0.

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

 

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

Третье ограничение выполнилось как равенство, это означает, суммарная оценка сырья, используемого для производства единиц продукции вида С, равна соответствующей прибыли, следовательно производить это изделие экономически целесообразно, т.е. >0.

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

Увеличение сырья «Пластмасса» на одну единицу приведет к получению нового оптимального плана, в котором прибыль увеличиться на 5/4, при этом остатки сырья S1 увеличатся на ¼ , а запасы сырья S2 сократятся на ½.

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

 

Способ.

 

Найдем решение двойственной задачи с использованием третьей теоремы двойственности:

 

 

В оптимальный план вошли вектора: A5, A3, A7, поэтому .

 

Решение двойственной задачи найдено.

 

Анализ устойчивости

 

Определим также интервалы изменения запасов каждого вида сырья, при котором оптимальный план двойственной задачи не изменится.

bi – запасы i-ого вида сырья,

∆ bi - изменение запаса i-ого вида сырья.

 

Исходя из последней симплекс-таблицы, получим :

 

 

 

Таким образом, в результате перемножения матриц получим следующую систему неравенств:

 

 

 

.

 

а) Пусть , тогда . Значит, . Следовательно, сырье 1-ого вида (металл) не является дефицитным, увеличение его запаса невозможно, но возможно уменьшение не более чем на 400 единиц, при этом количество металла не должно быть меньше 900 единиц.

б) Пусть , тогда . Значит, . Следовательно, сырье 2-ого вида (пластмасса) является дефицитным, увеличение его запаса целесообразно не более чем на 800 единиц.

в) Пусть , тогда . Значит, . Следовательно, сырье 3-ого вида (резина) не является дефицитным, увеличение его запаса невозможно, но возможно уменьшение не более чем на 2700 единиц, при этом количество резины не должно быть меньше 180 единиц.

 

 





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