Понятие метода линейного программирования

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

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

В процессе работы алгоритма  происходит спонтанное обращение матрицы  ограничений по частям, соответствующим  текущим базисным векторам. Указанная  способность делает весьма привлекательной  машинную реализацию вычислений вследствие экономии памяти под промежуточные  переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных  значительно  превышает число ограничений .

В целом, метод отражает традиционные черты общего подхода к решению  задач линейного программирования, включающего в себя канонизацию  условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.

Особенности заключаются  в наличии двух таблиц - основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных  формул.

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

1. если прямая задача  является задачей максимизации, то двойственная будет задачей  минимизации, и наоборот;

2. коэффициенты целевой  функции прямой задачи становятся  свободными членами ограничений  двойственной задачи;

3. свободные члены ограничений  прямой задачи становятся коэффициентами  целевой функции двойственной  задачи;

4. матрица ограничений  двойственной задачи получается  путем транспортирования матрицы  ограничений прямой задачи;

5. знаки неравенств в  ограничениях изменяются на противоположные;

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

Заключение

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

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

Значительное число  задач, возникающих в обществе, связано  с управляемыми явлениями, т.е. с  явлениями, регулируемыми на основе сознательно принимаемых решений. При том ограниченном объеме информации, который был доступен на ранних этапах развития общества, принималось оптимальное  в некотором смысле решение на основании интуиции и опыта, а  затем, с возрастанием объема информации об изучаемом явлении, - с помощью  ряда прямых расчетов. Так происходило, например, создание календарных планов работы промышленных предприятий.

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

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

Третий этап - исследование влияния переменных на значение целевой  функции. Этот этап предусматривает  владение математическим аппаратом  для решения математических задач, возникающих на втором этапе процесса принятия решения.

Четвертый этап - сопоставление  результатов вычислений, полученных на третьем этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень  адекватности модели и моделируемого  объекта в пределах точности исходной информации.

Широкий класс задач  управления составляют такие экстремальные  задачи, в математических моделях  которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как  раз и составляют содержание математического  программирования.

Список литературы

Берюхова Т.Н.Банк производственных задач в расчетах на ЭВМ: учебное пособие. – Тюмень.: ТюмИИ, 1992. – 124с.

Карманов В.Г. Математическое программирование: учебное пособие  для студентов вузов. – М.: Физматлит, 2001. – 264с.

Кузнецов А.В. Математическое программирование: учебное пособие  для вузов. – М.: Высшая школа, 1976. – 352с.

Мочалов И.А. Нечеткое линейное программирование. // Промышленные АСУ и контроллеры. – 2006. - № 10. –  с.26-29.

Пашутин С.Оптимизация издержек и технология формирования оптимального ассортимента. // Управление персоналом. – 2005. - №5. – с.20-24.