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

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

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

                                                                    _(1.3.)

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

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

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

2. Симплекс-метод

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

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

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

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

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

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

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

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

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

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

     (1)

     (2)

     (3)

     (4)

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    

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

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

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

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

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

    

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

      

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Если  условие оптимальности выполнено, то решение ЗЛП симплекс-методом  закончено, необходимо выделить оптимальные  значения переменных и оптимальное  значение целевой функции.  

3. Технология  решения задач  линейного программирования с помощью режима Поиска решений в среде EXCEL.

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

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