Решение задачи линейного
программирования симплекс-методом
Ладовер Татьяна Михайловна
Новороссийский колледж строительства и экономики



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

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

Общий вид записи модели ЗЛП:


            f(X) = c₁x₁ + c₂x₂+ … +c_nx_n → extrem


при условиях-ограничениях:

   a₁₁x₁ + a₁₂x₂ + … +a_1nx_n ≤ b₁
  a₂₁x₁+ a₂₂x₂ + … +a_2nx_n ≤ b₂

  .

  .

a_m1x₁ + a_m2x₂ + … +a_mnx_n≤b_m,

где

x_i ≥ 0, i = 1 ÷ n – искомые величины,
a_ij, b_j, c_i– заданные постоянные величины,
b_j - запасы сырья, энергии и т.д., j= 1 ÷ m.


Совокупность чисел Х= (х₁, х₂, х₃, ..  х_n), удовлетворяющих ограничениям
задачи, называется допустимым решением или планом или областью допустимых
решений (ОДР).

Допустимое решение, максимизирующее или минимизирующее целевую функцию, называется оптимальным решением или оптимальным планом.

Решить ЗЛП в частном случае при наличии двух переменных можно графическим методом.
Если в ЗЛП более двух переменных, то самым распространённым методом решения является симплекс-метод.
Симплексом называется выражение вида
           c₁x₁ + c₂x₂ + …+ c_nx_n 
или сумма парных произведений векторов

Методика решения задач с f(x)→ min отличается от методики решения задач c f(x)→ max. Для удобства решения задач обоих типов по единому алгоритму их модели необходимо привести к т.н. канонической форме (КФ).

Считается, что ЗЛП записана в канонической форме, если:
a) её целевая функция максимизируется;
b) ограничения задачи имеют вид равенства с неотрицательной правой частью (b_j ≥ 0);
c) все переменные в модели задачи неотрицательные (≥ 0).


Таким образом, каноническая форма модели ЗЛП имеет вид:

f(x) = c₁x₁ + c₂x₂ + …+ c_nx_n  → max

a₁₁x₁+ a₁₂x₂ + …+ a_1nx_n = b₁
a₂₁x₁+ a₂₂x₂ + …+ a_2nx_n = b₂  
.

a_m1x₁+ a_m2x₂ + …+ a_mnx_n = b_m

x_i  ≥ 0, i = 1 ÷ n
b_j≥ 0, j = 1 ÷ m

Рассмотрим два типа математических моделей ЗЛП.
I.                  
Приведём к КФ ЗЛП, заданную моделью, в которой все ограничения вида ≤:

f(x) = c₁x₁+ c₂x₂ + …+ c_nx_n  → max
                 a₁₁x₁ + a₁₂x₂+ …+ a_1nx_n ≤ b₁
(*)             a₂₁x₁ + a₂₂x₂+ …+ a_2nx_n ≤ b₂
                 .
                 .        
                a_m1x₁+ a_m2x₂ + …+ a_mnx_n ≤ b_m

                 x_i  ≥ 0, i = 1 ÷ n
                 b_j≥ 0, j = 1 ÷ m


Во всех неравенствах системы ограничений  левая часть меньше либо равна правой (≤). Для того чтобы уравнять их (как того требует каноническая форма), необходимо к левой части каждого ограничения прибавить, соответственно, неотрицательные целые переменные x_n+1, x_n+2,…, x_n+m.  Чтобы не изменилось значение целевой функции, эти переменные вводятся в неё с нулевыми коэффициентами.
Т.о. после приведения к канонической форме наша
задача будет иметь вид:

f(x) = c₁x₁ + c₂x₂ + …+ c_nx_n + 0* x_n+1  + 0* x_n+2 … +0* x_n+m  → max
  a₁₁x₁+ a₁₂x₂ + …+ a_1nx_n  + x_n+1 = b₁
  a₂₁x₁+ a₂₂x₂ + …+ a_2nx_n  + x_n+2 = b₂
  ·
  ·
  a_m1x₁+ a_m2x₂ + …+ a_mnx_n  + x_n+m = b_m

  x_i ≥ 0, i = 1 ÷ n+m
  b_j≥ 0, j = 1 ÷ m

Переменные x_n+1 ÷   x_n+m  называются дополнительными.

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

Пример1.

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

f(x) = 10x₁ +13x₂ → max

      6x₁+ 5x₂ ≤ 30
      4x₁ + 8x₂ ≤ 32
      2x₁ + 4x₂ ≤ 12

      х_i ≥ 0, i = 1 ÷
 

Приведём эту математическую модель к КФ:

f(x) = 10x₁ +13x₂ + 0* x₃   + 0*x₄   + 0* x₅  → max
                 6x₁+ 5x₂ + x₃  = 30
(*)             4x₁ + 8x₂ + x₄  = 32
                 2x₁ + 4x₂ + x₅  = 12
                x_i  ≥0, i = 1 ÷ 5.

II.            
Рассмотрим второй частный случай: f(x)→min и хотя бы одно из ограничений вида ≥ (или даже все). Модель этой задачи имеет вид:

f(x) = c₁x₁+ c₂x₂ + …+ c_nx_n  → min

                 a₁₁x₁ + a₁₂x₂+ …+ a_1nx_n ≥ b₁
(**)           a₂₁x₁ + a₂₂x₂+ …+ a_2nx_n ≥ b₂
                 ·
                 ·
                 a_m1x₁+ a_m2x₂ + …+ a_mnx_n ≥ b_m

                x_i  ≥0, i = 1 ÷ n
                b_j≥ 0, j = 1 ÷ m

Определение минимального значения функции f(x) можно свести к нахождению максимального значения функции -f(x).
Т.о. в подобных случаях коэффициенты при неизвестных в f(x) → min надо умножить на (-1).
Чтобы привести к строгому равенству ограничения вида ≥, надо из левой части каждого ограничения такого вида вычесть, соответственно, неотрицательные целые переменные x_n+1,  x_{n+2, ….,}  x_n+m.
Тогда после приведения к КФ задача (**) будет иметь вид:

f(x) = -(c₁x₁ + c₂x₂ + …+ c_nx_n)  + 0* x_n+1  + 0* x_n+2 …+0* x_n+m  → max

a₁₁x₁+ a₁₂x₂ + …+ a_1nx_n  - x_n+1 = b₁
a₂₁x₁+ a₂₂x₂ + …+ a_2nx_n  - x_n+2 = b₂
·
·
a_m1x₁+ a_m2x₂ + …+ a_mnx_n  - x_n+m = b_m


x_i ≥ 0, i = 1 ÷ n+m
b_j≥ 0, j = 1 ÷ m.



Все переменные в математической модели делятся на два типа:


- базисные (зависимые), которые могут быть выражены через все остальные
переменные. Переменная является базисной, если она входит
только в одно из уравнений системы с коэффициентом равным 1 (так в системе (*)базисными являются переменные х₃, х₄, х₅).
- все остальные переменные являются небазисными (независимыми).

 Частное решение, т.е. нахождение базисных переменных при приравнивании небазисных переменных нулю (х_i= 0), называется базисным. Базисное решение называется вырожденным, если хотя бы одна из базисных переменных = 0, такая задача называется вырожденной. В противном случае - задача называется невырожденной.


Выше мы рассмотрели два частных случая I и II.
В  случае I базисное решение является допустимым решением:

x_n+1 = b₁
x_n+2 = b₂
·
x_n+m= b_m .


Во II-м случае (см. КФ модели (**)) базисное решение имеет вид
- x_n+1 = b₁
- x_n+2 = b₂
.
.
- x_n+m= b_m       

и не является допустимым, т.к. противоречит условию неотрицательности переменных (x_i ≥ 0).


 В таких случаях для выделения базисных переменных и нахождения допустимого решения используют метод искусственного базиса, заключающийся в следующем:
₁₎ в каждое ограничение вида ≥ или = вводят искусственную неотрицательную переменную у₁, у₂,… у_m;
2) в целевую функцию искусственные переменные входят с коэффициентом (-М), где М – очень большое положительное число (отсюда  и название - М-метод).

После ввода искусственных переменных КФ задачи (**) будет иметь вид:


f(x)= -(c₁x₁+ c₂x₂+ …+c_nx_n) + 0* x_n+1 + 0* x_n+2 …+ 0* x_n+m– М*у₁ …–М*у_m → max
a₁₁x₁+ a₁₂x₂ + …+ a_1nx_n  - x_n+1 + у₁ = b₁
a₂₁x₁+ a₂₂x₂ + …+ a_2nx_n  - x_n+2 + у₂ = b₂
·
·
a_m1x₁+ a_m2x₂ + …+ a_mnx_n  - x_n+m + у_m = b_m

x_i  ≥0, i = 1 ÷ n+m,
b_j ≥ 0,
y_j ≥ 0, j = 1 ÷ m


Набор искусственных переменных у₁, у₂,…,у_m  в М-методе образует искусственный базис. Искусственные переменные вводятся только для получения исходного базисного плана при решении задач ЛП симплекс-методом. Решение ЗЛП удобно производить в т.н. симплекс-таблицах следующего вида:




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

Алгоритм решения ЗЛП симплекс-методом

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

2. – если все относительные
оценки неотрицательные и среди базисных переменных нет искусственных, то план
оптимален, т.е. задача решена. Решение находим в столбце В:

x_n+1 = b₁
x_n+2 = b₂
·
x_n+m= b_m ;

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

- если все относительные оценки неотрицательные, но среди базисных переменных есть искусственные, то задача решений не имеет;

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


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

Далее необходимо произвести перерасчёт таблицы.


4. В новой таблице переменные главной строки и главного столбца (вместе со своими коэффициентами) меняются местами. Остальные переменные и их коэффициенты переписываются без изменений.
Вместо главного элемента записывается обратное ему число: 1/главный элемент.
Элементы главного столбца старой таблицы делят на (- главный элемент).
Элементы главной строки старой таблицы делят на (главный элемент).
Все остальные элементы пересчитывают по правилу прямоугольника:
из произведения элементов главной диагонали, проходящей через главный элемент, вычитают произведение элементов побочной диагонали и результат делят на главный элемент; получившееся число записывают в соответствующую клетку новой симплекс-таблицы. Если в главной строке или главном столбце есть нули, то
элементы соответствующих этим нулям столбца и строки переписываются без
изменения в новую таблицу.


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



Пример 2.
Решим следующую задачу симплекс-методом.


Мастер делает мельхиоровые ложки двух видов: без чеканки (Л1) по цене 2 евро и с чеканкой (Л2) по цене 3 евро. За день мастер делает не менее одной ложки. Дневной запас сырья не более 12 дм³: при этом на ложку вида Л1 идёт 3 дм³, а на ложку вида Л2 - 2 дм³ мельхиора.
На какой максимальный доход в день может рассчитывать мастер при соблюдении указанных норм?

Обозначим:
  x₁ – количество ложек вида Л1_,
  x₂ – количество ложек вида Л2_.

По условию задачи составим её математическую модель:
доход от продажи ложек вида Л1 составит 2*x₁ (евро);
доход от продажи ложек вида Л2 составит 3*x₁ (евро). Сумма этих чисел равна доходу мастера - целевая функция.
На производство ложек вида Л1 расходуется 3*x₁ дм^{3 м}  мельхиора, а на производство ложек вида Л2 расходуется 2*x₁ дм^{3 м} , причем мастер не может использовать в день больше 12  дм^{3 м} - это первое ограничение. Из условия, что мастер в день делает не менее одной ложки, запишем второе ограничение и получим модель задачи:

f(X) = 2x₁ + 3x₂ → max
3x₁+ 2x₂ ≤ 12
    x₁ +   x₂ ≥ 1
   
    х₁ ≥ 0
    х₂ ≥ 0

Для решения задачи симплекс-методом приведём математическую модель к канонической форме:

f(x) = 2x₁ + 3x₂ + 0* x₃ + 0* x₄ - М* у → max

3x₁ + 2x₂ + x₃ =12
  x₁ +   x₂ - x₄ + y =1
 
  x_i  ≥0, i = 1 ÷ 4
  y ≥ 0.

На основании канонической формы построим начальный базисный план задачи:


Задача не решена, т.к. в базисе есть искусственные переменные, а среди относительных оценок - отрицательные. Среди отрицательных относительных оценокmso-fareast-font-family:Calibri;mso-ansi-language:RU;mso-fareast-language:EN-US;
выбираем наибольшую по модулю (-М-3) - ей соответствует главный столбец; находим главную строку (вторая, т.к.1/1 Отрицательная относительная оценка одна (-3), ей соответствует главный столбец; главная строка  - первая, соответственно, главный элемент равен двум (ячейка выделена голубым цветом). Выполнив перерасчёт таблицы, перейдём к новому базисному плану.



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


Решение:
X1 = 0 (т.к. эта переменная не вышла в базис), в базис вышла X2 = 6, максимальный доход при таком плане выпуска изделий равен

f(X) = 2*0 + 3*6 = 18 (евро).


Список рекомендуемой литературы


1   Кремер Н.Ш.,Путко Б.А. и др. Под ред. проф. Кремера Н.Ш. Исследование операций в экономике.– М: ЮНИТИ, 2002.- 407 с.

2      Малик Г.С. Основы экономики и математические методы в планировании/ – М.: Высшая школа, 1988.-
279 с.

3     Миркин Б.Г., Фаенсон А.И. Экономико-математические методы в планировании
жилищно-коммунального хозяйства./ – М: Стройиздат,1990. – 137 с.

4      Палий И.А. Линейное программирование/ - М: ЭКСМО, 2008. – 255 с.

Татьяна Михайловна! Здравствуйте!
Удачного Вам дня!
Ваша работа достойна внимания!
Показал своим преподавателям...
Вам -