bannerka.ua

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

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

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.

Tagged with: , , ,
Posted in Математические модели в расчетах на эвм
Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: