ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ .

Алгебра симплекс – метода.
Существо метода состоит в следующем. Находим какое-нибудь базисное решение. Далее проверяем, не достигнут ли уже максимум целевой функции. Если нет, то ищем новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение q/. Затем процедуру повторяем. Для перехода к новому допустимому базисному решению одну из свободных переменных следует сделать базисной. При этом она станет отличной от нуля и будет возрастающей. Если какая либо свободная переменная входит в целевую функцию со знаком «+», т.е. при её увеличении целевая функция увеличивается, то максимум не достигнут и данную переменную следует сделать базисной (отличной от нуля).

Математическое описание.
Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом .
Информация, которую можно получить с помощью симплекс-метода, не ограничивается лишь оптимальными значениями переменных.
Процесс решения задачи линейного программирования носит итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования .
Симлекс-метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач.
Правая и левая части ограничений линейной модели могут быть связаны знаками . Кроме того, переменные, фигурирующие в задачах ЛП, могут быть неотрицательными или не иметь ограничения в знаке. Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме, которую назовем стандартной формой линейных оптимизационных моделей. При стандартной форме линейной модели.
1. Все ограничения записываются в виде равенств с неотрицательной правой частью;
2. Значения всех переменных модели неотрицательны;
3. Целевая функция подлежит максимизации или минимизации.
Покажем, каким образом любую линейную модель можно привести к стандартной.

Линейное программирование. 3
Симплекс-метод. 6
Двойственная задача. 13
Список используемой литературы. 14

• Ашманов С.А., «Линейное программирование», Москва, 1961 г.
• Коршунов Ю.М., «Математические основы кибернетики», Москва, 1987 г.;