15. ПАРАМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

15.1. Экономическая и геометрическая интерпретации задачи ПП. В математических моделях оптимизационных задач, рассмотренных ранее, все заданные коэффициенты были постоянными числами.

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

Рассмотрим зависимость данных задачи от некоторого параметра по отношению к канонической задаче ЛП.

1. Задача, в которой коэффициенты целевой функции линейно зависят от параметра t, заключаются в определении для каждого значения параметра t???,?? максимального значения функции

z=                                                           (1)

с условиями

=bi, i=1?m,                                                      (2)

xj?0, j=1?n,                                                                (3)

где , , aij и bi – заданные константы.

2. Если от параметра t линейно зависят правые части системы ограничений, то задача состоит в нахождении для каждого t???,?? максимума функции

z=                                                                       (4)

с условиями

=, i=1?m,                                                   (5)

xj?0, j=1?n,                                                                   (6)

где , aij, bi? и b??i – заданные константы.

3. Если от t линейно зависят и коэффициенты целевой функции, и свободные члены ограничений, то задача состоит в нахождении для каждого t???,?? максимума функции

z=                                                              (7)

с условиями

=, i=1?m,                                                  (8)

xj?0, j=1?n.                                                                  (9)

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

z=                                                            (10)

с условиями

=, i=1?m,                                       (11)

xj?0, j=1?n.                                                                      (12)

Решение этих задач можно найти методами ЛП, например, задачи (1) – (3). Пусть множество неотрицательных решений системы линейных уравнений (2) (многогранник решений или ОДР) не пусто и включает больше одной точки.