Рассмотрение симплексного метода при решении задач линейного программирования и разработка приложения в среде Delphi для ее решения

Пусть ЗЛП представлена в  следующей записи:

                                                        (14)

                                        (15)

                                            (16)

Чтобы задача (14) – (16) имела решение, система ее ограничений (15) должна быть совместной. Это возможно, если ранг r системы (число линейно независимых уравнений) не больше числа неизвестных n (r n). При r = n система имеет единственное решение, которое и будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл.

Выясним структуру координат  угловой точки многогранных решений. Пусть r < n. В этом случае система векторов содержит базис – максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть  несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП.

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

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

Теорема 3. Если система  векторов содержит m линейно независимых векторов , то допустимый план

является крайней  точкой многогранника планов.

Рассмотрим основную теорему  линейного программирования. Не сужая  область экономических приложений, ЗЛП с неограниченной областью планов формально можно свести к задаче с ограниченной областью введением  дополнительного ограничения , где М – большое положительное число.

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

 

 

2. Применение симплексного метода для решения ЗЛП.

1. Общая схема построения решения ЗЛП.

 

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

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

Симплекс метод – универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

Построение начального опорного плана. Пусть ЗЛП представлена системой ограничений в каноническом виде:

     .

Говорят, что ограничение  ЗЛП имеет предпочтительный вид, если при неотрицательности правой части ( ) левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения-равенства – с коэффициентом, равным нулю. Например, в системе ограничений

первое и второе ограничения  имеют предпочтительный вид, третье – нет.

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

  

предпочтительными (базисными) являются переменные х₂, х₃ и х₄, свободными х₁, х₅. Приравниваем свободные переменные х₁ и х₅ нулю, тогда базисные переменные примут значения х₂ = 10, х₃ = 80 и х₄ = 32. Имеем план х = (0; 10; 80; 32; 0). Если полученный план будет иметь не более m отличных от нуля координат, то, согласно теореме о структурах координат крайней точки, он будет опорным.

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

Пусть, далее, система ограничений  имеет вид

    .

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

    ,

которая имеет предпочтительный вид. И, следовательно, начальный опорный  план примет вид

В целевую функцию, как  отмечалось выше, дополнительные переменные вводятся с коэффициентами, равными  нулю:

  .

Пусть, далее, система ограничений  имеет вид

    .

Сведем ее к эквивалентной  вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

    .

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

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

Пусть исходная ЗЛП имеет  вид

                                               (17)

    ,                                        (18)

                                                      (19)

причём ни одно из ограничений  не имеет предпочтительной переменной. М-задача запишется так:

  ,                                     (20)

     ,                                         (21)

  ,   .                                     (22)

Задача (20) – (22) имеет предпочтительный вид. Её начальный опорный план имеет вид

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

Теорема 5. Если в оптимальном плане

                                    (23)

М-задачи (20) - (22) все искусственные переменные  , то план

                                                 (24)

является оптимальным планом исходной задачи (17) – (19).

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

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

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

Теорема 6. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности опорного плана. Любую ЗЛП, как было показано выше, можно представить в эквивалентном предпочтительном виде:

                                              (25)

    ,                           (26)

  .                                         (27)

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

  (28)

Введем обозначения:

                               (29)

  ,               (30)

где – вектор коэффициентов целевой функции при базисных переменных; – вектор-столбец свободных членов; – вектор-столбец коэффициентов при переменных .

С учетом равенств (28) – (30) задача (25) – (27) примет вид:

                                     (31)

    ,                           (32)

  .                                         (33)

 

Таблица 1

БП
			1       0         0           0                           0       1         0           0                             0       0         1           0                              0       0         0           1
			0       0       0            0

где

     .

Задачу (31) – (33) записывают в  таблицу, которая называется симплексной  (табл. 1). Последнюю, (m + 1)-ю, строку называют индексной строкой (строкой целевой функции), число – значение целевой функции для начального опорного плана , то есть . Числа    называются оценками свободных переменных.

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

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