Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 49


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

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формулируется так: найти неотрицательные значения переменных х1, х2, ..., xn, которые удовлетворяли бы условиям-равенствам

      (8.1)

и обращали бы в максимум линейную функцию этих переменных:

L = c1x1 + c2x2 + ... + cnxn =>max.      (8.2)

Убедимся в этом. Uo-нерпых, случай, когда L

надо обратить не в максимум, а и минимум, легко сводится к предыдущему, если попросту изменить знак L на обратный (максимизировать не L, а L' = — L). Кроме того, от любых условий-неравенств можно перейти к условиям-равенствам ценой введения некоторых новых «дополнительных» переменных. Покажем, как это делается, на конкретном примере.

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

               (8.3)

и обращающие в максимум линейную функцию от этих переменных:

L = 4х1 – х2

+ 2х3 => max.            (8.4)

Начнем с того, что приведем условия (8.3) к стандартной форме, так, чтобы знак неравенства был

, а справа стоял нуль. Получим:

         (8.5)

А теперь обозначим левые части неравенств (8.5) соответственно через у1 и у2:

               (8.6)

Из условий (8.5) и (8.6) видно, что новые переменные у1, у2 также должны быть неотрицательными.

Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных х1, х2, х3, y1, у2 такие, чтобы они удовлетворяли условиям-равенствам (8.6) и обращали в максимум линейную функцию этих переменных (то, что в L не входят дополнительные переменные у1, у2, неважно: можно считать, что они входят, но с нулевыми коэффициентами). Перед нами — основная задача линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями-неравенствами (8.3) «куплен» ценой увеличения числа переменных на два (число неравенств).




Содержание  Назад  Вперед