Параметрическое линейное программирование - Методы линейного программирования

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

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

Если обратиться к геометрической интерпретации задачи, то можно заметить, что вектор-градиент линейной формы определяется ее параметром. Например, для целевой функции L(X, л) = лX1 + (1-л)X2 при различных значениях параметра л градиент определяет различные направления роста функции.

Нетрудно видеть, что, если при некотором значении параметра максимум достигается в вершине A, то небольшая вариация этого значения несколько изменит направление градиента, но не изменит положение точки максимума. Отсюда, что некоторый оптимальный при л = л0 оптимален и в окрестности л0, т. е. при б ? л ? в где л0 [б, в].

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

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

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

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

Предприятие должно выпустить два вида продукции А и В, для изготовления которых используется три вида сырья, нормы расходов заданы в таблице. Известно, что цена на А единицу продукции может изменяться от 2 до 12 у. е., для В от 13 до 3 у. е. Найти оптимальные планы выпуска для заданных интервалов цен.

А

В

ЗАПАСЫ

1

4

1

16

2

2

2

22

3

6

3

36

Обозначим через Х1 количество единиц продукции А, через X2 -- количество единиц продукции В. Матема­тическая модель задачи имеет вид

При ограничениях:

Область допустимых решений -- многоугольник OABCD (рис. 25.2). Полагая л = 0, L() = 2X1 + 13Х2 строим (2, 13). Перемещая линию уровня по направлению, находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким образом, при л = 0 1опт(0, 11), L(1)Max = 143.

Если уравнение прямой имеет вид

При ограничениях

Область допустимых решений -- многоугольник OABCD (рис. 25.2). Полагая л = 0, L(Х) = 2X1 + 13Х2 строим (2, 13). Перемещая линию уровня по направлению С, находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким образом, при л = 0 х 1опт(0, 11), L(1)Max = 143.

Если уравнение прямой имеет вид

То угловой коэффициент равен K = - А/В.

Угловой коэффициент линии уровня, перпендикулярной С, При произвольном значении л равен K = (2 + л) / (13 - л).

Найдем область оптимальности Х 1опт: Х 1опт будет оставаться оптимальным для всех л, при которых соответствующая линия уровня находится внутри угла, образованного прямыми X1 = 0 и (25.2). Угловой коэффициент прямой (25.2) K = - 2/2 = -1. По условию л1 = 0, л2 = (2 + л) / (13 - л) = -1, откуда л2 = 11/2. Решение Х 1опт остается оптимальным при л Э [0, 11/2].

При л = 11/2 линия уровня совпадает с прямой (25.2) и оптимальными будут все точки, лежащие на прямой (25.2), в том числе и точка В(1, 10), лежащая на пересечении прямых (25.2) и (25.3).

Оптимальное решение будет сохраняться до тех пор, пока при изменении л линия уровня не совпадет с прямой (25.3), что будет соответствовать новому оптимальному решению 2опт. Найдем новый диапазон изменения л: л1 = 11/2, л2 = (- 2 + л) / (13 - л) = -2, так как K3 = -2. Откуда л2 = 8.

Получили при л Э [11/2, 8] Х 2опт = (1, 10), L( х 2)Max = 132 - 9л.

Аналогично определяем, что при л Э [8,10], Х 3опт = (2, 8), L( Х 3)mах = 108 - 6л.

Таким образом, при л = [0, 11/2] необходимо производить только 11 изделий В, при этом стоимость продукции будет максимальной и равной (143 - 11л) усл. ед.; при л Э [11/2, 8] необходимо производить одно изделие А и 10 изделий В, при этом стоимость продукции является максимальной и равной (132 - 9л) усл. ед.; при л Э [8, 10] необходимо производить 2 изделия А и 8 изделий В, при этом стоимость продукции будет максимальной и равной (108 - 6л) усл. ед.

Найдем решение этой же задачи симплексным методом (табл. 25.2-25.4), для чего приведем задачу к каноническому виду:

При ограничениях:

Получим л1 = -, так как все Д"J ? 0;

Таким образом, л э [0, 11/2], Х 1опт = (0, 11, 5, 0, 3), L( Х 1)max = 143 - 11л.

Получим:

Таким образом, л Э [8, 10],Х 3опт = (2, 8, 0, 2, 0), L(Х 3)mах = 108 - 6л.

Получили следующие оптимальные решения в зависимости от диапазона изменения л:

Список литературы

    1. Волков С. И. Землеустройство. Экономико - математические методы и модели. 2002 год. 2. Кундиус. Математические методы в экономике и моделирование социально-экономических процессов в АПК. 2001 год. 3. Полунин. Математическое програмирование в землеустройстве. 1972 год.

Похожие статьи




Параметрическое линейное программирование - Методы линейного программирования

Предыдущая | Следующая