§6. Параметрическое программирование.

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

(6.1)

при условиях:

или краткой форме:

,

заданные постоянные.

Задачу решают в следующем порядке.

1. Пользуясь симплекс-методом, решаем задачу (6.1) – (6.3) при до получения оптимального плана.

Коэффициенты линейной формы равны:

(6.4)

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

(6.5)

Тогда

(6.6)

что означает совместность всей системы неравенств

(6.7)

Решение задачи (6.1) – (6.3) , полученное при , является оптимальным для всех значений параметра, удовлетворяющих условию

где

(6.8)

( 6.9)

Здесь возможны следующие случаи:

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

б) , при . Если все, то линейная форма (6.1) прине ограничена снизу. Полученный план приостается оптимальным для всех значений параметра;

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

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

Величины называют критическими значениями параметра, а оптимальные планы, соответствующие различным значениям– критическими решениями.

2. Пользуясь симплекс-методом, можно убедиться, что при линейная форма не ограничена снизу на выпуклом множестве, определяемом условиями (6.2).

Здесь возможны следующие случаи:

а) – вектор, подлежащий вводу в базис, , всеЕсли, то линейная форма задачи не ограничена снизу для любого

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

Пусть, тогда этот план является решением задачи при, а далее решение продолжается так же, как в случае (а).

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

Если для всех j, встречаем случай (а).

Если , линейная форма задачи не ограничена снизу при всех.

Если , то линейная форма при, где’ >, не ограничена снизу.

Глава 2. Динамическое программирование.

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

Покажем принцип метода динамического программирования на модели эффективного использования ресурсов.

Имеется некоторое количество ресурса , которое можно использовать различными способами. Пусть– количество ресурса, используемое-м способом,– доход от использования ресурса-м способом (). Требуется распределить общее количество ресурсамежду различными способами, чтобы суммарный доход был максимальным.Математически задача выразится следующим образом.

Найти

(10.1)

при условиях:

(10.2)

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

Зададим последовательность функций , определенных дляследующим образом:

(10.3)

где

Очевидно,

Существует рекуррентное соотношение

(10.4)

для

Вывод этого соотношения основан на принципе оптимальности Беллмана.

Очевидно,

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

Примечания.

1. Наряду с решением исходной задачи получают решения целого семейства сходных между собой задач.

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

Схема решения задачи [10.1] –[10.2]

1. Находят функции и.

2. Строят рекуррентное соотношение.

3. Находят функции и.

4. Выбирают значения – максимальное значение целевой функции- значение переменнойв решении.

5. Остальные переменные получают следующие значения:

Пример

при условиях:

Решение. Для построения рекуррентного соотношения обозначим ,. Построим последовательность функций

Легко видеть, что при , а при.

Запишем значения функций ипри дискретных целых значениях из заданного интервала

Построим рекуррентное соотношение, связывающее функции и:

Поскольку записать данную функцию в явном виде сложно, вычислим ее значения при дискретных значениях х:

Здесь минимальное значение выбрано из двух выражений – при ии достигается при=1.

Находим

Следовательно, решение данной задачи следующее .