Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Специальная задача ЛП
Рассмотрим задачу ЛП в канонической форме: (6) (7) (8) Будем предполагать, что (иначе, умножим соответствующее уравнение на -1), уравнения системы (7) линейно независимы, m<n и система (7) -(8) совместна. При сделанных предположениях можно выбрать m неизвестных (к примеру ) таких, чтобы определитель, составленный из коэффициентов при этих неизвестных, не обращался в ноль. Тогда задача (6) – (8) может быть приведена к виду, который называется специальной формой задачи ЛП: ………………….. (9) Одно из допустимых решений этой задачи можно найти, если переменные положить равными нулю. Такое решение называется допустимым базисным решением. Оно имеет вид: Этому решению соответствует значение целевой функции . Переменные называют базисными, набор переменных называют базисом, а переменные называют небазисными или свободными. Число возможных базисов в задаче размерности n с m ограничениями не превосходит величину . Известно, что каждому допустимому базисному решению соответствует вершина многоугольника допустимых решений и оптимальное решение задачи (при условии его существования) достигается в одной из вершин многоугольника. Поэтому оптимальное решение задачи ЛП находится среди допустимых базисных решений. Существуют рациональные способы последовательного перебора допустимых базисных решений, которые позволяют рассматривать не все допустимые базисные решения, а их минимальное число. К таким методам относится симплекс-метод.
Дата добавления: 2015-07-26; просмотров: 148; Нарушение авторских прав Мы поможем в написании ваших работ! |