Создан заказ №2918126
21 апреля 2018
Использовать аппарат теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования
Как заказчик описал требования к работе:
Оформить все графики в контрольной; 2. начертить схемы в соответствие со стандартами (можно в графическом редакторе на пк). Работу нужно сдавать в пятницу, поэтому 2 дня на выполнение максимум. Подробное задание прикрелено.
Фрагмент выполненной работы:
Использовать аппарат теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
1 вариант.
Для изготовления четырех видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и цены реализации единицы каждого вида продукции приведены в таблице.
Тип сырья Нормы расхода сырья на одно изделие
Запасы
сырья
А
Б
В
Г
I
II
III
1
1
1
2
1
3
1
2
3
0
1
2
18
30
40
Цена изделия 12 7 18 10
Требуется:
Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный план выпуска продукции. (работа была выполнена специалистами author24.ru)
Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.
На основе свойств двойственных оценок и теорем двойственности:
проанализировать использование ресурсов в оптимальном плане исходной задачи;
определить, как изменится выручка при увеличении запасов сырья I и II вида на 4 и 3 единицы соответственно и уменьшении на 3 единицы сырья III вида;
оценить целесообразность включения в план изделий "Д" ценой 10 ед., на изготовление которого расходуется по две единицы каждого вида сырья.
Прямая задача
right26479500F(X) = 12x1+7x2+18x3+10x4
x1+2x2+x3≤18
x1+x2+2x3+x4≤30
x1+3x2+3x3+2x4≤40
x1,x2,x3,x4 ≥ 0
Строим шаблон решения
Заполняем окно инструмента Поиск решения
Получаем решение
Решение:
x1=18; x2=0; x3=0; х4=11
F(X) = 326
Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A.
1 2 1 0 18
1 1 2 1 30
1 3 3 2 40
12 7 18 10
Транспонированная матрица AT.
1 1 1 12
2 1 3 7
1 2 3 18
0 1 2 10
18 30 40
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (↔), называются сопряженными.
31051530924518y1+30y2+40y3 → min
y1+y2+y3≥12
2y1+y2+3y3≥7
y1+2y2+3y3≥18
y2+2y3≥10
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Исходная задача I Двойственная задача II
12x1+7x2+18x3+10x4 → max ↔ 18y1+30y2+40y3 → min
x1 ≥ 0 ↔ y1+y2+y3≥12
x2 ≥ 0 ↔ 2y1+y2+3y3≥7
x3 ≥ 0 ↔ y1+2y2+3y3≥18
x4 ≥ 0 ↔ y2+2y3≥10
x1+2x2+x3≤18 ↔ y1 ≥ 0
x1+x2+2x3+x4≤30 ↔ y2 ≥ 0
x1+3x2+3x3+2x4≤40 ↔ y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи. Найдем решение двойственной задачи у* воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.
Поскольку x1>0, 1-е ограничение в двойственной задаче будет равенством.
Поскольку x4>0, 4-е ограничение в двойственной задаче будет равенством.
Таким образом, решение двойственной задачи сводится к решению уравнений при следующих условиях:
3390909525y2 = 0
y1+y2+y3 = 12
y2+2y3 = 10
18y1+30y2+40y3 → min
377190297815или
y1+y3 = 12
2y3 = 10
18y1+30y2+40y3 → min
Оптимальный план двойственной задачи равен:
y1 = 7, y2 = 0, y3 = 5
Z(Y) = 18*7+30*0+40*5 = 326
Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной 339090246380математической модели:
1*18 + 2*0 + 1*0 + 0*11 = 18 = 18
1*18 + 1*0 + 2*0 + 1*11 = 29 < 30
1*18 + 3*0 + 3*0 + 2*11 = 40 = 40
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1 ≠ 0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y2 = 0.
Неиспользованный экономический резерв ресурса 2 составляет 1 (30-29).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3 ≠ 0).
Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны) - они будут равны нулю.
Посмотрим на отчет об устойчивости, полученный при решении прямой задачи
120014323278545777153261360
Таким образом, 1-й запас может быть уменьшен на 18 или увеличен на 2.
Интервал изменения равен:
[18-18; 18+2] = [0;20]
2-й запас может быть уменьшен на 1.
2-й вид ресурса в оптимальном плане недоиспользован, является недефицитным. Увеличение данного ресурса приведет лишь к росту его остатка. При этом структурных изменений в оптимальном плане не будет, так как двойственная оценка y2 = 0.
Интервал изменения равен:
[30-1; +∞] = [29;+∞]
3-й запас может быть уменьшен на 22 или увеличен на 2...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
200 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
22 апреля 2018
Заказ завершен, заказчик получил финальный файл с работой
5
Использовать аппарат теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.docx
2018-11-10 14:34
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Безумно благодарна автору за работу). Выполнена качественно и раньше срока. Данного автора рекомендую!!!
Хочешь такую же работу?
300 ₽
