Глава 5. Модели линейного программирования.

Детерминированные модели.

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

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

Кроме того, к этому классу задач относятся задачи оптимизации размещения предприятий, календарного планирования, максимизация производительности поточной линии, планирование и обеспечение материально-технического снабжения и т. п. Более общий класс задач этого рода включает исследование механизма химических реакций, проектирование сетей связи, анализ электрических сетей, исследование потока сигналов и теория обратной связи, задачи проектирования электрических и монтажных схем, поиск в информационных системах, исследование движения транспорта и многое другое [8].

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

Глава 5. Модели линейного программирования.

Все задачи математического программирования сводятся к одной общей постановке: найти значения переменных х₁, х₂...... х_n, доставляющих max(min) заданной целевой функции F(х_1, х₂,..., х_n)и удовлетворяющих одновременно ряду условий:

g_i (x₁, x₂,...x_n) <> b_i; i = 1, 2 , ... , m; x_j > 0.

Эти условия называются ограничениям. Задача линейного программирования возникает, если целевая функция F и все ограничения g_i линейны относительно переменных х₁,х₂,..., х_n , т. е.:

; ;i=1,…,m. (5.1)