Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Е.В. Буйная Симплексный метод решения оптимизационных задач

.pdf
Скачиваний:
59
Добавлен:
19.08.2013
Размер:
248.34 Кб
Скачать

1

Министерство образования Российской Федерации

Кузбасский государственный технический университет

Кафедра вычислительной техники и информационных технологий

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Методические указания и задания к практическим занятиям по курсу «Экономико-математические методы» для студентов экономических специальностей

Составители Е.В. Буйная

М.А. Тынкевич

Кемерово 2000

2

Министерство образования Российской Федерации

Кузбасский государственный технический университет

Кафедра вычислительной техники и информационных технологий

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Методические указания и задания к практическим занятиям по курсу «Экономико-математические методы» для студентов экономических специальностей

Составители Е.В. Буйная

М.А. Тынкевич

Утверждены на заседании кафедры Протокол № 5 от 30.11.99

Рекомендованы к печати учебнометодической комиссией по специальности 071900 Протокол № 2 от 30.11.99

Электронная копия находится в библиотеке главного корпуса КузГТУ

Кемерово 2000

3

1. Основные понятия и алгоритм стандартного симплекс-метода

Пусть стоит задача максимизации (минимизации)

 

L(X)

=

n

C

j X

j

( 1.1 )

 

 

 

 

j = 1

 

 

 

 

при условиях

 

 

 

 

 

 

 

 

n

A

j

X

j =

B

,

 

(1.2 )

j =

1

 

 

 

 

 

 

 

X

j

0

,

j = 1, .., n

,

(1.3 )

где Aj (j=1,...,n) , B m-мерные векторы.

Напомним несколько ключевых определений и свойств задачи.

Вектор X=(X1,X2,..,Xn) , удовлетворяющий условиям (1.2) и (1.3), называется планом. Множество планов в геометрической интерпретации представляет собой выпуклый многогранник.

План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом. Опорный план соответствует некоторой вершине многогранника планов.

Опорный план содержит не свыше m положительных компонент (m – число независимых ограничений задачи). Опорный план, содержащий менее m положительных компонент, называют вырожденным.

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

Система m векторов Aj при положительных компонентах опорного плана называется базисом этого плана.

Симплексметод - это метод упорядоченного перебора опор-

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

В теоретическом обосновании симплексного метода [1] обнаруживается, что в случае единичного базиса (векторы образуют единичную матрицу) коэффициенты разложения некоторого вектора по векторам базиса, используемые в симплексной процедуре, совпадают с компонентами самого вектора (в общем же случае придется решать систему

4

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

Предположим, что исходная задача приведена к канонической форме (1.1)-(1.3) при В 0 и первые m векторов начального базиса образуют единичную матрицу (их можно принять за базис).

Для единообразия описания вычислительной процедуры в дальнейшем будем пользоваться т. н. симплексными таблицами вида:

C

 

Базис

План

С1

C2 ...

Сm

Cm+1

...

Ck

...

Cn

 

баз

 

плана

X

A1

A2 ...

A

A

m+1

A

...

A

 

 

 

 

 

 

 

 

m

 

 

k

 

n

 

С1

 

A1

B1

1

0 ...

0

Z

 

...

Z

...

Z1n

 

 

 

 

 

 

 

 

 

1,m+1

 

1k

 

 

 

 

С2

 

A2

B2

0

1 ...

0

Z

 

...

Z

...

Z2n

 

 

 

 

 

 

 

 

 

2,m+1

 

2k

 

 

 

 

...

 

...

 

...

... ... ... ...

 

...

... ... ... ...

 

 

Cm

 

Am

Bm

0

0 ...

1

Zm m+1

...

Zmk

...

Zmn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Zk

L(X)

Z1

Z2 ...

Zm

Z m+1

...

Zk

...

Zn

 

 

 

k

 

 

1

2 ...

m

m+1

...

k

...

n

 

В первом столбце таблицы (С баз) записывают коэффициенты целевой функции (С1, С2 …Сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу, как в нашем случае А1 Аm). Во втором столбце (Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) – правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со столбцом – «План Х», и суммируя эти произведения, мы получаем значение целевой функции (ячейка – L(X)=С1 В1 + С2 В2+…+

m Bm).

Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизменной на протяжении всего решения (С1, С2, …, Сn).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z11,…, Z1n,…, Zm1,…, Zmn). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу.

 

5

 

 

Строку Zk рассчитывают по формуле

 

 

Zk = m C j Z jk ,

 

(1.4)

 

j=1

 

 

а строку k рассчитывают по формуле

 

 

k = Z k - C k .

 

(1.5)

Известно, что при переходе к новому опорному плану X(Θ

), в ко-

тором k-я компонента равна Θ

>0 (станет базисной),

значение целевой

функции изменится и будет равно

 

 

L { X( Θ

) } = L(X 0 ) - Θ ∆

k .

(1.6)

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

Критерий 1 (критерий оптимальности). Если все k ≥ 0 , то вы-

бранный план для задачи максимизации является оптимальным (для за-

дачи на минимум признак оптимальности - неположительность всех k

).

Критерий

2 . Если обнаруживается некоторое k < 0 (для задачи

минимизации

k>0) и хотя бы одно из значений Zjk >0,

то переход к

новому опорному плану увеличит (уменьшит) значение

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

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

понент опорного плана должно оставаться

равным

m, то одну из m

базисных компонент исходного плана обращаем в нуль выбором

Θ = m

i n

X 0j

 

,

(1.7)

Z jk

Z

jk > 0

 

 

где X 0j - компоненты опорного плана;

Z jk - коэффициенты при k-й переменной в ограничениях задачи.

6

Критерий 3 . Если обнаруживается некоторое ∆ k < 0, но все Zjk0, то линейная форма задачи не ограничена по максимуму (неограниченность по минимуму устанавливается аналогично при ∆ k>0 и всех Zjk

0).

Переход к очередной симплексной таблице сводится к тому, чтобы

выразить Xk из уравнения, соответствующего минимуму для Θ , и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):

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

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

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

2.Приведение задачи к канонической форме

Как мы уже отмечали, изложенный алгоритм стандартного сим- плекс-метода применим к задачам, представленным в каноническом виде.

Для приведения задачи к такому виду используют следующие приемы.

1. Если на некоторую переменную Xk отсутствует условие неотрицательности, то ее всегда можно заменить разностью двух неотрицательных переменных, т.е.

X k = X k' - X "k , где X k'

0 , X "k 0 .

Если же на некоторую переменную стоит условие неположи-

тельности, производится замена X k = - X k©

, X k© 0 .

7

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

ляющую (свободную, дополнительную), переменную, уравновешиваю-

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

Например, ограничения

 

 

 

 

X 1 + 2 X 2 + 3 X 3

7

X 1 -

X 2 +

X 3

2

преобразуются к виду

 

 

 

 

X 1 + 2 X 2 + 3 X 3 - X 4

= 7 , X 4 0

X 1 - X 2 +

X 3

+ X 5 = 2 , X 5 0 .

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

Рассмотрим несколько примеров:

Пример 1.

Пусть стоит задача максимизации

L(X) = 3X1+4X2-5X3

при условиях

3X1 - 4X2 + X3 5

X1 - 10X2 + X3 = 10 5X2 - 3X3 0 X1, X2 0, X3 0.

Так как X3 0, произведем замену X3 = - X3, где X30.

Так как первое и третье ограничения записаны в форме неравенства, необходимо ввести ослабляющие переменные. В первое ограничение вводим переменную Х4 = 5 - 3X1 - 4X2 + X3 , Х4 0, а в третье - переменную Х5 = 0 - 5X2 - 3X3 , Х5 0. В итоге исходная задача примет вид:

Максимизировать

L(X) = 3X1 + 4X2 + 5X3

при условиях

- X3+ Х4

 

3X1 - 4X2

= 5

X1 - 10X2

- X3

= 10

5X2 - 3X3- Х5 = 0 X1, X2, X3, X4 , X5 0.

8

Пример 2.

Пусть стоит задача минимизации

L(X) = -5X1 + 2X2

при условиях

-5X1 + X2 -10

X1 - X2 = 10

Приводим исходную задачу к каноническому виду:

1. Расписываем переменные X1 и X2 через разность двух неотрица-

тельных переменных, т.е. X1 = X1- X1’’ и X2 = X2– X2’’, где X1, X1’’,

X2, X2’’ 0.

2. Первое ограничение умножаем на (-1) и вводим ослабляющую переменную X3 0.

В результате переходим к задаче минимизации

L(X) = -5X1 + 5 X1’’+ 2X2- 2X2’’

при условиях

5X1- 5X1’’ - X2- X2’’- X3 = 10

X1- X1’’ - X2+ X2’’

= 10

X1, X1’’, X2, X2’’, X3 0.

3. Выбор начального опорного плана

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

Если такой единичной подматрицы не обнаруживается, то либо придется перебирать все подсистемы m уравнений с m неизвестными в надежде обнаружить неотрицательные решения, либо прибегнуть к ме-

тоду искусственного базиса.

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

9

чи минимизации и с коэффициентом - М для задачи минимизации, где М>0 - сколь угодно большое число.

Полученная М-задача решается до получения оптимального плана.

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

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

4. Примеры решения линейных задач симплексным методом

Пример 1.

Предприятие планирует закупить четыре вида сырья, которое должно использоваться на производство продукции А, Б, В в следующих пропорциях:

Сырье

 

Продукция

 

 

А

 

Б

 

В

1-го вида

0,5

 

0,2

 

0

2-го вида

0,1

 

0

 

0,3

3-го вида

0,2

 

0

 

0,2

4-го вида

0

 

0,5

 

0,2

У предприятия имеются заказы на поставку этих видов продукции в размерах до 10, 30 и 20 единиц соответственно. В договоре предусмотрены цены поставок за единицу продукции - 10, 8 и 20 условных единиц. Рыночная цена требуемого предприятию сырья равна 2, 5, 8 и 3 у.е. за единицу сырья соответственно.

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

Решение:

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

10

1 этап. Математическая постановка задачи

В начале определим, какие величины в задаче неизвестны и что нужно найти. Так как нам необходимо определить оптимальное количество закупаемого сырья, обозначим за Х1 , Х2 , Х3 и Х4 – объемы закупки сырья соответствующих видов. В этом случае количество произведенной продукции будет равняться:

-продукции А - 0,5Х1+0,1Х2+0,2Х3;

-продукции Б - 0,2Х1+0,5Х4;

-продукции В - 0,3Х2+0,2Х3+0,2Х4.

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

Максимизировать

L(X)=10(0,5X1+0,1X2+0,2X3)+8(0,2Х1+0,5Х4)+ +20(0,3Х2+0,2Х3+0,2Х4)-(2X1+5X2+8X3+3X4)

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

0,5X1+0,1X2+0,2X3

≤ 10

(4.1)

0,2Х1+

0,5Х4 ≤ 30

(4.2)

0,3Х2+0,2Х3+0,2Х4 ≤ 20

(4.3)

Х1≥ 0

Х2≥ 0

 

(4.4)

 

 

(4.5)

 

Х3≥ 0

 

(4.6)

 

Х4

0

(4.7)

Условия (4.1)-(4.3)

– это ограничения на объем производства

 

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

Условия (4.4)-(4.7) – естественные условия неотрицательности переменных (объемы закупки сырья не могут быть отрицательны).

В итоге мы имеем оптимизационную задачу с четырьмя неизвестными и семью ограничениями (четырьмя ограничениями на неотрицательные неизвестные).