Задача оптимизации: Линейное программирование, математическая модель

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

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

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

q_j £ x_j £ Q_j, где

где F – целевая функция;

a_ij, b_i – постоянные коэффициенты для уравнений;

c_j – постоянный коэффициент для целевой функции;

x_j – неизвестные переменные;

q_j, Q_j – ограничения, соответственно нижняя и верхняя границы для возможных значений x_j.

В процессе решения задачи необходимо определить численные значения x_j, которые лежали бы в пределах от q_j до Q_j доставляли бы экстремум целевой функции F.

Имитационное моделирование.

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

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

1. незаконченность математического аппарата или поставленной задачи для решения этой задачи.

2. математические модели имеются, но они настолько сложны и трудоемки, что имитационное моделирование дает более простое решение задачи.

3. когда кроме определения необходимых параметров необходимо наблюдение за процессом в течение определенного периода.

4. имитационное моделирование является единственно верным средством из-за трудностей проведения эксперимента в существующих условиях.