Оптимизация заполнения гостиничного комплекса на примере предприятия ООО "Омега", гостиница "Камея"

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

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

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

* постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через

* зависимые факторы (элементы решения) x₁, х₂, ..., которые в известных пределах мы можем выбирать по своему усмотрению.

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

Z = f (x₁, x₂,…, )

Идею построения математической модели для объекта управления можно представить в виде следующей схемы:

Рисунок 8. Урубков А.Р. Курс MBA по оптимизации управленческих решений. Практическое руководство по использованию моделей линейного программирования / А.Р. Урубков. - М.: Альпина Бизнес Букс, 2006. - с. 13

2.2 Оптимизация в экономике

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

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

Оптимизационную задачу можно сформулировать в общем виде:

Найти переменные х₁, х₂, ..., x_n, удовлетворяющие системе неравенств (уравнений):

= (х₁, х₂, х₃,..., х_n)b_i, i = (2.1)

и обращающие в максимум (или минимум) целевую функцию, т.е.

Z = f (x₁ х₂, ..., х_n) mах (min). (2.2)

Как известно, упорядоченная совокупность значений n переменных x₁, x₂,…,x_n представляется точкой n-мерного пространства. Обозначим эту точку через Х= (x₁, х₂, ..., х_n), а само оптимальное решение - X* = (x*₁, х*₂, ..., х*_n).

В тех случаях, когда функции f и , хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако применение этих методов в исследовании операций весьма ограниченно, так как задача определения условного экстремума функции я переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким -- тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция Z задана таблично. В этих применяются методы математического программирования.

В зависимости от характера ограничений и целевой функции различают следующие типы оптимизационных задач:

ь Если критерий эффективности Z = f(x₁ х₂, ..., х_n) представляет линейную функцию, а функции = (х₁, х₂, х₃,..., х_n) в системе ограничений также линейны, то такая задача является задачей линейного программирования.

ь Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования.

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

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

ь Если критерий эффективности (2.2) и система ограничений (2.1) задаются функциями вида с… то имеем задачу геометрического программирования.

ь Если функции f и (или) в выражениях (2.2) и (2.1) зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, -- задачу стохастического программирования.

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

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.

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

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

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

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

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

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

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

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

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

Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы -- детерминированными, динамические процессы -- статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т. Саати, как "искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами" [Вентцель Е.С. Исследование операций. -- М.: Сов. радио, 1972].Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман; Под ред. - проф. Н.Ш. Кремера. - М: ЮНИТИ, 2002..

гостиница оптимизация симплекс отель

2.3 Линейное программирование

2.3.1 Общая постановка задачи

В общем виде задача линейного программирования может быть сформулирована как задача нахождения наибольшего (наименьшего) значения линейной функции:

(3.1)

на некотором множестве D Rⁿ ,где x D удовлетворяют системе ограничений:

(3.2)

и ограничениям:

(3.3)

He умаляя общности, можно считать, что в системе (3.2) первые k ограничений являются неравенствами, а последующие - l уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак.

Ограничения (3.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями), вытекающими из реального экономического смысла разрешимости задач.

Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции

эквивалентна задаче поиска минимума функции

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х*= (x₁*,x₂*,…,x_n*) системы ограничений (4.2), удовлетворяющее условию (3.3), при котором линейная функция (3.1) принимает оптимальное (максимальное или минимальное) значение.

Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй -- о содержательной стороне (экономической интерпретации).

При условии, что все переменные неотрицательны (x_j 0 , j=), а система ограничений состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной; если система ограничений состоит из одних уравнений, то задача называется канонической.

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

Общая идея перехода от общей задачи линейного программирования к канонической достаточно проста:

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

Ш переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

В ряде работ по математическому программированию стандартную задачу называют симметричной, а каноническую -- основной.

Каноническую задачу можно также представить в векторной или матричной форме.

1. Векторная форма записи:

Целевая функция

f(x)= cx> max (min)

при ограничениях P₁x₁+P₂x₂+…+P_nx_n=P, X 0,

где cx - скалярное произведение векторов C (с₁, c₂,…,с_n) и X (x₁,x₂,…,x_n), а векторы

P₁=, P₂=, … , P_n=, P= состоят соответственно из коэффициентов при переменных и свободных членов.

Векторное неравенство X0 означает, что все компоненты вектора X неотрицательны, т.е. x_j 0 , j=

2. Матричная форма записи:

Целевая функция

f(x)=CX > max (min)

при ограничениях AX=B, X 0,

где С = (с₁, c₂,…,с_n), A=, X=, B=

Здесь С -- матрица-строка, А -- матрица системы, X -- матрица-столбец переменных, В -- матрица-столбец свободных членов.

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные (n--m) переменных называются неосновными (или свободными). Если для системы m линейных уравнений с n переменными (m < n) ранг матрицы коэффициентов при переменных равен m, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы. Решение системы называется допустимым, если оно содержит лишь неотрицательные компоненты. В противном случае решение называется недопустимым. Среди бесконечного множества решений системы выделяют так называемые базисные решения.

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все (n--m) неосновных переменных равны нулю.

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

2.3.2 Условия существования и оптимальности решений

Решение задач ЛП требует разрешения трех проблем:

1. проблемы существования оптимального решения

2. проблемы установления необходимых и достаточных признаков оптимальности (т.е. характерных свойств, присущих точкам максимума и минимума)

3. проблемы численного вычисления оптимальных решений.

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

Сформулируем условия, при которых такие решения существуют.

В классических оптимизационных задачах применяют экстремальные точки двух видов: локальный максимум (минимум) и глобальный максимум (минимум). Точка x₀X называется точкой локального максимума (минимума), если f(x₀) f(x) [f(x₀) f(x)] для всех xO(x₀), где O(x₀) - окрестность точки x₀. Точка x₀X называется точкой глобального максимума (минимума), если эти неравенства выполняются для всех xX.

Достаточное условие существования оптимального решения определяется по теореме Вейерштрасса: Для того чтобы в оптимизационных задачах существовала точка глобального максимума (минимума) достаточно, чтобы допустимое множество X было компактно в Rⁿ, а целевая функция f непрерывна на X.

Ввиду сложности проверки ограниченности множества X на практике часто применяется следствие из этой теоремы:

Если функция f непрерывна на Rⁿ и , то f достигает своего глобального минимума (максимума) в любом замкнутом подмножестве X пространства Rⁿ.

Целевая функция f(x) может иметь глобальный оптимум (единственный) либо несколько локальных.

Большинство методов оптимизации позволяет вычислить только локальный оптимум.

В задачах оптимизации непрерывной функции f(x) на замкнутом допустимом множестве X каждый локальный оптимум будет глобальным, если:

1) f(x) - вогнутая (выпуклая вверх) функция в задаче максимизации и выпуклая в задачах минимизации;

2) X - выпуклое множество.

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

2.3.3 Геометрические свойства задач линейного программирования Минюк С.А. Математические модели в экономике: Учеб. пособие / С.А. Минюк, Е.А. Ровба, К.К. Кузьмич - Мн.: ТетраСистемс, 2002. - 432 с.

Определим геометрические свойства задачи линейного программирования:

1. Допустимое множество решений задачи линейного программирования либо пусто, либо является выпуклым многогранником в Rⁿ (как пересечение полупространств, описываемых ограничениями-неравенствами).

2. Если допустимое множество непусто и целевая функция ограничена (для задач максимизации - сверху, для задач минимизации - снизу), то существует хотя бы одно оптимальное решение.

3. Если в задаче линейного программирования f(x)=max (min) при условии xX допустимое множество X имеет хотя бы одну угловую точку, а целевая функция f(x) ограничена, то угловая точка x, в которой f(x) принимает наибольшее (наименьшее) значение среди всех угловых точек, является оптимальным решением данной задачи. Если таких угловых вершин несколько, то любая их выпуклая комбинация также является оптимальным решением.

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

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

2.3.4 Графический метод решения задач линейного программирования

Рассмотрим задачу ЛП в стандартной форме двумя переменными (n=2).

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

Целевая функция f(x)=c₁x₁+c₂x₂ max,

ограничения: (3.4)

x₁0, x₂0

Каждое из неравенств (3.4) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми , x₁=0, x₂=0.

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

Поведение целевой функции f(x)=c₁x₁+c₂x₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

Линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение, т.е. f(x)=a или c₁x₁+c₂x₂=a.

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

Градиентом функции f(x) называется вектор указывающий направление наиболее быстрого возрастания функции, и, стало быть, ориентированный перпендикулярно линиям уровня

Если линия уровня определяется уравнением f(x)=c_lx_l+c₂x₂=a , то этот вектор имеет вид:

и указывает направление возрастания функции.

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

Алгоритм решения можно записать следующим образом (рис.9):

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

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

3. Определить многоугольник решений (многоугольную область и т.д.);

4. Построить вектор ;

5. Построить прямую Z=c₁x₁+c₂x₂=0, проходящую через начало координат и перпендикулярную вектору ;

6. Передвигать прямую Z=c₁x₁+c₂x₂ в направлении вектора , в которой функция принимает максимально значение, либо устанавливают неограниченность функции сверху на множестве планов;

7. Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Рисунок 9. Решение задачи линейного программирования графическим методом

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

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

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

2.3.5.1 Общая идея метода

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

Классическим методом решения таких задач стал симплекс-метод, получивший также в литературе название метода последовательного улучшения плана, предложенный в 1947 г. американским математиком Джорджем Данцигом. Однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.

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

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

* способ определения какого-либо первоначального допустимого базисного решения задачи;

* правило перехода к лучшему (точнее, не худшему) решению;

* критерий проверки оптимальности найденного решения.

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

Алгоритм симплекс-метода для задач максимизации включает однократно выполняемый 0-этап и повторяемый конечное число раз 1-этап (стандартную итерацию):

0-этап состоит в выборе начального допустимого базисного решения ⁰

1-этап состоит в переходе от данного базиса ⁰ к другому, новому базису ¹ с таким расчетом, чтобы значение целевой функции Z увеличивалось, т.е. . Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. В конечном итоге находится некоторый базис ^k для которого искомый максимум, а соответствующее базисное решение является максимальным, либо выясняется, что задача не имеет решения.

Критерий оптимальности решения при отыскании максимума линейной функции записывается следующим образом Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман; Под ред. - проф. Н.Ш. Кремера. - М: ЮНИТИ, 2002.:

Если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимально.

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

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

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

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

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

Применяется так же метод Жордана-Гаусса Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. - 2-е изд., перераб. И доп. - М.: Финансы и статистика, 2005. (метод полного исключения) - приведение к базисному виду. Для стандартной задачи максимизации с ограничениями , алгоритм будет следующим:

1. Записать каноническую задач в форму жордановской таблицы, при этом все элементы столбца свободных членов b_i должны быть неотрицательны. Уравнения системы, в которых свободные члены отрицательны, предварительно нужно умножить на (-1).

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

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

4. Новые элементы таблицы вычисляются по правилу прямоугольника.

5. В процессе преобразований вычеркиваются строки, состоящие из одних нулей.

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

7. В итоге таблица преобразуется таким образом, что базисные переменные становятся выделенными, при предположении, что свободные неизвестные равны нулю.

2.3.5.2 Симплексные таблицы

С точки зрения обеспечения рациональности и наглядности вычислительного процесса выполнение алгоритма симплекс-метода удобно оформлять в виде последовательности таблиц. Алгоритм будет выглядеть следующим образом:

I. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

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

Он заключается в следующем.

В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную y₁, y₂, … y_k, которая имеет тот же знак, что и свободный член в правой части уравнения. Вначале включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения.

Составляем новую линейную функцию Т = F - М(y₁ + y₂ +…+ y_k), где М - произвольно большое число, и ищем ее максимум (Т-задача). Назовем М-функцией выражение М(y₁ + y₂ +…+ y_k)

Справедлива теорема Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман; Под ред. - проф. Н.Ш. Кремера. - М: ЮНИТИ, 2002.:

1. Если в оптимальном решении Т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. Т_mах = F_max, если y₁ = y₂ =…= y_k = 0, т.е. минимум М-функции равен 0).

2. Если имеется оптимальное решение Т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

3. Если T_mах =, то исходная задача также неразрешима, причем либо F_max=, либо условия задачи противоречивы.

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

На практике находят не минимум M-функции, а максимум (-M)-функции.

II. Исходную расширенную систему заносим в первую симплексную таблицу (таб. 1). Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: b_i = - c_i. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы - все переменные (отмечая при этом основные), во втором столбце - свободные члены расширенной системы b₁, b₂, … b_m. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и, второй строки) занесены коэффициенты a_ij при переменных из расширенной системы.

Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности при решении задачи на максимум - наличие в последней строке отрицательных коэффициентов b_i < 0 (c_i >0). Если таких нет, то решение оптимально, достигнут max F = c₀ (в левом нижнем углу таблицы), основные переменные принимают значения a_i0 (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент b_i< 0 в последней строке определяет разрешающий столбец s.

Составляем оценочные ограничения каждой строки по следующим правилам:

1. , если b_i и a_is имеют различные знаки;

2. , если b_i=0 и a_is<0;

3. , если a_is=0;

4. 0, если b_i=0 и a_is>0;

5. , если a_i0 и a_is имеют одинаковые знаки.

Определяем min . Если конечного минимума нет, то задача не имеет конечного оптимума (F_max = ). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей (генеральной) строкой.

На пересечении разрешающих (генеральных) строки и столбца находится разрешающий (генеральный) элемент a_qs.

V. Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной x_q - переменную x_s;

б) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 - против "своей" основной переменной, 0 - против "чужой" основной переменной, 0 - в последней строке для всех основных переменных;

в) новую строку с номером q получаем из старой делением на разрешающий элемент a_qs;

г) все остальные элементы a'_ij вычисляем по правилу прямоугольника (рис. 10):

Рисунок 10. Правило прямоугольника

Далее переходим к п. III алгоритма.

Таблица 1

Базис	Свободный член	Переменные	Оценочные отношения
x1	b1	x1	x2	x3	…	xn+m
x2	b2	a11	…	…	…	a(n+m)1
x3	b3	a21
…	…	…
xr	br	ar1				a(n+m)r
Fmax	с	c1	c2	c3	…	с(n+m)

Замечание. При решении задачи на отыскание минимума линейной функции цели рекомендуется вместо Z_min, находить (-Z)_max.

Примечания к симплекс-методу:

1. Если в разрешающем столбце нет ни одного строго положительного элемента, то задача не имеет оптимального решения, а целевая функция неограниченна снизу (в задаче на минимум) или сверху (в задаче на максимум).

2. Если в последней (оптимальной) таблице оценка какой-либо небазисной переменной равна нулю, то задача имеет бесконечное множество оптимальных решений.

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

4. На каждой итерации целевая функция убывает (в задаче на минимум) и возрастает (в задаче на максимум), однако максимальность оценки разрешающего столбца ведет к сокращению числа итераций; это свойство нарушается только в случае зацикливания.

5. Дополнительные переменные со знаком «+» (вводимые для преобразования неравенств вида ) можно использовать в качестве базисных переменных, а дополнительные переменные со знаком «-» - нет.

6. Структуру симплекс-таблицы можно упростить, если на каждой итерации исключать из таблицы столбики базисных переменных.

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

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

2.4 Нелинейное программирование

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

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

Найти переменные x₁, x₂, … , x_n, удовлетворяющие системе уравнений

и обращающие в максимум (минимум) целевую функцию

Z=f (x₁. x₂, … ,x_n).

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

Примером типичной и простой нелинейной задачи является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве x₁ и x₂ соответственно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а величины x₁ и x₂ - затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это "труд" и "машины", то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое). В сельском хозяйстве взаимозаменяемыми факторами могут быть посевные площади или минеральные удобрения (экстенсивный или интенсивный метод производства).

Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства Z=f(x₁, x₂). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (x₁ и x₂) и от цен этих факторов (c₁ и c₂). Совокупные издержки выражаются формулой b = c₁x₁+c₂x₂. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z. Математическая модель этой задачи имеет вид:

Определить такие переменные x₁ и x₂ удовлетворяющие условиям

c₁x₁+c₂x₂ = b, x₁,x₂ 0,

при которых функция

Z = f (x₁,x₂) достигает максимума.

Как правило, такая функция может иметь произвольный нелинейный вид.

Перечислим свойства задач нелинейного программирования, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования Конюховский П. В. Математические методы исследования операций в экономике. - СПб: Питер, 2000. - 208 с.:

1. Множество допустимых планов X может иметь очень сложную структуру (например, быть невыпуклым или несвязным).

2. Глобальный максимум (минимум) может достигаться как внутри множества X, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

3. Целевая функция Z может быть недифференцируемой, что затрудняет применение классических методов математического анализа.

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

2.4.1 Выпуклое программирование

Рассмотрим методы решения оптимизационных задача для выпуклых функций.

Множество точек называется выпуклым, если оно вместе с любыми своими двумя точками содержит и весь отрезок, соединяющий эти точки. Если [а,b] -- отрезок на числовой прямой и х[а,b], то

или

(4.1)

Нетрудно видеть и обратное: если выполняется (4.1), то х[а,b]. Таким образом, отрезок [а,b] можно определить как множество всех точек х, удовлетворяющих условию (4.1). Тогда выпуклое множество - это множество, которое вместе с любой парой своих точек a, b содержит и все точки x, для которых выполняется (4.1). Эти определения отрезка и выпуклого множества сохраняются для случая, когда а, b, x -- точки n-мерного пространства (где операции в равенстве (5.1), выполняются покоординатно).

Исходя из равенства (4.1), можно показать, что если М - выпуклое пространство, то для любых точек и любых действительных чисел t_i 0, удовлетворяющих условию

Функция F(X) = F(x₁,…,x_n), определенная на выпуклом множестве М n-мерного пространства, называется выпуклой на этом множестве, если

(4.2)

для любых точек X₁, X₂M и любого числа

Рисунок 11. Выпуклая функция одной переменной

Если в условии (4.1) изменить знак неравенства на , то получим определение вогнутой функции. Если же в условии (4.2) неравенство выполняется как строгое, то функция называется строго выпуклой (или строго вогнутой).

Рассмотрим алгебраические и аналитические свойства выпуклых функций:

1. Если функция F (X) выпукла, то функция -F(X) вогнута.

2. Функция F(X) = С и линейная функция F(X) = аХ + b являются всюду выпуклыми и всюду вогнутыми.

3. Если функции F_i (X), , выпуклы, то при любых действительных числах функция также является выпуклой.

4. Если функция F(X) выпукла, то для любого числа область решений неравенства F(X) < является либо выпуклым множеством, либо пустым.

5. Если функции выпуклые при всех неотрицательных значениях переменных, то область решений системы неравенств является выпуклым множеством (если она не пуста).

6. Выпуклая (вогнутая) функция, определенная на выпуклом множестве М, непрерывна в каждой внутренней точке этого множества.

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

8. Дважды дифференцируемая функция F(X) = F(x₁, x₂, …, x_n) является выпуклой в том и только в том случае, когда для любых и не обращающихся в нуль одновременно.

Достаточным условием выпуклости Конюховский П. В. Математические методы исследования операций в экономике. - СПб: Питер, 2000. - 208 с. функции является положительная определенность матрицы

называемой также матрицей Гессе, во всех точках xX. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе. В частности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства .

2.4.1.1 Постановка задачи выпуклого программирования

Пусть дана система неравенств вида

(4.3) и функция

Z = f (x₁, x₂, …, x_n), (4.4)

причем все функции является выпуклыми на некотором выпуклом множестве M, а функция Z либо выпукла на множестве М, либо вогнута.

Задача выпуклого программирования состоит в отыскании такого решения системы ограничений (4.3), при котором целевая функция Z достигает минимального значения, или вогнутая функция Z достигает максимального значения. (Условия неотрицательности переменных можно считать включенными в систему (4.3)).

Ввиду свойства 3⁰ всякая задача линейного программирования является частным случаем задачи выпуклого программирования. В общем случае задачи выпуклого программирования являются задачами нелинейного программирования. Выделение задач выпуклого программирования в специальный класс объясняется экстремальными свойствами выпуклых функций: всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным; кроме того, ввиду свойства 2⁰ выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума. Отсюда вытекает, что если целевая функция Z является строго выпуклой (строго вогнутой) и если область решений системы ограничений не пуста и ограничена, то задача выпуклого программирования всегда имеет единственное решение.

Функция F(X) = F(x₁, x₂, …, x_n) называется сепарабельной, если ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. если

(4.5)

(не исключено, что F_i(x_i) = 0 при некоторых i).

Пусть в задаче выпуклого программирования заданы система ограничений (4.3) и целевая функция (4.4), при этом и функция цели Z, и все ограничения , являются сепарабельными. Тогда задача имеет вид:

Найти минимум выпуклой (максимум -- вогнутой) функции

Z =

при ограничениях

(4.6)

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

Рисунок 12. Решение задачи выпуклого программирование методом кусочно-линейной аппроксимации

Для построения приближенной задачи рассмотрим кусочно-линейную аппроксимацию функции одной переменной h(х), заданной на отрезке [0, а]. Разобьем этот отрезок на r частей точками x₀<x₁<…<x_r так, чтобы х₀ = 0, х_r = а (рис. 12). Вычислим значения функции h_k(x) (k = 0, ..., r) в этих точках. Соединим попарно точки (x_k;h_k) и (x_k+1;h_k+1) отрезками прямых. Состоящая из этих отрезков ломаная аппроксимирует функцию h(x) на отрезке [0, а]. (Не рассматривая здесь оценку точности приближения, отметим только, что точность можно увеличить за счет более мелкого разбиения отрезка).

Уравнение участка ломаной между точками (x_k; h_k) и (x_k+1; h_k+1) имеет вид (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через , то получим:

 (4.7)

причем

Отметим, что для каждого существует единственное значение , удовлетворяющее условиям (4.7). Обозначив можно переписать (4.7) в виде:

(4.8)

где

[Уравнения (4.8) называются параметрическими уравнениями отрезка.

Если h(x) = 0, то второе из этих уравнений обращается в тождество 0 = 0, а первое принимает вид (4.1) - уравнение отрезка, лежащего на оси абсцисс].

Таким образом, для любого уравнение ломаной можно записать в виде:

(4.9)

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

Возвращаясь к задаче выпуклого программирования с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x_j. Затем каждый этот интервал разбивается на части точками x_jk и с использованием формул (4.9) строится кусочно-линейная аппроксимация для функций f_j и. После этого можно для исходной задачи (4.6) записать приближенную задачу:

Найти максимум функции

при ограничениях (4.10)

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

Отличие полученной задачи (4.10) от обычной задачи линейного программирования состоит в том, что для каждого x_j имеется не более двух соседних ненулевых и, значит, нельзя брать в качестве основных переменных два с одинаковым j и несоседними k. Заметим также, что для условий неотрицательности переменных слагаемых f_j(x_j) и (если таковые окажутся) кусочно-линейную аппроксимацию проводить, конечно, не нужно.

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