11, 12 Основная теорема линейного программирования. Построение первого опорного плана, его содержательный смысл. Алгоритм симплекс метода.

Алгоритм симплекс метода базируется:

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

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

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

Алгоритм симплекс метода начинается с построения 1-го дополнительного плана, который соответствует одной из вершин, такой дополнительный план называется опорным. Эта задача решается наиболее просто, если среди векторов ограничений aj имеется m векторов образующих единый базис в пространстве ограничений.

Переменные дополненные базисным вектором называются базисными переменными, остальные объявлены свободными

Базисные переменные имеют положительные значения, совпадающие с правыми частями ограничений, значения свободных переменных = 0.

, , - базис

Х4, Х5, Х6 – базисные переменные

Х1,Х2,Х3 – свободные переменные

Х1=Х2=Х3=0

Первый опорный план соотв. Бездействию, ни какая п…. не производится, резервы ресурсов равны запасам.

В верхнюю строчку записываются коэффициенты целевой функции, в столбец Хбаз – значение базисных переменных, в столбец Сбаз – коэффициенты целевой функции при базисных переменных, записываются названия векторов и их координаты.

нач. целевой функции на рассматриваемом опорном плане

Fj=

Проверка опорного плана на оптимальность:

Если все оценки Aj ≤0, то записаны в таблице опорный план является оптимальным, значения его базисных переменных беруться из столбца Хбаз, остальные являются свободными, их значения = 0.

Проверка целевой функции на неограниченность:

Если хотя бы один столбец отвечающий Aj>0 целиком состоит из неположительных элементов, то целевая функция неограниченна на множестве допустимых планов, задача не имеет решения.

Построение нового базиса:

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

Из этих отношений выбираю наименьшее, называю ключевой строкой. Вектор, записанный в ключевой строке, исключается из базиса.