9. Алгоритм симплекс метода

1)Находим первоначальный опорный план, исключаем из ценовой ф-ии базисные переменные и находим оценки плана (коэф-ты при соотв-х неизвестных с противоположными знаками)

2)Если все оценки >= 0, то план оптимальный и задача решена. Если в плане есть отриц. оценки, то переходим к п.3

3)Выбираем в строке оценок мин. Отрицательную оценку Δк . Будем сводить в базис переменную Хк

4)Если в К-той строке все коэфф-ты у матрицы отрицательные, то задача не ограничена в многограннике решений. В противном случае в качестве разрешающего элемента Выбираем элемент аik такой, что

5)Выводим из базиса переменную Хi, проводя преобразования по методу Жордана-Гауса, далее переходим на пункт 2.

6)Если решаем задачу на min, то рассматриваем ф-ию –z и задача сводится к задаче на max

Z=c1x1+c2x2+…+cnxn →min

-Z=-c1x1-c2x2-…-cnxn →max

10 Метод искусственного базиса

Рассмотрим задачу лин. программ-ия в каноническом виде

Z=c1x1+c2x2+…+cnxn →min(max)

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

И решают эту задачу с целевой ф-ей U:

U= Xn1+1+…+ Xn1+m→min

Если Umin =0, то оптимальный план X*(x1,… xn,0,…0) задачи будет первоначальным опорным планом. Если же Umin ≠0, то тогда система уравнений несовместна и следовательно не имеет решения.

При решении задач по методу искусственного базиса выписывают 2 строки оценок: строку z и u, при этом в начале иттерации проводят по строке u, и если Umin =0, то далее проводят иттерации по строке z

13 Рассмотрим пару взаимодвойственных симметричных задач. Оптимальные планы которых x^*(x^*_1…x_n^*),y^*(y₁^*…y^*_n). Тогда y_i*(∑a_ijx_j^*-b_i)=0(1), x_j*(∑a_ijx_i^*-c_j)=0(2).Из равенства 1 следует, что если ресурс избыточный, то соотв-я оценка равна нулю, и если она не равна нулю, то ресурс деффицитный (полностью используется).

14 (dz/db_i)*(x^*)=y^*_i. тогда ∆z≈ y^*_i(∆b_i). Если ∆b_i = 1,то ∆z≈ y^*_i. Таким образом, y^*_i указывает,на сколько увеличится прибыль, если соотв-й ресурс увеличится на единицу.

15 Дополнительные переменные показывают рентабельность производства соответствующей продукции. Если соотв-я переменная равна нулю, то производство этой продукции рентабельно.

16 Предположим, что преобразования системы ограничения задачи линейного программирования получилось некоторое базисное решение, некоторые координаты которого отрицательны. Вэтом случае это базисное решение не будет опорным планом. Предположим также,что все оценки для этого плана =>0. Тогда возникает необходимость получить другое базиснон решение таким образом, чтобы знаки остались у оценок теми же, а число отрицательных координат уменьшилось. Это можно сделать, решая двойственную задачу. При этом нет необходимости выписывать симплексные таблицы для двойственной задачи, поскольку в прямой задаче по строкам записана прямая задача, а по столбцам двойственная.

Алгоритм:

1. Рассматривают первую симплексную таблицу и выбирают строку с миним отрицательной правой частью(разрешающая строка)

2. Рассматривают коэффициетны матрицы в 1 строке и выбирают в качестве разрешающего элемента такой, чтобы он был наименьшим отрицательным.

3. Вводим переменную в базис и переходим на пункт 1.