Методы линейного программирования

            

принимает максимальное значение при ограничениях:

           

Методы  целочисленной оптимизации можно  разделить на три основные группы:

1. Методы отсечения;

2. Комбинаторные методы;

3. Приближенные методы. 

1. Методы отсечения  Гомори.

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

• оно должно быть линейным;
• должно отсекать найденный оптимальный нецелочисленный план;
• не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости  добавляется еще одно ограничение и т.д.

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

Алгоритм:

1. Задача оптимизации решается симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
2. Если среди компонент оптимального решения есть нецелые, то выбирают компоненту с наибольшей целой частью и по соответствующему уравнению системы ограничений формируется правильное отсечение:

                  

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

                 

     и включить его в систему ограничений.

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

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

2. Комбинаторные  методы.

Наиболее известным  комбинаторным методом является метод ветвей и границ.

Впервые метод  ветвей и границ был предложен  в работе Лэнд и Дойг в 1960 г. применительно  к задаче линейного целочисленного программирования. Второе рождение метода связано с работой Литтла, Мурти, Суини и Кэрел, 1963 г., посвященной  задаче о коммивояжере.

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

3. Приближенные методы.

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

Задача  линейного программирования 

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

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

В самом  общем виде задача математически  записывается так:

U = f(x) ® max; x Î w,

где x = (x₁, x₂,…, x_n);

w – область допустимых значений переменных x₁, x₂,…, x_n;

f(x) – целевая функция. 

Для того чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать x* Î w такое, что f(x*) ³ f(x), при любом x Î w, или для случая минимизации - что f(x*) ≤ f(x), при любом x Î w.

Оптимизационная задача является неразрешимой, если она  не имеет оптимального решения. В  частности, задача максимизации будет  неразрешима, если целевая функция f(x) не ограничена сверху на допустимом множестве w.

Методы  решения оптимизационных задач  зависят как от вида целевой функции f(x), так и от строения допустимого множества w. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

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

• задачи линейного программирования, если f(x) и w линейны;
• задачи целочисленного программирования, если ставится условие целочисленности переменных x₁, x₂,…, x_n;
• задачи нелинейного программирования, если форма f(x) носит нелинейный характер.

 

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

 ,

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

,

.  

Функция F(x) называется целевой функцией (или линейной формой) задачи.

Любое решение системы ограничений  называется допустимым решением задачи.

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

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

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

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

     2) если в ограничениях правая  часть отрицательна, то следует  умножить это ограничение на -1;

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

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

где x_k – свободный индекс, . 

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

    Понятие критерия оптимальности 

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

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

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

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

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

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

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

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

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

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