Исследование операций (стр. 3 )

S3=0

S1=0

2

F

C

S2=0

1

XH=0

B

A

XH

4

3

1

XB=0

Увеличение Si соответствует смещению точек с ребер во внутреннюю область симплекса.

Занесем координаты угловых точек в таблицу:

точки	нулевые переменные	нулевые переменные
А B C D E F	xнхв xнs2 s1s2 s1s4 s3s4 xнs3	s1 s2 s3 s4 s1 xн s3 s4 xн xв s3 s4 xн s2 s3 xв s1 s2 xн xв s1 s2 xн s4

Введем обозначения: m – число уравнений ограний ограничений, n – число

переменных. Анализируя таблицу можно сделать выводы :

1) Угловым точкам симплекса соответствуют пданы, в которых равны нулю n переменных.

2) Смежные экстремальные точки отличаются одной переменной в наборах нулевых и ненулевых переменных.

Внутренним точкам симплекса соответствуют планы, не содержащие ни одной нулевой переменной. Поэтому приравнивая нулю (n-m ) переменных в системе ограничений мы всегда получаем опорный план – то есть координаты угловой точки. Это свойство симплекса получило название однозначности экстремальных точек.

Решения системы уравнений, получаемые приравниванием нулю (n-m) переменных называются базисными .Нулевые переменные ,им соответствующие - небазисными.(свободными), остальные- базисными.

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

2.6.3. Вычислстельная процедура симплекс - метода.

Симплекс-алгоритм состоит из следующих шагов:

0)После приведения задачи к стандартной форме определяют начальное допустимые стороны решения (первоначальный опорный план), приравнивая нулю свободные переменные.

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

2)  Из числа базисных выбирается исключаемая переменная.

3)  Находится новый опорный план, далее шаг 1.

Пример

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

Z - 3xH - 2xB = 0

xH + 2xB + S1 = 6

2xH + xB + S2 = 8

- xH + xB + S3 = 1

xB + S4 = 2

xH, xB, S1, S2, S3, S4 > 0

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

ЛЕКЦИЯ 5

В качестве свободных переменных выбираем Xн =Xв =0 . В результате получаем опорный план: {Xн, Xв =0 ,S1,S2,S3,S4} это координаты т. А, которую мы используем в качестве первоначального опорного плана (П. О.П.)

Полученные результаты удобно представить в виде таблицы:

Базисные перемен.	Z	Xн	Xв	S1	S2	S3	S4	Решение
Z	1	-3	-2	0	0	0	0	0
S1	0	1	2	1	0	0	0	6
S2	0	2	1	0	1	0	0	8
S3	0	-1	1	0	0	1	0	1
S4	0	0	1	0	0	0	1	2

Столбец “базисные переменные” содержит их набор в П. О.П. Строки таблицы ¾ коэффициенты целевой функции ( Z ) и соответствующих уравнений ограничений. В столбце “Решение” содержатся значение целевой функции ¾ 0 и базисное решение

(S1=6, S2=8, S3=1, S4=2) .

1) Для выбора включаемой переменной существуют различные процедуры. При использовании компьютера, когда трудоемкость расчетов не играет роли, разумнее всего выбрать самую простую: по максимальному положительному коэффициенту в целевой функции при минимизации и максимальному отрицательному при максимизации. В нашем случае такой переменной является Xн . Признаком оптимума является отсутствие положительных при минимизации и отрицательных при максимизации коэффициентов Z .

2) Выбор исключаемой переменной производят таким образом, чтобы обеспечить в новом опорном плане выполнение условия: Xн, Xв, S1,¼,S4³0. Доказано, что это условие выполняется при выборе исключаемой переменной по минимуму величины q :

где ai, m+2 – элементы столбца “Решение”

ai,h –элементы h-го столбца, соответствующего включаемой переменной (h=2) min+ –оператор, выбирающий минимальное положительное значение.

Столбец, соответствующий включаемой переменной, назовем ведущий, а его но­мер обозначим h (его элементы aih). Строку, соответствующую исключаемой переменной, назовем ведущей строкой, а ее номер обозначим k (ее элементы akj ) где k=3 . Элемент, находящийся на пересечении ведущих строки и столбца, называется ведущим.

3) Новый опорный план получается решением системы уравнений ограничений относительно новых базисных переменных методом исключения (Гаусса - Жордана).

Алгоритм состоит из двух этапов:

а) Формируются элементы новой ведущей строки:

a*kj=a kj/a kh

б) Рассчитываются значения остальных коэффициентов a*ij:

a*ij=a ij - a ih * a* kj

Звездочкой обозначены ”новые” значения

Воспользовавшись формулами, можно получить новый опорный план:

Базисные перемен.	Z	Xн	Xв	S1	S2	S3	S4	Решение
Z	1	0	-1/2	0	3/2	0	0	12
S1	0	0	3/2	1	-1/2	0	0	2
Xн	0	1	1/2	0	1/2	0	0	4
S3	0	0	3/2	0	1/2	1	0	5
S4	0	0	1	0	0	0	1	2

1) a*11 = a11 – a12 * a*31 = 1 – (–3) * 0 = 1

2) a*12 = a12 – a12 * a*32 = –3 – (–3) * 1 = 0

3) a*13 = a13 – a12 * a*33 = –2 – (–3) * (1/2) = –1/2

4) a*14 = a14 – a12 * a*34 = 0 – (–3) * 0 = 0 и т. д.

В новом решении Xн = 4, Xв = 0, что соответствует точке В на О. Д.З. Значение В возросло до 12.

В новом опорном плане свободные переменные Xв и S2 = 0, а базисные

представлены в столбце ”Решение”

Анализируя таблицу, находим: столбец по максимальному отрицательному коэффициенту целевой функции:

a13 = –1/2; h = 3

Включаемая переменная Хв

Исключаемая - S1

Направляющую строку по формуле:

Пересчет по методу Гаусса – Жордана позволяет составить следующую таблицу

Базисные переменн.	Z	Xí	Xâ	S1	S2	S3	S4	Решение
Z	1	0	0	1/3	4/3	0	0	12 2/3
Xâ	0	0	1	2/3	-1/3	0	0	4/3
Xí	0	1	0	-1/3	2/3	0	0	10/3
S2	0	0	0	-1	1	1	0	3
S4	0	0	0	-2/3	1/3	0	1	2/3

В новом базисном решении Хн=3 1/3, Xв=1 1/3 (точка С на графическом решении).