Симплекс метод решения задачи линейного программирования

М-ды мат программирования.Задача линейного программирования

Линейное программ-е связано с исследованием и решением задач:дана сис-ма m линейно независ. ур-й с n неизвестными,наз-я сис-ой ограничений.

Требуется найти неотрицат знач-е переменных,обращающее в min целевую ф-ию(xi>=0):

(1) наз линейной формулой и удовлетвор ограничению(1)

Базисом наз любой набор из m переменных таких,что определитель составленный из коэф-ов при этих переменных не равен нулю.Остальные (n-m)переменных наз свободными. Решение сис-мы ограничений путём приравнивания к нулю свободных переменных наз базисным. Базисное решение,кот удовлетворяет неравенству xi>0,наз допустимым. Решение задачи оптимизации лежит среди допустимых базисных решенй.

В случае, если ЦФ - линейная и в задаче оптимизации введены ограничения в виде линейных неравенств, то такая задача представляет собой задачу линейного программирования. Для решения задач линейного программирования чаще всего и используют симплекс. К типичным задачам линейного программирование относят:

1) задачи изготовления различных видов продукции в условиях ограничения на сырьё

2) Задачи оптимального использования оборудования (получение максимального выпуска различных изделий, при использовании однотипного оборудования в производстве)

3) Транспортная задача (необходимо обеспечить перевозку грузов между пунктами назначения при минимальных затратах на перевозку)

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