<<
>>

СИМПЛЕКСНЫЙ МЕТОД

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

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

Значение целевой функции при этом перемещении для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется базисное неотрицательное решение. Алгоритм симплексного метода

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

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1–го шага, за исключением строки Δj (индексная строка), заполняем по данным системы ограничений и целевой функции.

Индексная строка для переменных находится по формуле

и по формуле

Возможны следующие случаи при решении задачи на максимум:

— если все оценки Δj ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка Δj ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т.е. целевая функция неограничена в области допустимых решений;

— если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

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

Если хотя бы одна оценка Δk < 0, то k–й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k–гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2–го шага:

— переписываем ключевую строку, разделив ее на ключевой элемент;

— заполняем базисные столбцы;

— остальные коэффициенты таблицы находим по правилу "прямоугольника"[1]. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

Примечание. Если целевая функция L() требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δj при всех j = .

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме СИМПЛЕКСНЫЙ МЕТОД:

  1. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  2. 4.2. Защищенные каналы передачи информации
  3. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  4. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  5. § 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом
  6. Содержание дисциплины
  7. СИМПЛЕКСНЫЙ МЕТОД
  8. ТРАНСПОРТНАЯ ЗАДАЧА
  9. Метод Гомори
  10. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
  11. Перечень вопросов к экзамену на первом курсе
  12. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  13. 4.3. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
  14. ОГЛАВЛЕНИЕ
  15. Основные отличия от предыдущих изданий