Автор работы: Пользователь скрыл имя, 16 Ноября 2010 в 00:30, Не определен
Введение
Глава 1. Теоретическая часть
1.1. Решение оптимизационной задачи линейного программирования
1.2. Симплекс-метод
1.3. Технология решения задач линейного программирования с помощью режима Поиска решений в среде EXCEL
Первая теорема двойственности
Вторая теорема двойственности
Теорема об оценках
1.5. Области допустимых решений для двойственных переменных
В диалоговом окне Поиск решения есть три основных параметра:
• Установить целевую ячейку
• Изменяя ячейки
• Ограничения
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение.
Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.
Третий параметр, который нужно вводить, для Поиска решения – это ограничения.
Для решения задачи необходимо:
Запустить Поиск решений.
Рассмотрим технологию решения задачи линейного программирования в Excel.
Решить ЗЛП:
Перейдем к решению задачи в Excel.
1. В ячейки А3:В3 введем значения коэффициентов целевой функции (18 и 12).
2. В
ячейки А10:В12 введем значения
коэффициентов ограничений (
3. В
ячейки В15:В17 введем значения
правых частей ограничений (
4. Отведем
под переменные
,
диапазон ячеек
А7:В7 (пока они пустые) как показано на
рис. 1.2
Рисунок 1.2 Ввод исходных данных для задачи планирования производства
Выполним расчеты:
5. В ячейку С3 введем формулу: =СУММПРОИЗВ(А3:В3;А7:В7), которая представляет целевую функцию.
6. В ячейку А15 введем формулу: = СУММПРОИЗВ($A$7:$B$7;А10:В10), которая представляет левую часть первого ограничения.
7. С
помощью автозаполнения
Рабочий
лист Excel примет вид, показанный на рис.
2 и на рис. 3 (значения ячеек, в которые
вносились формулы, будут пока равны нулю,
так как неизвестны
).
Рисунок
1.3 Рабочий лист Excel после внесения формул
Рисунок
1.4 Расчеты для решения задачи планирования
производства
8.
Для дальнейшего решения
9.
Диалоговое окно Поиск решения
заполним, как показано на рисунке 1.5
Рисунок
1.5 Заполненное окно Поиск решения
- Установить целевую ячейку С3, равной максимальному значению
- Изменяя ячейки А7:В7
- Ограничения: нажать кнопку Добавить и в открывшееся окно ввести диапазоны (можно их выделить, они сами впишутся в окно Добавить):
А15:А17 <= В15:В17
А7:В7 >= 0
- После ввода последнего (второго) ограничения в окне Добавить нужно нажать кнопку ОК.
10. Далее
следует нажать кнопку
Рисунок 1.6 Полученное решение задачи планирования производства
Ответ
задачи: Функция
достигает максимального
значения равного 12 при х1=4 и х2=4.
Двойственная
задача (ДЗ) – это вспомогательная
задача линейного программирования,
формулируемая с помощью
С
каждой задачей линейного
Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1)
целевая функция исходной
2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица Ат в двойственной задаче получаются друг из друга транспонированием;
3)
число переменных в
4)
коэффициентами при
5)
каждому ограничению одной
Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:
Модель двойственной задачи имеет вид:
Две приведенные задачи образуют пару симметричных двойственных задач.
Основные
утверждения о взаимно
Первая теорема двойственности.
Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:
1.
В прямой и двойственной
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограниченна сверху. При этом у двойственной задачи будет пустое допустимое множество.
3.
В двойственной задаче
4.Обе из рассматриваемых
Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов yi. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:
f(X)
< g(Y}, т. е. ценность всей
Из первой теоремы двойственности следует, что при оптимальной
производственной программе и векторе оценок ресурсов производственные потери равны нулю.
Вторая теорема двойственности
(теорема о дополняющей нежесткости)
Пусть X=(x1,x2,...xn) - допустимое решение прямой задачи, а Y= (y1,y2,...ym) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:
*
**
Условия (*) и (**) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,...,Xn) и оптимальный вектор оценок Y=(Y1,Y2,...,Ym):
(4)
(5)
Условия
(4) можно интерпретировать так: если
оценка yi единицы ресурса i-го вида положительна,
то при оптимальной
Информация о работе Линейные и нелинейные модели в экономике