- •2. Типичные задачи лп.
- •3. Классификация распределительных задач.
- •7. Свойства решения задач лп
- •8. Общая линейная распределительная задача
- •Алгоритм
- •Правила заполнения симплекс-таблицы
- •10. Правила замены вектора в базисе
- •11. Модифицированный см
- •12. Геометрическая интерпретация линейных оптимизационных задач.
- •13. Вырожденность и зацикливание
- •14. Двойственная задача.
- •15. Двойственный см
- •16. Алгоритм метода искусственного базиса
16. Алгоритм метода искусственного базиса
Характерной особенностью является то, что для получения опорного плана так же используется симплекс метод.
Алгоритм:
Представление неравенств исходной системы ограничений в виде системы равенств
a11*x1+…+a1n*xn=b1
…
am1*x1+…+amn*xn=bm
Ввод искусственных или вспомогательных неизвестных Zi по числу уравнений Zi=bi-( ai1*x1+…+ain*xn) В системе переменные Zi образуют опорный план.
Формирование искусственной целевой ф-ии, выраженной через искусственные переменные F=Z1+Z2+…+Zmmin
Использование СМ для минимизации целевой ф-ии, при этом возможны 2 пути:
* Fmin>0 В этом случае с-ма уравнений, исходная с-ма ограничений(п.1) не имеет неотрицат решений, а это значит, что и исходная задача ЛП с такой с-ой ограничений не имеет решений
* Fmin=0 Исходная с-ма имеет по крайней мере 1 неотрицательное решение. В этом случае после неск-их итераций СМ приходят к системе ур-ий , в которой все переменные Zi уже небазисные. Оставшаяся система будет равносильна исходной, но уже имеющей базис.
На этом первый этап закончен и приступаем к оптимизации имеющегося плана.
Если в Зе ЛП требуется минимизировать критерий, то необходимо выполнить замену. Ввести искусственную целевую ф-ию F/=-F, F/→max.