Правила выбора ключевого столбца и строки при решении задачи ЛП симплексным методом, последствия неправильного выбора

Ключевой столбец – тот, у которого коэффициент свободной переменной в функции цели является наименьшим отрицательным. Ключевая строка выбирается исходя из минимума соотношений вi на aij>0. При неправильном выборе условие неотрицательности свободных переменных не будет соблюдено, следовательно, неотрицательные базисные решения получены не будут.

32.Введение балансовых переменных в систему ограничений задачи ЛП: цель и правило введения

Балансовые переменные вводятся в систему ограничений с целью преобразования СЛАН с n переменными в СЛАУ с n+m переменными, где m – количество линейных уравнений/неравенств.

“балансовые”=”дополнительные”-чтобы приравнять неравенство в равенство.

33.Введение искусственных переменных в систему ограничений задачи ЛП при решении задачи ЛП методом искусственного базиса: цель и правило введения

В каждое i-ое ограничение вводим искусственную переменную X_n+i >0. Всего m новых искусственных переменных. Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных и решать полученную задачу симплекс-методом.

Метод искусственного базиса применяется к решению задач линейного программирования в общем случае, когда система ограничений не имеет предпочитаемого вида.

Пусть требуется минимизировать (1) при ограничениях:

(2)

. (3)

К данной задаче ЛП непосредственно нельзя применить симплексный метод, т.к. система (2) не имеет предпочитаемого вида, хотя правые части всех ее уравнений можно считать неотрицательными. Поэтому к левой части каждого уравнения системы (2) добавим по одной искусственной неотрицательной неизвестной и образуем следующую систему m линейных уравнений с n+m неизвестными:

(4)

где (5)

Очевидно, в системе (4) неизвестные образуют базисный набор, который принято называть искусственным. Кроме того, образуем искусственную линейную форму: (6) и сформулируем следующую вспомогательную задачу линейного программирования: минимизировать линейную форму (6) при линейных ограничениях (4) и (5).

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

34.В каком случае процесс решения задачи ЛП симплекс-методом является конечным?

Один шаг симплекс-метода состоит в работе с конкретным базисным решением и заключается в следующем:

1)вычисляется симплекс-разности для всех свободных переменных:

c_j-c_Bq_j, j=m+1, m+n;

2)определяется максимальная симплекс-разность

c_s –c_Bq_s =max (c_j- c_Bq_j)

m+1≤j≤m+n

(если разность положительна,переходим к след пункту,если нет то алгоритм закончен)

3)в базис вводится переменная Хs, а выводится переменная Xr, для которой

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

Когда возможно найти оптимальное решение Х= (х1,х2,..хn), при котором все симплекс-разности (∆) отрицательны.

35.В каких задачах применяется симплекс-метод?

В задачах линейного программирования.Для задач,связанных с принятием решений в экономике,характерна ситуация,когда требуется достичь некоторой цели при ограниченных ресурсах.Если функция цели линейно зависит от переменных (размеров видов деятельности или производственных процессов) и расходы ресурсов также линейно зависят от переменных,то такая задача принятия решений сводится к задаче линейного программирования(ЛП).

Для решения оптимизационной задачи линейного программирования. Это матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к “канонической форме”; последовательное ее преобразование по симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый план, обеспечивающий экстремальное значение целевой функции.

36.Что представляет собой симплексная таблица?

Симплекс-таблица составляется из коэффициентов при x₁, x₂, x₃, x₄ и чисел, стоящих в правых частях уравнений-ограничений задачи: в первой строке записываются элементы уравнения (А), во второй - (В). В последней строке симплекс-таблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи плюс один столбец правых частей (b):