Линейные и нелинейные модели в экономике

    В диалоговом окне Поиск решения есть три основных параметра:

    • Установить целевую ячейку

    • Изменяя ячейки

    • Ограничения

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

    Второй  важный параметр средства Поиск решения  — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

    Третий  параметр, который нужно вводить, для Поиска решения – это ограничения.

            Для решения задачи необходимо:

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
2. Ввести исходные данные.
3. Ввести зависимость для целевой функции
4. Ввести зависимости для ограничений.

    Запустить Поиск решений.

5. Назначение целевой функции (установить целевую ячейку).
6. Ввод ограничений.
7. Ввод параметров для решения ЗЛП.

  Рассмотрим  технологию решения задачи линейного  программирования в 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. С  помощью автозаполнения скопируем  формулу, введенную в ячейку  А15, в ячейки А16, А17.

Рабочий лист 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).

 

Рисунок 1.6 Полученное решение задачи планирования производства

Ответ задачи: Функция достигает максимального значения равного 12 при х1=4 и х2=4. 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. Постановка  и решение двойственной задачи линейного программирования в экономике

    Двойственная  задача (ДЗ) – это вспомогательная  задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий  прямой задачи. Заинтересованность в  определении оптимального решения  прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при ПЗ. Трудоёмкость вычислений при решении ЗЛП в большей  степени зависит от числа ограничений, а не от количества переменных. Для  перехода к ДЗ необходимо, чтобы  прямая задача была записана в стандартной  канонической форме. При представлении  ПЗ в стандартной форме в состав переменных включаются также избыточные и остаточные переменные.

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

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

    Переменные  двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

    1) целевая функция исходной задачи  формулируется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на  максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум — вид ³;

    2) матрица А, составленная из  коэффициентов при неизвестных  в системе ограничений исходной задачи и аналогичная матрица    А^т   в двойственной задаче получаются друг из друга транспонированием;

    3) число переменных в двойственной  задаче равно числу функциональных  ограничений исходной задачи, а  число ограничений в системе   двойственной задачи — числу  переменных в исходной задаче;

    4) коэффициентами при неизвестных  в целевой функции   двойственной  задачи являются свободные члены  в  системе ограничений исходной  задачи, а правыми частями в  ограничениях двойственной задачи  — коэффициенты при неизвестных  в целевой функции исходной  задачи;

    5) каждому ограничению одной задачи  соответствует переменная другой  задачи: номер переменной совпадает  с номером ограничения; при  этом ограничению, записанному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственнвой; задачи может принимать как положительные, так и отрицательные значения

    Модель  исходной (прямой) задачи в общем  виде может быть записана следующим  образом:

                                           

    Модель  двойственной задачи имеет вид:

    

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

    Основные  утверждения о взаимно двойственных задачах содержатся в двух следующих  теоремах.

    Первая  теорема двойственности.

    Для взаимно двойственных задач имеет  место один из взаимоисключающих  случаев:

    1. В прямой и двойственной задачах  имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).

    2. В прямой задаче допустимое  множество не пусто, а целевая  функция на этом множестве  не ограниченна сверху. При этом  у двойственной задачи будет  пустое допустимое множество.

    3. В двойственной задаче допустимое  множество не пусто, а целевая  функция на этом множестве  не ограничена снизу. При этом  у прямой задачи допустимое  множество оказывается пустым.

     4.Обе из рассматриваемых задач  имеют пустые допустимые множества.

    Экономический смысл первой теоремы двойственности следующий. План производства Х и  набор оценок ресурсов У оказываются  оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции  равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y_i. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:

    f(X) < g(Y}, т. е. ценность всей выпущенной  продукции не превосходит суммарной  оценки имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

    Из  первой теоремы двойственности следует, что при оптимальной

    производственной  программе и векторе оценок ресурсов производственные потери равны нулю.

    Вторая  теорема двойственности

    (теорема  о дополняющей  нежесткости)

    Пусть X=(x₁,x₂,...x_n) - допустимое решение прямой задачи, а Y= (y₁,y₂,...y_m) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

           *

                             **

    Условия (*) и (**) позволяют, зная оптимальное  решение одной из взаимно двойственных задач, найти оптимальное решение  другой задачи.

    Из  второй теоремы двойственности в  данном случае следуют такие требования на оптимальную производственную программу X=(X₁,X₂,...,X_n) и оптимальный вектор оценок Y=(Y₁,Y₂,...,Y_m):

       (4)

       (5)

    Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна  нулю. Из условия (5) следует, что если j-й вид продукции вошел в  оптимальный план, то он в оптимальных  оценках неубыточен, если же j-й вид  продукции убыточен, то он не войдет в план, не будет выпускаться.