Многостадийный процесс
Многостадийные процессы – это такие процессы, в которых решения принимаются на каждой из последовательных стадий.
При постановке и решении задачи формулируется некоторый критерий, подлежащий удовлетворению, рассматриваемый процесс разбивается на стадии во времени или в пространстве и на каждой стадии принимаются решения, при которых достигается поставленная цель.
При рассмотрении вопросов динамического программирования принята следующая терминология:
а) стадия – единичный элемент, на которые делится весь процесс во времени или в пространстве; ступень – часть стадии. В любом случае стадия и ступень – это математические конструкции, применяемые для представления в дискретном виде непрерывной переменной;
б) состояние системы характеризуется совокупностью переменных, последние описывают состояние системы на любой стадии процесса;
в) переход от стадии к стадии и от состояния к состоянию описывается функциональными уравнениями;
г) стратегия определяется системой решений функционального уравнения; оптимальная стратегия выражается системой функций, максимизирующих правую часть уравнения.
Стадии процесса могут быть однородными и неоднородными. Процесс с однородными стадиями представляет собой последовательное изменение состояния объекта во времени, он состоит из последовательности однотипных стадий.
Процесс с неоднородными стадиями состоит из разнородных стадий. Состояние отдельной стадии характеризуется совокупностью величин, которые называются выходом или переменными состояния стадии. Если выход стадии является входом для следующей стадии, то для последней совокупность выходных переменных предыдущей стадии определяет состояние входа.
Кроме входных и выходных переменных на каждой стадии определяется группа управляющих переменных (управление), а также предполагается известным математическое описание каждой стадии.
Рассматриваемый многостадийный процесс условно изображается функциональной схемой, изображенной на рисунке .
Рисунок 2. Функциональная схема
Задача линейного программирования
Перед решением задачи составляем её математическую модель.
Математическая модель – это совокупность соотношений состоящие из линейной целевой функции и линейных ограничений на переменную.
Принцип составления математической модели.
Выбирают переменные задачи.
Переменными
задачи называются величины
которые полностью характеризуют
экономический процесс, описанный в
задачи. Обычно записываются в виде
вектора X
= (
)
Причём
)
Составляют систему ограничения задачи.
Система ограничений – это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.
В общем виде система записывается в виде
(1)
Задают целевую функцию.
Целевая
функция – это функция Z(X)
которая характеризует качество выполнения
задачи, экстремум которой надо найти.
В общем виде целевая функция записывается
Z(X)
=
(max,
min)
т.о. математическая модель имеет вид найти переменные задачи
удовлетворяющие
системе ограничений:
(2)
и
условию неотрицательности
0 (j
=
),
которая обеспечивает экстремум целевой
функцииZ(Y)
=
Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.
Множество допустимых решений образует область допустимых решений задачи (ОДР).
Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума.
Каноническая форма задачи линейного программирования
Математическая модель задачи должна иметь каноническую форму.
Если система ограничения состоит только из уравнения и все переменные удовлетворяют условию неотрицательности, то задача имеет каноническую форму.
Если в системе есть хотя бы одно неравенства или какая–либо переменная неограниченна условию неотрицательности, то задача имеет стандартную форму. Чтобы привести задачу к каноническому виду надо:
перейти
от неравенств к уравнению следующим
образом: в левую часть неравенств вводим
дополнительную переменную с коэффициентом
(+1) для неравенства (
)
и (-1) для неравенства (
)
дополнительные переменные не наложены
целевые неотрицательности, то её заменяют
разностью двух неотрицательных
переменных, то есть:
=
–
(
(3)
Общий вид канонической формы:
(4)
Решение задачи линейного программирования симплекс-методом
Симплекс-метод известен с 1947 года, когда появилась первая публикация Джона Данцига, посвященная этому методу. В советской литературе 60-80-х гг. прошлого столетия этот метод был известен также как метод последовательного улучшения плана.
За прошедшие с тех пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности различных подклассов задачи ЛП (блочные задачи, задачи со слабо заполненной матрицей условий A ={ai, j}), но и несколько принципиально иных методов решения задачи ЛП. Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят симплекс-метод (известно, что симплекс-метод обладает экспоненциальной сложностью, т.е. имеет экспоненциальную оценку трудоемкости на всем классе задач ЛП, тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя) характеризуются полиномиальной сложностью). И, тем не менее, по утверждению многих специалистов в теории линейного программирования симплекс-метод и после десятилетий всесторонней апробации с точки зрения алгоритмической реализации и универсальности применимости на классе задач ЛП остается наиболее предпочтительным, а потому наиболее распространенным методом решения задач ЛП.
Симплексный метод – это метод последовательного улучшения плана (решения), наиболее эффективный и применяется для решения любой задачи линейного программирования.
Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.
Симплексный метод позволяет за конечное число шагов либо найти оптимальное решение либо доказать что его нет.