Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Решение ЗЛП средствами MSExcel.Пример Решим задачу из Примера 2 раздела 1.3с использованием настройкиПоиск решенияMSExcel.
Для решения нашей задачи создадим в Excelкнигу с именем «Решение задачи линейного программирования». Подготовим данные на листе. Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений (строки 5-7). Заведем строку 9 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.
В ячейки D5, D6, D7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку E9 – формулу для зависимости целевой функции.
Далее необходимо воспользоваться надстройкой Поиск решения. На вкладке Данные в группе Анализ выберитекомандуПоиск решения. Появится диалоговое окно Поиск решения, которое необходимо заполнить следующим образом (для добавления ограничений пользуемся кнопкой Добавить):
Далее нажимаем кнопку Параметры и в появившемся окне Параметры поиска решений устанавливаем флажок неотрицательные значения, линейная модель и нажимаем OK.
В окне Поиск решения после нажатия кнопкиВыполнить появляется окно Результаты поиска решения, в котором выбираем сохранение найденных значений и нажимаем кнопку ОК.
Результаты поиска решений (для ячеек В2 и С2 установлены числовые форматы с 0 знаками после запятой):
Получили Двойственные задачи  Рассмотрим задачу использования сырья. Для изготовления двух видов продукции P1, P2 предприятие использует 4 вида сырья S1, S2, S3, S4. Запасы сырья и расходы на изготовление каждого вида продукции приведены в таблице. Составить план производства, при котором стоимость выпущенной продукции будет максимальной.
Для составления математической модели задачи введем две переменные: x1 – количество произведенной продукции P1 и x2 – количество произведенной продукции P2. По определению эти переменные должны быть неотрицательны. При производстве продукции предприятие израсходует 2x1+3x2 единиц сырья S1, 2x1+x2единиц сырья S2, 3x2 единиц сырья S3 и 4x2 единиц сырья S4. Предприятие не может израсходовать сырья больше, чем у него имеется, поэтому получаем следующие ограничения на использование имеющегося сырья:
От продажи выпущенной продукции предприятие получит 10x1+6x2 у.е. Получаем математическую модель задачи:
Предположим, что по некоторым обстоятельствам потребитель отказался от заказа, и предприятие решило продать сырье, не выпуская продукцию. По каким ценам будет продаваться сырье? Составим математическую модель возникшей задачи. Введем три переменные: y1- стоимость единицы сырья S1, y2- стоимость единицы сырья S2, y3- стоимость единицы сырья S3, y4- стоимость единицы сырья S4. По определению эти переменные должны быть неотрицательны. Предприятию имеет смысл не выпускать продукцию только в случае, если выручка от продажи сырья не меньше, чем стоимость произведенной из этого сырья продукции. На производство одной единицы продукции P1 расходуется 3 единицы сырья S1, 4 единицы сырья S2 и 4 единицы сырья S4. Если не выпускать продукцию P1, а продать все сырье, из которого его можно изготовить, то выручка от реализации этого сырья составит
С другой стороны, покупатель сырья хочет купить это сырье как можно дешевле. На покупку сырья будет затрачено
Составленная задача называется двойственной к исходной. Как видно из построенных моделей кроме экономической связи между ними существует и математическая связь. Перечислим условия, связывающие построенные задачи. 1. Количество переменных двойственной задачи соответствует количеству ограничений исходной задачи. 2. Цели задач противоположны: в исходной задаче функция максимизируется, а в двойственной минимизируется. 3. Коэффициенты при неизвестных в целевой функции исходной задачи являются правыми частями в ограничениях двойственной задачи и, наоборот, правые части ограничений исходной задачи являются коэффициентами при неизвестных в целевой функции двойственной задачи. 4. Знаки неравенств задач противоположны: все неравенства исходной задачи имеют знак «£», а двойственной «³». 5. Матрица коэффициентов при неизвестных в системе ограничений двойственной задачи является транспонированной матрицей коэффициентов при неизвестных в системе ограничений исходной задачи .
6. Переменные обеих задач не отрицательны. Заметим, что если к двойственной задаче построить двойственную, то получим исходную задачу. Поэтому говорят о паре симметричных взаимно двойственных задач. Рассмотрим правила построения двойственной задачи в общем случае. Пусть имеется задачи линейного программирования в общем виде:
Каждой задаче такой можно поставить в соответствие двойственную задачу:
Построение двойственной задачи происходит по следующим правилам: 1. Сначала производится согласование цели исходной задачи и неравенств ее системы ограничений. Если целевая функция максимизируется, то все знаки неравенств должны быть «£», если целевая функция минимизируется, то все знаки неравенств должны быть «³». Если какое-нибудь неравенство не соответствует цели задачи, то его следует домножить на -1 для смены знака на противоположный. 2. Каждому i-му ограничению системы исходной задачи соответствует переменная yi двойственной задачи и, наоборот, каждому j-му ограничению системы двойственной задачи соответствует переменная xi исходной задачи. Подпишем эти соответствия слева от систем. 3. Коэффициенты при неизвестных в целевой функции двойственной задачи совпадают с правыми частями системы ограниченийисходной задачи. 4. Цель двойственной задачи противоположна цели исходной задачи. 5. Матрица системы ограничений двойственной задачи получается транспонированием из матрицы системы ограничений исходной задачи; 6. Коэффициенты правых частей двойственной задачи – это коэффициенты при неизвестных в целевой функции исходной задачи. 7. Знаки ограничений двойственной задачи могут быть либо неравенствами, соответствующими цели двойственной задачи, либо равенствами. Неравенство ставится в случае, если на переменную исходной задачи, соответствующую ограничению двойственной задачи, наложено условие неотрицательности. Если такого условия нет, то соответствующее ограничение двойственной задачи – уравнение. 8. На переменную yj двойственной задачи следует наложить условие неотрицательности лишь в том случае, если i-е ограничение исходной задачи – неравенство. Пример 1 Построим двойственную задачу для задачи
Согласуем знаки неравенств с целью задачи. Целевая функция максимизируется, поэтому все неравенства должны быть «£». Второе неравенство не согласовано с целью функции, умножим его обе части на -1.
В системе имеется 3 ограничения, поэтому в двойственной задаче будет 3 переменные, подпишем эти переменные слева от ограничений.
Матрица левой части системы ограничений исходной задачи:
Матрица левой части системы ограничений двойственной задачи:
Двойственная задача:
Второе ограничение является уравнением, т.к. на переменную x2 не наложено условие неотрицательности. На переменную y3 не наложено условие неотрицательности, т.к. соответствующее y3 ограничение исходной задачи – уравнение. В силу того, что все три формы записи задачи линейного программирования (общая, симметричная, каноническая) эквиваленты, далее будем рассматривать пару симметричных двойственных задач.
Двойственная задача:
Следующие теоремы дают зависимости между решениями пары двойственных задач. Теорема 1 (Основное неравенство теории двойственности) Пусть Экономический смысл Теоремы 1 заключается в том, что при любом допустимом плане производства общая стоимость всей произведенной продукции не превосходит суммарной оценки ресурсов, соответствующей любому допустимому решению двойственной задачи. Теорема 2 (Достаточный признак оптимальности решения) Пусть Экономический смысл Теоремы 2 заключается в том, что планы производства и оценки ресурсов оптимальны, если стоимость произведенной продукции совпадает с суммарной оценкой ресурсов. Теорема 3 (О минимаксе) Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причем Экономический смысл Теоремы 3 заключается в том, что максимально возможная стоимость произведенной продукции совпадает с минимально возможной стоимостью сырья. Теорема 4 (Равновесия) Пусть
Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением. Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится. В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений. Пример 2 Составить двойственную задачу и найти ее решение по теореме равновесия
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.
Двойственная задача:
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.
Подставим в составленную систему оптимальное решение исходной задачи:
Произведение равно нулю, если один из множителей равен 0. Получаем
Тогда,
Оптимальное решение двойственной задачи Пример 3 Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия
Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.
Подставим в составленную систему оптимальное решение исходной задачи:
Произведение равно нулю, если один из множителей равен 0. Получаем
Тогда,
Вычтем из первого уравнения второе:
Оптимальное решение двойственной задачи Окончательно, Вопросы для самопроверки 1. Может ли система ограничений общей ЗЛП включать строгие неравенства? 2. Может ли целевая функция ЗЛП содержать нелинейные выражения из переменных? 3. Может ли допустимое решение ЗЛП содержать отрицательную компоненту? 4. Чем отличается оптимальное решение ЗЛП от допустимого? 5. Чем отличается канонический вид ЗЛП от общего? 6. Каждая ли симметрическая задача может быть приведена к каноническому виду? Если да, то как это делается? 7. Может ли каноническая задача быть приведена к общему виду? 8. Какое максимальное число неравенств может содержать ЗЛПс двумя переменными? 9. Как строится ОДР ЗЛПс двумя переменными? 10. Может ли ОДР быть невыпуклым многоугольником? 11. Может ли ОДР быть открытым множеством? Пустым? 12. Что такое градиент? Как его строить? 13. Что такое линия уровня? Как ее строить? 14. Может ли линия уровня целевой функции быть параллельной вектору целевой функции? 15. Может ли ЗЛПс двумя переменными иметь два и только два оптимальных решения? 16. В каком случае задача ЛП с двумя переменными не имеет решения? 17. Какой вывод можно делать из того, что ОДР не ограничена по направлению, противоположному вектору целевой функции? 18. Сколько переменных может содержать ЗЛП, которую можно решить графически? 19. Можно ли для ЗЛП, содержащей в системе ограничений неравенства разных направлений, построить двойственную задачу? 20. Если в основной задаче отсутствуют условия неотрицательности переменных, то какие последствия это влечет в двойственной задаче задаче? 21. Чем отличаются матрицы систем ограничений в паре двойственных задач? 22. Какова связь между экстремальными значениями пары двойственныхзадач? 23. Что можно сказать о решении двойственной задачи, если решение основной задачи не существует по причине несовместимости ее системы ограничений? 24. В чем смысл теоремы равновесия? |
||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2018-06-01; просмотров: 285. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |
||||||||||||||||||||||||||||
.Решение совпадает с найденным графическим способом.
. Аналогично, выручка от реализации сырья, из которого можно изготовить продукцию P2, составит 
. Выручка от продажи сырья должна быть не меньше стоимости единицы соответствующей продукции. Получаем ограничения:
у.е. Получаем математическую модель задачи:
и 
- допустимые решения пары двойственных задач в симметричной форме. Тогда, 
.
и 
- допустимые решения пары двойственных задач и 
. Тогда, X*, Y* – оптимальные решения этих задач.
. Если одна из пары двойственных задач имеет неограниченную функцию, то система ограничений второй задачи не совместна.
, если известно решение исходной задачи: 
.
.
По Теореме 3 
. Окончательно, 
.
В разделе 1.5 было найдено решение исходной задачи средствами MSExcel:
Двойственная задача:
.
Þ 
По Теореме 3 
.