9. Характеристика симплексної таблиці. Чому в першій симплексній таблиці в стовпцях Aj залишуються компоненти відповідних векторів.

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

В столбцах записываются: Б – векторы, составляющие ортонормированный базис; - коэффициенты целевой функции при базисных переменных; – коэффициенты целевой функции; – коэффициенты разложения вектора по векторам базиса.

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

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

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

М-метод применяется в тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи. Прежним остается требование, чтобы задача была представлена в канонической форме. М-метод состоит в том, что применяются те же правила СМ, но к М-задаче. М-задача получается из исходной с добавлением к левой части системы уравнений в канонической форме исходной задачи, таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных, линейно независимых векторов. В ЦФ исходной задачи добавляется в случае её максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где число М является сколь угодно большим положительным числом. Дальнейшая процедура М-метода будет сводиться к тому, чтобы из базиса были удалены все искусственные переменные. До тех пор, пока все искусственные переменные не выведутся из базиса, значение Z будет бесконечно большим, т.е. соответствующие планы не будут оптимальными.

Теорема про зв'язок опт. планів початкової задачі та М-задачі. ЗЛП та М-задача одночасно або мають розв'язки, або їх не мають. Якщо М-задача має розв'язок та в її оптимальному плані всі штучні змінні нульові, то вихідна ЗЛП має оптимальний план із М-задачі відкиданням штучних змінних. Якщо ж хоча б одна штучна змінна додатна, то цільова ф-я ЗЛП необмежена на множині планів К (ЗЛП не має розв’язків). Якщо М-задача не має розв’язків, то і відповідна ЗЛП також не має розв’язків.

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

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

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