Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

3. Решение методом симплекс-таблиц

   3.1. Приведение математической модели к каноническому виду
   3.2. Векторный анализ
   3.3. Метод искусственных переменных
   3.4. Построение симплекс-таблицы
   3.5. Анализ симплекс-таблицы
   3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц
   3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц

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

x1 + a1,m+1* xm+1 + ... + a1s* xs+...+ a1n* xn = b1;

...

x2 + a2,m+1* xm+1 + ... + a2s * xs+...+ a2n* xn = b2;

...

xm + am,m+1* xm+1 + ... + ams* xs+...+ amn* xn = bm.

Переменные x1, x2,...,xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (xm+1, ...,xn) называются небазисными переменными.

3.1. Приведение математической модели к каноническому виду

Приведем математическую модель задачи к каноническому виду.Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства эксклюзивно, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменых: при ">=" - переменная вводится в неравенство с коэффициентом +1; при "<=" - с коэффициентом (-1).

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

Также можно переориентировать целевую функцию с минимума на максимум или наоборот умножив все коэффициенты при переменных в этой функции на (-1).

3.2. Векторный анализ

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

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

3.3. Метод искусственных переменных

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

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

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

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

3.4. Построение симплекс-таблицы

Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. xi=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. xj = bj >=0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: S = cb* xb = c1* b1 + c2* b2+...+cm* bm. Заполняем первоначальную таблицу симплекс - метода:

 Таблица 2.3

cb xb c1 c2 ... cm cm+1 ... cn bi
  базис x1 x2 ... xm xm+1 ... xn  
с1 x1 1 0 ... 0 a1,m+1 ... an b1
с2 x2 0 1 ... 0 a2,m+1 ... a2n b2
... ... ... ... ... ... ... ... ... ...
cm xm 0 0 ... 1 am,m+1 ... amn bm
                  S

3.5. Анализ симплекс-таблицы

  1. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения

cj = cj - cb* Sj ,

где

сb - вектор оценок базисных переменных;

Sj - j-тый столбец в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

Таблица 2.4

cb xb c1 c2 ... cm cm+1 ... cn bi
  базис x1 x2 ... xm xm+1 ... xn
с1 x1 1 0 ... 0 a1,m+1 ... a1n b1
с2 x2 0 1 ... 0 a2,m+1 ... a2n b2
... ... ... ... ... ... ... ... ... ...
cm xm 0 0 ... 1 am,m+1 ... amn bm
c-строка 0 0 ... 0 ... W

3.      Если все оценки c<=0 (cj  >= 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

4.      Впротивном случае в базис необходимо ввести небазисную переменную xr с наибольшим значением cj вместо одной из базисных переменных (табл. 2.5).

  1. При помощи правила минимального отношения min(bi /air) определяем переменную xp, выводимую из базиса. Если коэффициент air отрицателен, то bi /air бесконечность . В результате пересечение столбца, где находится вводимая небазисная переменная xr и строки, где находится выводимая базисная переменная xp определит положение ведущего элемента таблицы (табл. 2.6).

Таблица 2.5

cb

xb

c1

c2

...

cm

cm+1

...

cr

...

cn

bi

 

базис

x1

x2

...

xm

xm+1

...

xr

...

xn

 

с1

x1

1

0

...

0

a1,m+1

...

a1r

...

a1n

b1

с2

x2

0

1

...

0

a2,m+1

...

a2r

...

a2n

b2

...

...

...

...

...

...

...

...

...

...

...

...

cm

xm

0

0

...

1

am,m+1

...

amr

...

amn

bm

c - строка

0

0

...

0

...

...

W

 

 

 

 

 

 

 

 

max

 

 

 

Таблица 2.6

cb

xb

c1

c2

...

cm

cm+1

...

cr

...

cn

bi

bi/

air

 

 

 

x1

x2

...

xm

xm+1

...

xr

...

xn

 

 

 

с1

x1

1

0

...

0

a1,m+1

...

a1r

...

a1n

b1

b1/a1r

 

с2

x2

0

1

...

0

a2,m+1

...

a2r

...

a2n

b2

b2/a2r

 

...

...

...

...

...

...

...

...

...

...

...

...

...

 

сp

xp

0

0

...

0

ap,m+1

...

apr

...

apn

bp

bp/apr

min

...

...

...

...

...

...

...

...

...

...

...

...

...

 

cm

xm

0

0

...

1

am,m+1

...

amr

...

amn

bm

bm/anr

 

c -стро-ка

0

0

...

0

...

...

W

 

 

 

 

 

 

 

 

 

 

max

 

 

 

 

 

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

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

Далее: 3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц


Далее: 3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц

Далее: 4. Целочисленное линейное программирование - метод отсечений Гомори

Вернуться в Начало

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх