Лекция 5. Симплекс-метод решения задач линейной оптимизации

МЕТОДА

План

1. Приведение задач ЛП к каноническому виду.

2. Различные формы задачи ЛП.

3. Общие сведения о симплексном методе решения задач ЛП.

1. Из геометрической интерпретации задачи линейной оптимизации видно, что максимум или минимум целевой функции достигается в угловой точке выпук- лого многогранника – ОДР. Поэтому в основу симплекс-метода положена идея рассмотрения и испытания на оптимальность только угловых точек – вершин многогранника. Сформулируем теоретические факты, на которых базируется симплекс-метод.

Для решения задач ЛП симплекс-методом необходимо, чтобы задача бы-

ла записана в каноническом виде.

Канонический вид задачи ЛП:

1) Z → min;

2) Система ограничений содержит только равенства;

3) Правые части ограничений – неотрицательные числа;

4) Все переменные задачи – неотрицательные.

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

Z = −16 x 1− x 2 + x 3 + 5 x 4 + 5 x 5 → min,

⎨ 1 2

⎧2 x 1+ x 2 + x 3

⎪−2 x + 3 x

+ x 4

=10

= 6

⎩ 1 2

⎪2 x + 4 x

− x 5 = 8

x j ≥ 0 (j =1, 5).

Любая задача ЛП может быть приведена к каноническому виду.

Пример 2. Привести задачу ЛП к каноническому виду:

Z = −5 x 1− 3 x 2 + 2 x 3 + 9 → max,

⎧3 x 1+ x 2 + x 3 ≥ −7

⎪

⎩ 1

⎨2 x 1+ 3 x 2 + x 4 =1

⎪ x ≥ 6

x 1 ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0.

Решение. Запишем задачу в более удобном виде:

Z = −5 x 1− 3 x 2 + 2 x 3 + 9 → max,

⎧3 x 1+ x 2 + x 3

⎪

≥ −7

x

⎨2 x 1+ 3 x 2

⎪

⎩ 1

+ x 4 =1

≥ 6

x 1 ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0.

Задача ЛП не удовлетворяет ни одному из условий 1)-4) канонического вида. Поменяем знак правой части первого ограничения на противоположный, выполняя условие 3):

Z = −5 x 1− 3 x 2 + 2 x 3 + 9 → max,

⎧−3 x 1 − x 2 − x 3 ≤ 7

⎪

x

⎨2 x 1 + 3 x 2

⎪

⎩ 1

+ x 4 =1

≥ 6

x 1 ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0.

Не выполняется условие 4) о каноническом виде, т.к. переменная

x 2 мо-

жет быть числом произвольного знака. Любое действительное число может

быть представлено разностью неотрицательных чисел: 5 = 7 − 2, 0 = 3 − 3,

−4 = 6 −10. Поэтому делаем замену x

= x / − x //, где

x / ≥ 0 и

x // ≥ 0. Записы-

ваем задачу ЛП:

2 2 2 2 2

/ / //

Z = −5 x 1− 3 x 2

+ 3 x 2

+ 2 x 3 + 9 → max,

⎧−3 x

− x / + x

// − x ≤ 7

1 2 2 3

⎪

2 x + 3 x

/ − 3 x //

+ x =1

⎨

⎪ x

⎪⎩1

1 2 2 4

≥ 6

x

x

x 1 ≥ 0,

/ ≥ 0,

// ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0.

Не выполняется условие 1). Делаем замену

// / //

Z // = − Z /:

Z = 5 x 1 + 3 x 2

− 3 x 2

− 2 x 3 − 9 → min,

⎧−3 x

− x / + x

// − x ≤ 7

1 2 2 3

⎪

2 x + 3 x

/ − 3 x //

+ x =1

⎨

⎪ x

⎪⎩1

1 2 2 4

≥ 6

x

x

x 1 ≥ 0,

/ ≥ 0,

// ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0.

Осталось выполнить только условие 2). Добавляем в первое и третье ог-

///

раничения балансовые переменные

x 5 и

x 6. Новая целевая функция

Z будет

содержать эти переменные с коэффициентом 0.

Заметим, что начальная целевая функция Z не содержала переменную

x 4. Значит, эта переменная входит во все целевые функции данного примера с коэффициентом 0.

Записываем задачу ЛП в каноническом виде:

/// / //

Z = 5 x 1 + 3 x 2

− 3 x 2

− 2 x 3 + 0 ⋅ x 4 + 0 ⋅ x 5 + 0 ⋅ x 6 − 9 → min,

⎧−3 x

− x / + x

// − x

+ x = 7

1 2 2 3 5

⎪

2 x + 3 x

/ − 3 x // + x =1

⎨

⎪ x

⎪⎩1

1 2 2 4

− x 6 = 6

x

x 1 ≥ 0,

/ ≥ 0,

// ≥ 0,

x 3 ≥ 0,

x 4 ≥ 0,

x 5 ≥ 0,

x 6 ≥ 0.

2. Пусть задача ЛП записана в каноническом виде:

x

Z = c 1 x 1 + c 2 x 2 +⋅⋅⋅+ cnxn → min, (1)

+ a x + ⋅⋅⋅ + a x = b,

⎧ a 11 x 1+ a 12 x 2 +⋅⋅⋅+ a 1 n xn = b 1,

⎪

⎪ a 21 x 1 22 2 2 n n 2

⎨

⎪...............................................,

⎩⎪ am 1 x 1 + am 2 x 2 +⋅⋅⋅+ amn xn = bm.

(2)

xj ≥ 0 (j =1, n). (3)

Рассмотрим матрицу-столбец переменных, матрицу-столбец свободных

членов, матрицу коэффициентов при неизвестных, матрицу-строку коэффици-

ентов целевой функции:

⎛ x 1 ⎞

⎛ b 1 ⎞

⎛ a 11

a 12

...

a 1 n ⎞

⎜ ⎟ ⎜ ⎟ ⎜ ⎟

X = ⎜ x 2 ⎟,

B = ⎜ b 2 ⎟,

A = ⎜ a 21

a 22

...

a 2 n ⎟, C = (c c

...

c).

⎜... ⎟

⎜... ⎟

⎜............ ⎟

1 2 n

⎜ ⎟ ⎜ ⎟ ⎜ ⎟

⎝ xn ⎠

⎝ bm ⎠

⎝ am 1

am 2

...

amn ⎠

	Z = CX → min,	(4)
AX = B,	(5)
X ≥0.		(6)

Тогда каноническая задача ЛП (1)-(3) может быть записана в матричной форме:

Матрицу, JсJGостJоGящJGую из одного столбца или строки, JмJGожно представлять

как вектор, т.е. X, B, C. Введём дополнительно векторы Aj

(j =1, n), коорди-

наты которых – это j -е столбцы матрицы A. Тогда задача ЛП представима в

векторной форме:

G JG

J Z JG= C ⋅ X JJG→min,

JJG JG

(7)

JJG

A 1 ⋅ x 1 + A 2 ⋅ x 2 +...+ An ⋅ xn = B, (8)

X ≥0.

JJG

(9)

Планом задачи (допустимым решением) называют вектор X, удовле-

творяющий условиям (2)-(3) или (5)-(6) или (8)-(9). Оптимальный план – это план, минимизирующий целевую функцию.

РасJGсмотрим вектоJрJGную форму (7)-(9). Уравнение (8) – это разложение

вектора B

по векторам Aj

(j =1, n) с коэффициентами разложения

JG

x j.

Напомним, что система векторов Aj

(j =1, n) называется линейно неза-

висимой, если равенство

JJG JJG JJG G

A 1 ⋅ µ1 + A 2 ⋅ µ2 +...+ An ⋅µ n = 0

выполняется только при одновременном равенстве нулю коэффициентов раз-

ложения, т.е.

µ1 = µ2 =... = µ n =0. В противном случае векторы называют линейно

зависимыми.

Если векторы

JJG

Aj, входящие в разложение (8) с положительными коэф-

JJG

фициентами

x j, являются линейно независимыми, то вектор X

JG

называют

опорным планом. А т.к. векторы Aj

имеют m координат, то количество

x j > 0

в опорном плане не может превышать число m.

Опорный план называют невырожденным, если он содержит m положи-

тельных компонент

x j. В противном случае он – вырожденный. Если все воз-

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

3. Рассмотрим некоторые свойства задачи ЛП.

Теорема 1. Множество всех планов задачи ЛП выпукло.

В общем случае ОДР либо пустая, либо является выпуклым многогран-

ным множеством.

Теорема 2. Пусть ОДР представляет собой выпуклый ограниченный мно-

гогранник в пространстве

Rn. Тогда целевая функция принимает своё мини-

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

Каноническая задача ЛП в векторной форме (7)-(9) имеет свои специфи-

ческие особенности.

Теорема 3. Если векторы

JGJJG JJG

A 1, A 2,..., Ak

являются линейно независимыми и

имеет место разложение

JJG JJG JJG JG

A 1 ⋅ x 1 + A 2 ⋅ x 2 +...+ Ak ⋅ xk = B,

n

где все

x j ≥ 0, то точка

X = (x 1, x 2,..., xk,0,0,...,0)∈ R

будет угловой точкой ОДР.

JJG

Теорема 4. Если

X =(x 1, x 2,..., xn) является угловой точкой ОДР, то векторы

Aj из разложения (8), соответствующие положительным коэффициентам

x j,

образуют линейно независимую систему.

Следствие 1 (из теорем 3 и 4). Если в задаче (7)-(9) векторы

JJG

Aj

имеют m

координат, то угловые точки ОДР

X =(x 1, x 2,..., xn)

содержат не более m положи-

тельных координат, а остальные равны нулю.

Решение задJJаGчJиJG

ЛПJJG(7)-(9) становится более удобным, если среди m -

мерных векторов

A 1, A 2,..., An

имеется m единичных векторов

JJG

⎛ 1 ⎞

⎜ ⎟

⎜ ⎟

JJG

⎛ 0 ⎞

⎜ ⎟

⎜ ⎟

JJG

⎛ 0 ⎞

⎜ ⎟

⎜ ⎟

A 1 = ⎜...⎟,

⎜ ⎟

⎝ ⎠

A 2 = ⎜...⎟,…,

⎜ ⎟

⎝ ⎠

Am = ⎜...⎟.

⎜ ⎟

⎝ ⎠

Т.к. эти векторы линейно независимы и их количество совпадает с размерно-

стью пространства, то данные векторы образуют базис пространства

Рассмотрим произвольный вектор из разложения (8):

⎛ a 1 j ⎞

⎜ ⎟

Rm.

JJG

⎜ a 2 j ⎟.

a

Aj = ⎜

... ⎟

⎜ ⎟

⎝ mj ⎠

Этому вектору соответствует переменная

JJG

x j и коэффициент c j

целевой функ-

ции. Вектор Aj

допускает единственное разложение в единичном базисе

JJG JJG JJG JJG

A 1 ⋅ a 1 j + A 2 ⋅ a 2 j +...+ Am ⋅ amj = Aj, (10)

которому соответствует единственное значение целевой функции

c 1 ⋅ a 1 j + c 1 ⋅ a 2 j +...+ cm ⋅ amj = zj. (11)

JG

Теорема 5. Пусть

X 1 =(x 1, x 2,..., xn)

является опорным планом задачи (7)-

(9). Если для некоторого вектора Aj

выполняется условие

zj − cj > 0, то данный

опорный план не будет оптимальным и можно построить другой опорный план

X 2, для которого

z (X 2) < z (X 1).

Заметим, что опорный план

X 2 является лучшим по сравнению с

X 1.

Критерий

zj − cj

из (10) и (11) называют оценками оптимальности. Если для

JJG

некоторого опорного плана разложения всех векторов Aj

(j =1, n) в данном ба-

зисе удовлетворяют условию

zj − cj ≤ 0, то данный план является оптимальным.

С учётом всего сказанного, симплексный метод – это метод последова-

тельного улучшения плана при решении задачи ЛП.

Симплекс-метод впервые предложил в 1947 г. американский математик

Дж. Данциг. Название метода происходит от английского слова «simple» – про-

стейший. Это связано с тем, что на начальном этапе развития метода, ОДР име-

ли простейший вид. Например, ОДР представляла собой пирамиду в простран-

стве

R 3 с вершинами

O (0; 0; 0),

A (1; 0; 0),

B (0;1; 0)

и C (0; 0;1). Эту пирамиду

иногда называют симплексом.

План

1. Пример решения задачи ЛП с помощью симплекс-метода.

2. Алгоритм симплекс-метода.

1. Рассмотрим решение конкретной задачи ЛП с помощью симплекс-метода.

Пример 1. Фирма выпускает два вида сухих строительных смесей по це-

не 4 тыс. грн. и 5 тыс. грн. за 1 т. Для производства используется три вида сы-

рья с запасами 15 т, 7 т, 12 т, соответственно. Изготовление тонны 1-й смеси требует 0,25 т сырья первого вида, 0,25 т сырья второго вида и 0,5 т сырья третьего вида. На производство тонны 2-й смеси требуется 0,6 т сырья первого вида, 0,2 т сырья второго вида и 0,2 т сырья третьего вида.

Табл. 1. Данные задачи

Сырьё	Продукция (расходы сырья на про- изводство 1 т смеси)	Запасы сырья
P 1	P 2
S 1 S 2 S 3	0,25 т 0,25 т 0,5 т	0,6 т 0,2 т 0,2 т	15 т 7 т 12 т
Цена за 1 т продукции	4 тыс. грн.	5 тыс. грн.
Количество продукции, т	x 1	x 2

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

ный.

Решение. Пусть

x 1 количество выпуска продукции первого вида,

x 2 –

второго вида, Z – доход от реализации всей продукции. Математическая мо-

дель задачи имеет вид:

Z = 4 x 1 + 5 x 2 → max;

⎧0, 25 x 1 + 0, 6 x 2 ≤15,

⎪

⎩ 1 2

⎨0, 25 x 1 + 0, 2 x 2 ≤ 7,

⎪0, 5 x + 0, 2 x ≤12;

x 1 ≥ 0, x 2 ≥ 0.

(1) (2)

(3)

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

Z ′ = − Z. Кроме того, для применения симплекс метода нужно, чтобы правые

части ограничений (2) были неотрицательными.

/

Z = −4 x 1− 5 x 2 + 0 x 3 + 0 x 4 + 0 x 5 → min;

(4)

⎧0, 25 x 1 + 0, 6 x 2 + x 3

⎪

=15,

⎨0, 25 x 1 + 0, 2 x 2

+ x 4

= 7,

(5)

⎩ 1

⎪0, 5 x

+ 0, 2 x 2

+ x 5 =12;

x j ≥ 0 (j =1, 5).

Запишем систему ограничений (5) в векторном виде:

(6)

где

x 1⋅ A 1 + x 2⋅ A 2 + x 3⋅ A 3 + x 4⋅ A 4 + x 5⋅ A 5 = B, (7)

⎛0, 25 ⎞ ⎛ 0, 6 ⎞ ⎛ 1 ⎞ ⎛ 0 ⎞ ⎛ 0 ⎞ ⎛15 ⎞

A 1 = ⎜0, 25 ⎟,

A 2 = ⎜0, 2 ⎟,

A 3 = ⎜0 ⎟,

A 4 = ⎜1 ⎟,

A 5 = ⎜0 ⎟, B = ⎜ 7 ⎟. (8)

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

⎜ 0, 5 ⎟ ⎜ 0, 2 ⎟ ⎜ 0 ⎟ ⎜ 0 ⎟ ⎜ 1 ⎟ ⎜12 ⎟

⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

Равенство (7) является разложением вектора B по векторам

A 1,

A 2,

A 3,

A 4,

A 5. Векторы (8) являются 3-х мерными. Поэтому базисом этой

системы векторов являются единичные векторы

Запишем общее решение системы (5):

Б 1 = (A 3,

A 4,

A 5).

⎧ x 3 =15 − 0, 25 x 1 − 0, 6 x 2,

⎪

⎩ 5 1 2

⎨ x 4 = 7 − 0, 25 x 1 − 0,2 x 2,

⎪ x =12 − 0, 5 x − 0, 2 x.

Чтобы получить базисное решение системы, свободные переменные при-

равниваем к нулю:

x 1 = 0, x 2 = 0. Вычисляем значения базисных переменных:

x 3 =15, x 4 = 7, x 5 =12. Базисное решение определяет начальный опорный план:

/

X Б 1 = (0; 0;15; 7;12), Z

(X Б 1)= −4 ⋅ 0 − 5 ⋅ 0 + 0 ⋅15 + 0 ⋅ 7 + 0 ⋅12 = 0.

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

столбце (столбец

Б 1) указаны векторы, образующие базис заданной системы

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

зис, то в первой симплексной таблице в столбцах стоять координаты векторов (8).

В 1,

A 1,

A 2,

A 3,

A 4, A 5

будут

Табл. 2. Первая симплексная таблица

С

Б 1	Б	В 1	À 1	À 2	À 3	À 4	А 5
–4	–5
À 3				⎡ 3⎤ ⎢⎣5⎥⎦
À 4
À 5
z j − c j

1

Последняя строка называется индексной. В третьем столбце этой строки стоит значение целевой функции:

/

Z (X Б 1)= С Б 1 ⋅ В 1 = 0⋅15 + 0⋅ 7 + 0⋅12 = 0.

В остальных клJеGтках индексной строки стоят оценки оптимальности

z j − c j

для векторов Aj

(j =1,5):

JG

Например,

z j − c j = С Б 1 ⋅ Aj − c j.

JJG

z − c = С

⋅ A − c

= 0⋅ 1 + 0⋅ 1 + 0⋅ 1 − (−4)= 4.

1 1 Б 1 1 1

4 4 2

Воспользуемся теоремой 5 из предыдущей лекции. Проверяемый опор-

ный план

X Б 1 = (0; 0;15; 7;12)

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

имеются положительные оценки для векторов

À 1 и

А 2. Перейдём к новому

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

Вводить следует вектор с наибольшей положительной оценкой оптималь-

ности. Это будет вектор

А 2, для которого

z 2 − c 2 = 5. Число 5 означает, что если

переменную

x 2 увеличить на единицу, то целевая функция уменьшится на 5

единиц и приблизится к минимуму. Столбец с вводимым в базис вектором А 2

называют направляющим и выделяем жирной линией и стрелкой.

Может оказаться, что несколько векторов имеют наибольшую положи-

тельную оценку оптимальности. Тогда выбирают любой из них.

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

Дата добавления: 2014-01-07