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

--PAGE_BREAK--Глава 1. Теоретическая часть 1.1.      Решение оптимизационной задачи линейного программирования
Линейное программирование — один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

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

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

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

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.

Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.

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

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

Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.

Стандартная задача ЛП

                                                                                                               (1.1)

или, в матричной записи,



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

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

Каноническая задача ЛП

                                                                       (1.2)

или, в матричной записи,



Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП

В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:

                                                               (1.3.)

Здесь. Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .

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

При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации), называется целевой функцией. Вектор , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи.
    продолжение
--PAGE_BREAK--1.2.      Симплекс-метод
 Симплекс – метод– это алгебраический метод решения задач линейного программирования. В процессе вычислений производиться последовательный обход вершин многогранника решений (ОДР.) с проверкой в каждой вершине условий оптимальности. При этом каждый переход в смежную вершину сопровождается улучшением целевой функции.

Вычислительные процедуры симплекс — метода.

При графическом методе решения ЗЛП оптимальному решению соответствует всегда одна из угловых (экстремальных) точек пространства решений. Это результат положен в основу построения симплекс-метода. Симплекс-метод не обладает наглядностью геометрического представления пространства решений.

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

Обозначим: – общее количество переменных в ЗЛП, представленной в канонической форме;   — количество исходных переменных;   — количество ограничений,   — количество дополнительных переменных, тогда .

Каждая вершина многогранника решений имеет   — ненулевых переменных и () — нулевых переменных.

Ненулевые переменные называются базисными, нулевые переменные – небазисными.

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

Для получения решения составляется начальный допустимый базис, в котором базисные переменные должны быть представлены в виде единичных орт. Это означает, что уравнения, представляющие данную вершину должны включать каждую базисную переменную только в одной строке с коэффициентом, равным 1.

При выборе начального допустимого базиса для составления симплекс-таблицы на первом шаге СТ(0) исходные  переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные  в равенствах (2) — (4) являются базисными и в   — строку входят с коэффициентами, равными 0. Для заполнения симплекс-таблицы необходимо целевую функцию преобразовать к виду . Таким образом, окончательно получаем:

(1)

(2)

(3)

(4)

При составлении симплекс-таблицы придерживаются следующих правил:

-в крайнем левом столбце располагаются базисные переменные и ;

-в крайнем правом столбце располагаются правые части ограничений;

-в первой строке располагаются переменные в определённом порядке:

сначала , потом небазисные переменные, базисные переменные располагаются в последних  столбцах перед правой частью (ПЧ). Запишем коэффициенты в СТ(0):
















ПЧ



1

-

-

















1

















1

















1





Рисунок 1.1 Пример симплекс-таблицы

Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в  – строке текущей симплекс-таблицы.

Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в  – строке являются неотрицательными (>0);

Для задачи минимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неположительными (

Если в задаче максимизации (минимизации) у одной небазисной переменной в  – строке коэффициент 0), то текущая точка не является оптимальной и необходимо изменить базис. Для этого выбирают небазисную переменную, имеющую максимально отрицательный (положительный) коэффициент в  – строке. Выбранная небазисная переменная будет включаться в новый базис, поэтому называется включаемой переменной. Базисная переменная, которая будет выведена из базиса, называется исключаемой переменной.

Исключаемой переменой будет та базисная переменная, которая первой обратится в «0» при переходе в смежную вершину после ввода включаемой переменной.

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

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

Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).

Чтобы определить исключаемую переменную необходимо:

-разделить правые части всех базисных переменных (кроме   — строки) на соответствующие положительные коэффициенты разрешающего столбца;

-выбрать из полученных отношений наименьшее.

Делить на «0» и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.

Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).

Для произвольной квадратной матрице размерности n, имеющей в качестве (n— 1) столбца единичные орты, расположенные в соответствии с единичными ортами единичной матрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали, обратная матрица находится по следующему правилу:



Рисунок 1.2 Транспонированная матрица

Каждый элемент j– столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М – метод.

Если исходное ограничение записано в виде равенства "=" или имеет знак "", то нельзя сразу получить допустимое начальное базисное решение, т. к. при записи задачи в стандартной форме, после введения дополнительных переменных может получиться вариант, когда полученные уравнения не позволяют сформировать начальный допустимый базис в виде единичных орт.  В этом случае для нахождения начального допустимого базиса вводятся дополнительно искусственные переменные . Искусственные переменные не имеют отношения к содержанию поставленной задачи, их введение допустимо только в том случае, если соответствующая схема вычислений будет обеспечивать получение оптимального решения, в котором все искусственные переменные окажутся равными нулю.

Переменные Rопределяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М>0).



Свойство М: При сложении (вычитании) с любой конечной величиной , определяющей любое значение, которое может принимать каждая из переменных исходной ЗЛП, её значение (переменной М) не меняется, а именно,

 

При составлении начальной симплекс-таблицы все переменные начального допустимого базиса (дополнительные и искусственные) должны располагаться в последних mстолбцах перед правой частью.

Алгоритм получения оптимального решения:

1. Переход от неравенств к равенствам с учётом правил перехода — введение остаточных, избыточных, искусственных переменных и коэффициентов штрафа;

2. Определение числа базисных и небазисных переменных;

3. Получение   — строки для заполнения СТ(0. Для этого необходимо целевую функцию преобразовать к виду ; для чего из соответствующих равенств ограничений выразить искусственные переменные  и подставить в  строку и привести к рациональному виду;

4. Заполнение СТ(0). Перенесение коэффициентов   — строки и равенств ограничений в соответствующие строки и столбцы симплекс-таблицы;

5. Исследование  функции на условие оптимальности:

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

определение включаемой переменной из небазисных переменных;

6. Определение разрешающей строки по условию допустимости:

определение минимального отношения при делении правых частей ограничений на положительные коэффициенты разрешающего столбца;

определение исключаемой переменной из начального базиса;

7. Определение разрешающего элемента РЭ;

8. Получение B(0). Замена в матрице начального базиса коэффициентов исключаемой переменной на коэффициенты включаемой переменной; вычисление B(0) по соответствующему правилу;

9. Определение элементов СТ(1) = В(0) СТ(0);

10. Исследование -строки СТ(1) на условие оптимальности.

Если условие не выполнено, то вычисления продолжаются и необходимо повторить пункты 5-10.

Если условие оптимальности выполнено, то решение ЗЛП симплекс-методом закончено, необходимо выделить оптимальные значения переменных и оптимальное значение целевой функции.
    продолжение
--PAGE_BREAK--1.3.             Технология решения задач линейного программирования с помощью режима Поиска решений в среде EXCEL.
Поиск решения -это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Ecли, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту над­стройку. Выберите команду СервисÞ
Надстройкии активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с по­мощью программы установки Excel (или Office) установить надстройку Поиск решения.

 После выбора команд Сервис ÞПоиск решения появится диалоговое окно Поиск решения.

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

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

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

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

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

Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячей­ки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в це­левой ячейке. Для поиска решения можно указать до 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

А7: В7 >= 0

-После ввода последнего (второго) ограничения в окне Добавить нужно нажать кнопку ОК.

10. Далее следует нажать кнопку Выполнить, после чего будет получено решение  (рисунок 1.6).




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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                        

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



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

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

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

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

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

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

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

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

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

f(X)

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

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

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


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

Пусть X=(x1,x2,...xn) — допустимое решение прямой задачи, а Y= (y1,y2,...ym) — допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

                                           *

                                                    **

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

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,...,Xn) и оптимальный вектор оценок Y=(Y1,Y2,...,Ym):

            (4)

          (5)

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

Теорема об оценках.


Значения переменных Yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

                                                             

Решая ЗЛП  симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.
    продолжение
--PAGE_BREAK--