Лекция: Параметрическое программирование

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

Задача, в которой коэффициенты целевой функции линейно зависят от параметра t, заключается в нахождении для каждого значения параметра t из промежутка его изменения [a, b] максимального значения функции

при условиях

где c’j, c’’j, aij, bi – заданные постоянные числа.

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

где a, b – промежуток изменения значений параметра t ( ).

Решение задач (1)–(3), (4)–(7) можно найти методами линейного программирования, например, геометрически при j = 2.

Предположим, что в задаче (1)–(3) множество неотрицательных решений системы линейных уравнений (2) (многогранник решений) не пустой и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре tÎ[a, b] такой точки многогранника решений, в который функция (1) принимает max. Чтобы найти эту точку, будем считать t = t0и, используя геометрическую интерпретацию, находим решение полученной задачи линейного программирования (1)–(3), то есть определим вершину многогранника решений, в которой функция (1) имеет max, либо устанавливаем, что при данном значении t0задача неразрешима.

После нахождения точки, в которой при t = t0функция (1) принимает max, ищут множество значений t, для которых координаты этой точки определяют оптимальный план задачи (1)–(3). Найденные параметры t исключают из рассмотрения и берут некоторое новое значение t из промежутка [a, b].

Для выбранного значения параметра t из промежутка [a, b] либо находят оптимальный план, либо устанавливают неразрешимость задачи.