Методы и способы решения задач целочисленного параметрического программирования (стр. 4 из 15)

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

Общая задача линейного программирования содержит постоянные величины: коэффициенты

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

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

3.1 Задача с параметром в целевой функции

Предположим, что коэффициенты линейной функции

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

Дана линейная функция

(3.1.1)

и система линейных ограничений

(3.1.2)

Считая значение параметра

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

В результате при данном значении

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

Для всех

задача имеет один и тот же оптимальный план, что и при .

В том случае, если задача при

неразрешима, – в строке последней симплекс - таблицы ее решения имеется число , где . Тогда:

1) если

, то задача неразрешима для любого ;

2) если

, то задача неразрешима для всех ;

3) если

, то задача неразрешима для всех .

Определив все значения параметра

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

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

Процесс нахождения решения задачи включает следующие этапы:

1. Считая значение параметра

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

2. Определяют множество значений параметра

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

3. Полагают значения параметра

равным некоторому числу, принадлежащему оставшейся части промежутка , и находят решение полученной задачи линейного программирования.

4. Определяют множество значений параметра

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

Пример 3.1.1. Для всех значений параметра

найти максимальное значение функции

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

Решение. Возьмем (число 0 выбрано произвольно) и найдем симплекс-методом оптимальный план.

Таблица 3.1.1.

БП	СЧ
	12	1	1	1	0	0
	10	1	-1	0	1	0
	6	-1	1	0	0	1
С	0	-2		0	0	0

Таблица 3.1.2.