Линейного программирования

Аналитические методы решения задачи

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

Для решения задач линейного программирования в общем случае разработано много методов, которые можно разделить:

1) по способу решения задачи на две группы:

Приближенные методы, которые гарантируют приближенное решение задачи. Они просты и хорошо приспособлены к обычным вычислениям (индексный метод, метод аппроксимации Фогеля и т.д.).

Конечные методы гарантируют нахождение точного решения за конечное число шагов; Конечные методы, в свою очередь, можно разделить на три группы: последовательного улучшения плана (симплекс- метод); последовательного уточнения оценок; последовательного сокращения невязок.

2) по виду решаемых задач на две группы:

универсальные, применяемые для решения широкого класса задач линейного программирования (последовательного улучшения плана; метод разрешающих множителей академика Л.В. Канторовича) и

специальные, применяемые для решения отдельных типов задач линейного программирования (распределительный закон и его модификации; метод дифференциальных рент, венгерский метод и т.д.). Они, как правило, проще универсальных, однако, приспособлены для решения узкого класса задач.

При использовании вычислительных машин универсальные методы дают возможность решать задачи линейного программирования общего вида с сотнями ограничений и практически любым числом переменных, а задачи специального вида – с тысячами ограничений (способы часто не хранятся в памяти, а воспроизводятся алгоритмически).

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