Численные методы решения задач ЛП


Симплекс-метод

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

(12)

……………………… (13)

(14)

Будем предполагать, что (иначе, умножим соответствующее уравнение на -1, уравнения системы (13) линейно независимы, m<n и система (13) - (14) совместна.

При сделанных предположениях можно выбрать m неизвестных (к примеру ) таких, чтобы определитель, составленный из коэффициентов при этих неизвестных, не обращался в ноль. Тогда задача (12) - (14) может быть приведена к виду, который называется специальной формой задачи ЛП:

…………………………………….. (15)

Одно из допустимых решений этой задачи можно найти, если переменные положить равными нулю. Такое решение называется допустимым базисным решением. Оно имеет вид

.

Этому решению соответствует значение целевой функции . Переменные называют базисными, набор переменных называют базисом, а переменные называют небазисными или свободными. Число возможных базисов в задаче размерности n с m ограничениями не превосходит величину .

Известно, что каждому допустимому базисному решению соответствует вершина многоугольника допустимых решений и оптимальное решение задачи (при условии его существования) достигается в одной из вершин многоугольника. Поэтому оптимальное решение задачи ЛП находится среди допустимых базисных решений. Существуют рациональные способы последовательного перебора допустимых базисных решений, которые позволяют рассматривать не все допустимые базисные решения, а их минимальное число. К таким методам относится симплекс-метод [1,2,3].



Дата добавления: 2020-10-01; просмотров: 385;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.