Метод искусственного базиса (М-метод)

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

Исходная ЗЛП в канонической форме: F(X) = c1Х1 + ... + сnXn => max

ai,1X1 + ... + ai,nXn = bi, (i=1,m) Xj>0 , (j=1,n)

Алгоритм М-метода:

В каждое i-ое ограничение вводим искусственную переменную Xn+i >0. Всего m новых искусственных переменных.

В целевую функцию F вводим m дополнительных отрицательных слагаемых вида :

-M*Xn+1 -M*Xn+2 ...-M*Xn+m , где М - произвольная очень большая константа.

Получим новую ЗЛП вида : F(X) = c1Х1 + ... + сnXn -M*Xn+1 - ... -M*Xn+m => max

ai,1X1+ ... + ai,nXn +Xn+i = bi , (i=1,m) Xj >0 , (j=1,n+m)

Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных: Xn+i = bi - ai,1X1 - ... - ai,nXn , (i=1,m)

Формируем начальное базисное решение новой М-задачи : X' = ( 0, ... 0, b1, ... bm )

Решаем М-задачу симплекс-методом

Анализируем решение М-задачи в соответствии со следующими правилами :

Если в оптимальном решении М-задачи: X" = ( X"1, ... X"n, X"n+1, ... X"n+m )

все искусственные переменные равны 0, то вектор X" = ( X"1, ... X"n )

является оптимальным решением исходной ЗЛП.

Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.

Если М-задача не имеет решения , то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.

15. Транспортная задача. Постановка задачи и её математическая модель.

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

Постановка транспортной задачи.Важным частным случаем задачи линейного программирования является транспортная задача.Постановка задачи: Пусть имеется m поставщиков и n потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.

Математическая модель транспортной задачи.

Пусть хij – количество груза, перевозимого с i-го в j-й пункт. Целевая функция: Система ограничений:

Для решения задачи составляется таблица. В клетки таблицы записывается стоимость соответствующих перевозок сij и в них же заносятся значения перевозок xij, удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками транспортная задача называется сбалансированной или несбалансированной.

Сбалансированная ТЗ: Несбалансированная ТЗ:

Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.