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

· ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».

· ограничения типа «=» дополняются одной вспомогательной переменной.

Соответственно, будет  создано некоторое количество дополнительных и вспомогательных переменных. В  исходный базис выбираются дополнительные переменные с коэффициентом «+1»  и все вспомогательные.

Осторожно: решение, которому соответствует этот базис, не является допустимым.

3.3 Различия между дополнительными и вспомогательными переменными

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

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

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

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

3.4 Фазы решения

После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как y_i, i∈{1., k}, то вспомогательную функцию определим, как

 

.

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

Когда будет найдено  оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:

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

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

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

 

 

4. Модифицированный симплекс-метод

 

В модифицированном методе матрица

 

 

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

1. Вычисляем двойственные переменные

2. Проверка оптимальности преобразуется в .

Проверка заключается  в вычислении  для всех столбцов . Столбец со значением < 0 можно вводить в базис.

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

Чаще выбирают значение, меньшее некоторого заданного значения

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

3. Определение выводимого.

Пусть   - вводимый столбец, соответствующий переменной   Базиный план - это решение системы   Увеличиваем  .

Умножим слева на  , т.е.  .

Здесь   - базисный план,   - разложение вводимого столбца по базису.

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

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный  план по уже приведенной  формуле       с найденным значением  .

5 . Пересчитываем обратную к базисной  .

Пусть   - выводимый столбец.

Матрица B представима в виде 

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

После замены столбца  базисная матрица будет иметь  вид 

Нам нужно найти матрицу  , такую что

 =>   =>   =>

Откуда  

 

Замечание.

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

4.1 Мультипликативный вариант симплекс-метода

 

В мультипликативном  варианте матрица  не хранится, хранятся лишь множители  

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

 

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

При подавляющем числе  ограничений типа «неравенство»  может быть использован метод переменного базиса.

Метод основан на том, что базисная матрица может быть представлена в виде:

 

 

Обратная к ней имеет  вид:

 

 

При относительно небольших  размерах матрицы  остальная часть матрицы может не храниться.

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

5.1 Двойственный симплекс-метод

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

 

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

 

.

 

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

 

5.2 Теорема двойственности.

Пусть рассматривается пара двойственных задач:

 

 

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

 

Так как данная таблица, по предположению, соответствует оптимальному решению задачи (7.1), то      и     .  
При этом Q= q₀ достигается при y₁=....=y_s = x_s+1=...=x_n=0. 
          Рассмотрим полученную таблицу двойственной задачи. Полагая значения переменных слева (небазисных) равными нулю: 
, 
найдем, 
u₁=q₁≥0, ..., u_s=q_s≥0,  , ...,  .  
 
Следовательно, получено опорное решение 
u₁=q₁, ..., u_s=q_s, u_s+1=₀, ..., u_m=0. 
Из последнего столбца находим, что 
 
и в точке           
значение W будет минимальным в силу того, что b_i,n+1≥0, 1,...,m. Следовательно, max Q = min W. 
          Пусть теперь линейная форма прямой задачи неограничена, т.е. для некоторой верхней переменной, например, y_s, соответствующий коэффициент q_s<0, а все коэффициенты этого столбца симплексной таблицы неположительны:  
b_1,s≤0, b_2,s≤0, ..., b_m,s≤0.  
           Тогда из таблицы для двойственной задачи: 
, 
то есть система ограничений двойственной задачи противоречива. Так как из неотрицательности   следует неположительность u_s (нельзя сделать ее положительной), то есть система несовместна.  
Теорема доказана.

 

 

Заключение

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

Существуют программные  реализации симплекс-метода. В настоящее  время появились интегрированные  математические программные системы  для научно-технических расчетов: Eureka, PCMatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.

Широкую известность  и заслуженную популярность приобрели  математические системы класса MathCAD, разработанные фирмой MathSoft (США). Это  единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков

 

 

 

 

 

 

 

 

 

 

Список используемой литературы: 

 

1. Зайченко Ю.П., Шумилова С.А.  Исследование операций.

2. Лищенко Линейное и нелинейное  программирование, М. 2003

3. А.Н. Карасев, Н.Ш. Кремер, Т.Н.  Савельева Математические методы  в экономике, М.2000

4. Орлов А.И. Теория принятия  решений. Учебное пособие. - М.: Издательство "Март", 2004

5. А.В.Кузнецов, Г.И.Новикова, И.И.Холод – «Сборник задач  по математическому программированию». Минск, Высшая школа, 1985г.

6. А.В.Кузнецов, Г.И.Новикова, И.И.Холод  – «Высшая математика. Математическое  программирование». Минск, Высшая  школа, 2001г.