10. Метод штучного базису (м-метод). Теорема про зв'язок оптимальних планів початкової задачі с м-задачі.

Метод штучного базиса применяется для решения ЗЛП, которых среди соответствующих векторов Aj (j=1,n) нет ортонормированного базиса. В этом случае в каждое из уравнение вводится неотрицательная переменная с коэффициентом 1. Она называется штучной, а соответствующий вектор ей, который очевидно будет ортом, так же называется штучным.

Имеем: Z= c1x1+c2x2+….+cnxn (min)

a11x1+a12x2+…..+a1nxn = b1

a21x1+a22x2+…..+a2nxn= b2

………………………………….

аm1x1+am2x2+…..+amnxn= bm

xj≥0,(j=1, n)

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

a11x1+a12x2+…..+a1nxn+ xn+1 = b1

a21x1+a22x2+…..+a2nxn+ xn+2 = b2

………………………………….

аm1x1+am2x2+…..+amnxn+ xn+m = bm

xj≥0,(j=1, n+m)

Штучные переменные по смыслу своего значения являются базисными. Для того чтбы сделать их равными 0, достаточно преобразовать их в свободные. С этой целью искусственные переменные вводятся в целевую функцию с условными коэффициентами М, где М – бесконечно большое число: ZM= c1x1+c2x2+….+cnxn+Mxn+1+Mxn+m (min). В этом случае пока все штучные переменные не обнулятся, значение ZM будет бесконечно большим, т.е план не будет оптимальным. Кроме того, коэффициенты в целевой функции гарантируют ,то что искусственные векторы не будут введены в базис,если раньше они были выведены из базиса.

Теорема: если в оптимальном плане М-задачи все искусственные переменные равны 0, то набор значений остальных переменных является оптимальным планом первоначальной задачи; значения целевой функции при этом совпадают.

11. Назвіть етапи заповнення другої та наступних симплексних таблиць. Як визначаються вектори для виведення із попереднього базису і введення в новий базис? Економічна інтерпретація в термінах задачі раціонального використання ресурсів.

Этапы.1) Элемен. Столбцов Б и Сб заполняют в соответствии с анализом предыдущей таблицы. 2) Элемен-ы ключевой строки (і=k) делят на разрешающий элемент . 3) Если вектор в базисе, то на пересечении строки, соответствующей базис-му вектору с одноименным столбцом, записывают единицу, а остальные элем. Столбца равны нулю.4) Все остальные, включая индексную строку, вычисляют по правилу прямоугольника . Для определения вектора, выводимого из прежнего базиса, заполняется столбец ТЕТА делением элементов столбца А нулевое на соответствующие положительные элементы ключевого столбца. Наименьшее число в столбце ТЕТА определяет вектор, выводимый из прежнего базиса. И на его место вводится новый вектор.

Оценки продукции Zj-Cj интерпретируются как затраты прибыли на внесение в план производства единицы продукции соответствующего вида. Делением элементов столбца «план» на элементы столбца «Xi» фактически делятся объемы ресурсов на удельные нормы их затрат на производство продукции i-того вида. В результате в столбце «Θi» получаем числа, которые определяют, сколько единиц продукции можно выпустить за счет каждого ресурса отдельно. Выбор наименьшего числа в столбце «Θi» определяет максимально возможное количество продукции i-того вида, полученную за счет объема всех ресурсов в совокупности. Абсолютная величина произведения Θi(Zj-Cj) является максимально возможной прибылью предприятия от включения в план производства только продукции i-того вида. Столбцы «Xj» можно интерпретировать как своеобразные удельные нормы затрат ресурсов.