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

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

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

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

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

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

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

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

, , - базис

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

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

Х1=Х2=Х3=0

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

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

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

Fj=

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

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

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

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

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

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

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

10. Формулировка транспортной задачи и ее математическая модель. Условия разрешимости транспортной задачи.

Транспортная задача формулируется как задача о сотавлении наиболее оптимистичного плна перевозок однородного груза. Однородный груз n – пункты направления в количестве aj, aj=1,2,3….m.

Требуется доставить в n- пунктах назначения, стоимость перевозки единицы груза из i-того пункта направления в j пункт назначения составляет Cij. В совокупности числа Cij образуют матрицу, которая называется матрицей тарифов. Требуется составит план перевозок, при котором все грузы будут вывезены из пунктов отправления в пункты назначения, удовлетворяющей имеющуюся минимальную стоимость.

Xij – количество грузов отправленных от i- поставщика к j – потребителю.

Хтхн – (Xij) f(Xij)= , Cij*Xij→min

ПО Xij = ai, i=

ПН Xij= bj, j=

Xij≥0

Постановка транспортной задачи в форме: все грузы вывезенные из пунктов отправления и потребности всех пунктов назначения удовлетворены, возможно только в том случае, если суммарные запасы груза = суммарным потребностям.

А= ai= bj= В

При выполнении этого равенства транспортная модель называется замкнутой (сбалансированной, закрытой)

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

Транспортная модель является задачей линейного программирования и может быть решаема симплекс методом, однако специфика модели: каждая переменная входит в 2 ограничения, причем с коэфф.1, позволяет применить к решению задачи более простой метод. Этот метод является частным случаем симплекс метода, в котором повторяются все основные моменты общего симплекс метода.