Симплексный метод решения задач линейного программирования

1.1 Понятие опорного и оптимального плана.

1.2 Алгоритм решения задач симплексным методом.

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

1.1. Понятие опорного и оптимального плана.

Вспомним общую постановку задачи математического программирования. В общем виде экстремальная задача математического программирования состоит из определения наибольшего или наименьшего значения Целевой функции

(1.1)

При условиях

, , (1.2)

Где и — заданные функции, а — некоторые действительные числа.

Совокупность чисел , удовлетворяющих ограничениям (1.2) задачи МП, называется Допустимым решением (Или Планом).

План , при котором целевая функция (1.1) достигает максимального (минимального) значения, называется Оптимальным.

1.2. Алгоритм решения задач симплексным методом.

Алгоритм симплексного метода будем рассматривать на примере задачи о норок и нутрий, которая описана в Лекции 1. Математическая постановка задачи имеет вид:

Перед применением симплексного метода задачу линейного программирования необходимо записать в основной форме:

И. Составляем первую симплекс таблицу (находим опорный план).

1) Определим базисные переменные. Для этого:

A) выпишем векторы с координатами, соответствующими коэффициентам системы ограничений при соответствующих переменных:

B) Среди выписанных векторов найдем те, составляющих систему единичных.

Напомним, что Единичным называется вектор, у которого одна координата равна единице, а все остальные — нули. В Систему единичных векторов должно входить столько векторов, сколько координат имеет каждый из них, причем таких, что в первом единица находится на первом месте, а все остальные координаты — нули; во втором единица находится на втором месте, а все остальные нули и т. д.

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

C) Переменные, соответствующие единичным векторам, называются Базисными. В нашем случае это переменные .

2) Заполняем таблицу:

№	Базис	Сб	План	16	6	0	0	0	Оценочное отношение
Х1	Х2	Х3	Х4	Х5
1	Х3	0	180	2	6	1	0	0	90
2	Х4	0	240	4	1	0	1	0	60
3	Х5	0	426	6	7	0	0	1	71
M +1	0	-16	-6	0	0	0

A) В столбец Базис записываем базисные переменные.

B) Над переменными запишем коэффициенты целевой функции при соответствующих переменных.

C) В столбец Сб Записываем коэффициенты целевой функции при базисных переменных.

D) В столбец План записываем координаты вектора Р0.

E) В столбики Х1, Х2, …, Х5 Заносятся соответственно координаты векторов Р1, Р2, …, Р5.

F) Заполняют строку (m +1):

-на пересечении (m +1)-й строки и столбца План записывают скалярное произведение двух векторов: и .

-на пересечении (m +1)-й строки и столбцов Х1, Х2, …, Х5 соответственно записывают значения выражений: , где , а
— коэффициенты системы ограничений, записанные в таблице над переменными . Так, например, на пересечении (m +1)-й строки и столбца Х1 Записываем число .

II. Оцениваем составлен план на оптимальность. Возможны три случая:

1) (m +1)-й строка не содержит отрицательных элементов, значит план считается Оптимальным. Переход к пункту V.

2) Среди чисел (m +1)-й строки находятся отрицательные, а в соответствующем этого числа колонке нет ни одного положительного. Тогда задача решений не имеет.

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

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

1) Нахождение нового базиса:

A) определения переменной, вводимой в новый базис: среди чисел (m +1)-й строки, находящиеся в столбцах Х1, Х2, …, Х5, находят меньше отрицательное. Столбик, в котором это число находится, называется Направляющим, а переменная, что в нем находится, вводится в новый базис.

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

В нашем примере направляющим столбиком есть столбик Х1, а направляющим строкой — второй. Итак, в новый базис вместо переменной х4 вводится переменная х1.

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

2) Заполнение новой симплексной таблице:

№	Базис	Сб	План	16	6	0	0	0	Оценочное отношение
Х1	Х2	Х3	Х4	Х5
1	Х3	0	60	0	5/2	1	-1/2	0	24
2	Х1	16	60	1	¼	0	¼	0	240
3	Х5	0	66	0	11/2	0	-3/2	1	12
M +1	960	0	-2	0	4	0

A) В столбец Базис записываем базисные переменные.

B) Над переменными запишем коэффициенты целевой функции при соответствующих переменных.

C) В столбец Сб Записываем коэффициенты целевой функции при базисных переменных.

D) Элементы направляющего строки делим на генеральный элемент.

E) На пересечении одноименных строк и столбцов ставим единицы, все остальные элементы базисных столбцов — нули.

F) Клетки таблицы, оставшихся заполняем по правилу четырехугольника:

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

180 — Элемент предыдущей таблицы, находившийся в клетке (х3, План).

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

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

4 — Генеральный элемент.

IV. Оценивают составлен план на оптимальность, т. е. переходят к п. II. Как видно из приведенной второй симплексной таблицы, полученный план не является оптимальным. Итак, вновь находим новый базис и переходим к еще одной симплексной таблицы.

№	Базис	Сб	План	16	6	0	0	0	Оценочные отношения
Х1	Х2	Х3	Х4	Х5
1	Х3	0	30	0	0	1	2/11	-5/11
2	Х1	16	57	1	0	0	7/22	-1/22
3	Х2	6	12	0	1	0	-3/11	2/11
M +1	984	0	0	0	38/11	4/11

Как видим, последняя строка не содержит отрицательных элементов, следовательно полученный план является оптимальным.

V. Выписывают полученный ответ с колонки План. На пересечении (m +1)-й строки и столбца План находится значение целевой функции. Другие элементы столбца план показывают значения базисных переменных. Если переменная не вошла в базис, ее значение равно нулю.

Согласно нашему примеру . Или, фермер получит максимальный Прибыль в размере 984 ден. ед., если выращивать 57 норок и 12 нутрий.

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

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

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

3) Если не переходить от поиска минимум функции к поиску максимума функции, то при применении симплексного метода в (m +1)-й строке лишаются положительных элементов. Направляющий столбик определяется по наибольшему положительным числом (m +1)-й строки. Все остальные этапы симплексного метода аналогичны описанным выше.

2. Терминологический словарь

Правило прямоугольника

Н. Е. — новый элемент, С. Е. — старый элемент, В. Е. Р. — соответствующий элемент по строке, В. Е. С. — соответствующий элемент по колонке; Г. Е. — генеральный элемент.

Направляющий (генеральный) столбик — Столбик, которому соответствует наибольший по модулю среди отрицательных элементов Δи m +1- й строки симплексной таблицы.

3. Рекомендуемая литература

1. Богаенко И. М., Григорков BC, Бойчук М. В., Рюмашин М.0. Математическое программирование: Учеб. пособие. — М.: Логос, 1996.

2. Бугир М. К. Тетрадь для практических занятий по математическому программированию. — Тернополь: Учебники и пособия, 1999.

3. Бугир М. К. Математика для экономистов. Линейная алгебра, линейные модели: Учеб. пособие. — К.: ВЦ «Академия», 1998.

4. Гвоздинський А. М. Оптимизационные задачи в организационном управлении: Учеб. посиб.-Харьков: ХГТУРЭ, 1997.

5. Гетманцев В. Д. Линейная алгебра и линейное программирование:

Уч. пособие. — М.: Просвещение, 2001.

6. Григорков BC, Бойчук М. В. Практикум по математическому программированию: Учеб. пособие. — Черновцы: Прут, 1995.

7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. — Луганск: ВУГУ, 1999.