Оснавная задача линейного программирования

Основная задача линейного программирования состоит в следующем. Задана система

(6.10)

m линейных алгебраических уравнений с n неизвестными x₁,...,x _n и линейная форма относительно этих же неизвестных:

F = c₁x₁ +... + c_nx_n. (6.11)

Требуется среди всех неотрицательных решений системы (10) выбрать такое, при котором форма F принимает наименьшее значение (минимизируется).

Определение: Система (6.10) называется системой ограничений данной задачи.

Сами равенства (6.10) называются ограничениями-равенствами. Отметим, что кроме ограничений-равенств в основу задач входят также ограничения-неравенства x₁≥0,...,x_n≥0

Определение: Всякое неотрицательное решение x₁⁽⁰⁾,...,x_n⁽⁰⁾(x_i⁽⁰⁾≥0; i=1,...,n) системы (6.10) назовем допустимым. Допустимое решение часто называют планом задачи линейного программирования.

Определение: Допустимое решение системы (6.10), минимизирующее форму F, назовем оптимальным.

Рассмотрим следующие ограничения системы (6.10).

Задача имеет смысл лишь в том случае, когда система (6.10) совместна, то есть когда (согласно теореме Кронекера-Капелли) ранги основной и расширенной матриц системы совпадают. Этот общий ранг r не может превосходить числа n неизвестных. При r= n решение x₁⁽⁰⁾,...,x_n⁽⁰⁾ системы (6.10) единственно. Если это решение допустимо, то оно является оптимальным, так как никаких других решений вообще нет. Если же среди чисел x_i⁽⁰⁾ имеется хотя бы одно отрицательное, то задача не имеет решения.

Таким образом, интерес представляет лишь случай r < n, и только он будет нами рассматриваться в дальнейшем.

Каждую задача линейного программирования можно свести к форме основной задачи. Для этого нужно:

1. Уметь сводить задачу максимизации к задаче минимизации.

2. Уметь переходить от ограничений, заданных в виде неравенств, к некоторым им эквивалентным ограничениям-равенствам.

Покажем, как это сделать.

1. Очевидно, что форма F достигает наибольшей величины при тех же самых значениях неизвестных x₁⁽⁰⁾,...,x_n⁽⁰⁾, при которых форма F₁ = -F достигает наименьшей величины. Следовательно, максимизация формы F равносильна минимизации формы F₁ = -F. Тем самым задача максимизации сводится к задаче минимизации.

2. Допустим теперь, что среди ограничений задачи имеется некоторое неравенство. Его всегда можно записать в виде

a₁x₁ + a₂x₂.+... + a_nx_n + β ≥ 0 (6.12)

Введем новую, так называемую добавочную, неизвестную, связанную с неизвестными x_1,...,x_n уравнением

x_{n+1 =} a₁x₁ + a₂x₂.+... +a_nx_n + β. (6.13)

Очевидно, что условие неотрицательности величины x_n+1 эквивалентно выполнимости неравенства (6.12). Иными словами, если система x₁⁽⁰⁾,...,x_n⁽⁰⁾,x_n+1⁽⁰⁾ неотрицательных значений x_1,...,x_n,x_n+1 удовлетворяет уравнению (6.13), то система x₁⁽⁰⁾,...,x_n⁽⁰⁾ удовлетворяет неравенству (6.12). И обратно, если величины x₁⁽⁰⁾,...,x_n⁽⁰⁾ неотрицательны и удовлетворяют неравенству (6.12), то величина x_{n+1 =} a₁x₁ + a₂x₂.+... +a_nx_n + β, найденная из уравнения (6.13), окажется неотрицательной.

Итак, ограничение-наравенство (6.12) эквивалентно ограничению-равенству (6.13). Следовательно, ценою введения в задачу добавочных неизвестных удается все ограничения-неравенства заменить ограничениями-равенствами. При этом число добавочных неизвестных равно числу ограничений-неравенств в исходной задаче.

Поиск по сайту: