Оптимизационные модели. Метод искусственного базиса (М-метод)

СОДЕРЖАНИЕ

I. Теоритическая часть

1.1. История развития экономико-математического планирования.

В 1938-1939 гг. ленинградский математик (впоследствии академик, лауреат Ленинской, Государственных и Нобелевской премий) Л. В. Канторович в результате анализа ряда проблем организации и планирования производства сформулировал новый класс условно-экстремальных задач и предложил методы их решения. Так было положено начало новой отрасли прикладной математики линейному программированию. В более поздних работах Л. В. Канторович расширил область применения линейного программирования в социалистической экономике, сформулировав задачи отраслевого и народнохозяйственного оптимального планирования. А через два десятилетия после своего возникновения линейное программирование стало основным инструментом плановоэкономических решений на всех уровнях социалистического народного хозяйства.

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

Далее методы планирования продолжали совершенствоваться, но только развитие вычислительной техники в конце 50-х гг. позволило сделать плановые многовариантные расчеты достаточно распространенными. Важную роль в организации и пропаганде экономико-математических исследований в этот период сыграл академик В. С. Немчинов. Именно в эти годы получают развитие некоторые разделы прикладной математики, связанные с решением оптимизационных задач: линейное и нелинейное программирование, теория оптимального управления и др.

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

1.2. Классификация математических моделей

В основу классификации математических моделей  можно положить различные принципы. Можно классифицировать модели по отраслям наук (математические модели в физике, биологии, социологии и т.д.). Можно  классифицировать по применяемому математическому  аппарату (модели, основанные на применении обыкновенных дифференциальных уравнений, дифференциальных уравнений в частных  производных, стохастических методов, дискретных алгебраических преобразований и т.д.). Наконец, если исходить из общих  задач моделирования в разных науках безотносительно к математическому  аппарату, наиболее естественна такая  классификация:

• дескриптивные  (описательные)  модели;
• оптимизационные модели;
• многокритериальные модели;
• игровые модели.

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

1.3. Оптимизационные экономико-математические модели

1.3.1. Понятие оптимизационных задач и оптимизационных моделей.

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

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных  моделей (ОМ) методами математического  программирования.

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

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

Если  система ограничений несовместима, то область допустимых решений является пустой. Ограничения подразделяются на:

а) линейные (I и II) и нелинейные (III и IV) (рис.1);

Рис. 1. Линейные и нелинейные ограничения б)  детерминированные (А,В) и  стохастические (группы кривых) (рис. 2).

Рис. 2. Детерминированные  и стохастические ограничения

Стохастические  ограничения являются возможными, вероятностными, случайными.

Оптимизационные задачи решаются методами математического  программирования, которые подразделяются на:

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