Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация, страница 6

Определим теперь задачу линейного программирования в наиболее общем виде. Определение 2,!. Пусть даны целочисленная (тхп)-матрица А со строками а;, М вЂ” множество индексов строк, соответствующих ограничениям в виде равенств, и М вЂ” множество индексов строк, соответствующих ограничениям в виде неравенств. Аналогично, пусть даны х Е Й", М вЂ” множество индексов, соответствующих ограниченным переменным, и У вЂ” множество индексов, соответствующих неограниченным переменным.

Тогда индивидуальная общая задача ЛП определяется следующим образом: в(п с'х ах=до (ЕМ, а)х) Ьо 1Е М, (2. 1) х,~)0, (с Л~, х,~~О, 1Е (у, где Ь и с — пелочисленные векторы длины соответственнот и я. г1 Пример 2.1(задача о диете), Задача о диете Ь(1) одной из первых была сформулирована в виде задачи ЛП. Рассмотрим задачу, с ко- торой сталкивается домохозяйка, покупая продукты. В ее распоря- жении имеется а названий продуктов, и каждый продукт содержит некоторое количество каждого из т питательных веществ. Пусть аы — количество Рго питательного вещества в единице 1чго продукза, 1=1,..., т, 1=1,..., и, г, — ежегодная потребность в Рм питательном веществе, 1=1,..., т, х~ — ежегодное потребление (что продукта в единипах, / - 1,...

сз — стонмосзь единицы 1'-го продукта, 1=1... а 2.1, Формы задачи линейного программировании Диета на !од определяется выбором вектора х)0. То, что диета удовлетворяет минимальным потребностям в питательных веществах, выражается неравенством Ах)г. Для того чтобы найти диету наименьшей стоимосчи, удовлетворяющую потребности в питательных веществах, нужно рассмотреть следующую задачу ЛП.' ш(п с'х, Ах) г, (2.2) х)0. [] ппп сх, Ах=Ь, х)0, (2.3) называется задачей ЛП в стандартной форме.

Наконен, задача вида (2.1) называется задачей .1!П в общей форме. [~ Докажем, что все формы: каноническия, спгандартноя и общая, в«вивалентны. Под этим мы понимаем го, что индивидуальную задачу в одной форме легко преобразовать в некоторую индивидуальную задачу в другой форме таким образом, что обе индивидуальные задачи будут иметь одно и то же решение. Каноническая и стандартная формы представляют собой частные случаи общей формы, поэтому нужно только показать, что задачу в общей форме можносформулпровагь в канонической и стандартной формах.

1. Чтобы задачу перевести из общей формы в каноническую, необходимо исключить все ограничения в виде равенств и неограничен. ные переменные. Если в задаче ЛП в общей форме имеется ограничение в виде равенства л' а,гх1 — — Ь„ ! ! то его можно заменить двумя ограничениями в виде неравенств Х а,гх1)Ь„ гм ! Х( — а,)х )( — Ь). ! Если в задаче ЛП в общей форме имеется неограниченная перемен- ная Форма задачи ЛП, полученная в задаче о диете, и форма, приведенная в гл. 1, являются достаточно общими и заслуживают специальных названий. Будем ипользовать следующую терминологию. Определение 2.2. Задача вида (2.2) называется задачей ЛП в канонической форме.

Задача вида (2,3) Гл. 2. Слмллекс.а»горио!м то в задаче ЛП в канонической форме можно ввести две переменные х! и хг и записать х =х',— х-;, где х+'=»О, х; )О. 2. Чтобы задачу перевести из общей формы в стандартную, нужно исключить ограничения в виде неравенств; неограниченные переменные можно исключить так же, как выше. Если в задаче ЛП в общей форме имеется ограничение в виде неравенства л Х а!тх,)Ьс, то в канонической задаче введем переменную з, и запишем л Х аых,— з, Ь„з!) О.

/= ! Переменная зо введенная при этом преобразовании, называвтся переменной избыгпка; она показывает, насколько левая часть неравенства превышает правую часть. Если при формулировке задачи ЛП мы получаем неравенство вида л Х а!!х!~Ьо ! ! то можно ввести переменную з, и записать л Х а„х,+ «;=Ьп з!)О.

! Такая переменная называется переменной недоотагпка. 2.2 Базисные допустимые решения Теперь перед нами стои1 цель — разработать симплекс-алгоритм для решения задачи ЛП. При этом удобно считать, что дана задача ЛП в стандартной форме ш!п с'х, Ах=Ь, (А — целочисленная (тхп)-матрица и т<а), х>0, что, согласно результатам предыдущего параграфа, не приводит к потере общности. Рассматривая пример 1.3, мы интуитивно убедились, что всегда должен существовать оптимальный «угол» в выпуклом допустимом множестве г" задачи ЛП. Есть два способа точного определения таких «угло⻠— один геометрический и один алгебраический.

Для то- 2.2. Базисные дояусшимые решения го чтобы дать алгебраическое определение, необходимо следующее предположение, которое, как мы увидим позднее, практически не ограничивает задачу. Предположение 2.1. В матрице А имеется т линейно независи- мых столбцов Ап т. е. ранг А равен т. Определение 2.3. Базисом матрипы А называется набор линейно независимых столбцов Я= (Аи,..., А,„). Можно также рассмат- ривать Я как невырожденную (тХт)-матрицу В=(А, ).

Базис- ным решением, соответствующим Я, называется вектор хЕР', в котором х=О при А (Я, х „есть й-я компонента вектора В Ь, где н=!...„т. () Таким образом, базисное решение х можно найти с помощью сле- дующей процедуры, 1. Выбрать множество Я линейно независимых столбцов в матрице А.

2. Положить все компоненты вектора х, соответствующие столбцам, не входящим в Я, равными О. 3. Решить т полученных уравнений для определения оставшихся компонент вектора х. Они будут называться базисными переменными. Пример 2.2. Рассмотрим задачу ЛП ппп 2х,+ х„+5х„, х,+ х,+х,+х, =4, хг +х, =-2, х, +х„=З, Зх,+х, +х,=б, хп хы хм х4 хм х~, хуЪО, Одним базисом здесь, естественно, является базис Я= (А„А„А„ А,), который соответствует матрице В=В Соответствующее базис- ное решение имеет вид х=(О, О, О, 4, 2, 3, 6).

Другим базисом будет Я'= (А„А„, А„А,) с базисным решением х'= (О, 4, О, О, 2, 3, — 6). Заметим, что х' не является допустимым решением, так как х',<О. Можно найти верхнюю опенку абсолютной величины компонент любого базисного решения, используя наше предположение о том, что элементы матрицы А и векторов Ь и с суть целые числа. Лемма 2.1. Пусть х=(х„.. „х„) — базисное решение.

Тогда (х ((т1а 'р, еде а=шах(1а, 1) и р= гпах 11Ь Ц. и~ Г=ц ...,ы 2 м 3032 Гл. 2. Симплекс-алгорппм Доказательство. Утверждение справедливо для тех переменных х,, которые не являются базисными, поскольку в этом случае х;=О. Напомним, что базисная переменная х! является суммой т произведений элементов матрицы В ' на элементы аскара Ь, По определению обратной матрицы каждый элемент матрицы В ' равен определителю порядка (т — 1) х (т — 1), деленному на отличный от нуля определитель порядка тхт.

Так как знаменатель — целое число, его абсолютная величина не меньше 1. Определитель, стоящий в числителе, есть сумма (т — 1)! произведений т — ! элементов матрицы А. Следовательно, его абсолютная величина не превосходит (т — !)! а '. Поскольку каждое ху есть сумма т элементов матрицы В ', умноженных на элементы вектора Ь, то ) х ) ( т! а '6. Е) Эта оценка будет неоднократно использоваться в дальнейших рассуждениях.

Определение 2.4. Если базисное реп~ение х лежит в Р, то х называется базисным допустимым решением (бдр). Например, в.задаче ЛП в примере 2.2 вектор х=(0, О, О, 4, 2, 3, 6) есть бдр. Базисные допустимые решения играют центральную роль как в теории, так и в вычислительной практике линейного программирования. Один из аспекгов пх важности выражен в следующей лемме, утверждающей, что все базисные допустимые решения суть потенциальные однозначные оптимальные решения подходящей задачи ЛП. Лемма 2.2. Пусть х есть бдр задачи Ах=Ь, х)0, соответсгтеующее базису Я.

Тогда существует вектор стоимости с, такой, что х является единапвенным оптимальным решением зада. чи ЛП ш!и с'х, Ах=Ь, х'.О. Доказательство. Определим вектор с следующим образом! ~ О, если АТЕЯ, ~т ( 1, если Ат(З. Стоимость бдр х равна с'х=О. Очевидно, х — оптимальное решение, поскольку все сг неотрицательны, Более того, если любое другое допустимое решение у также имеет нулевую стоимость, то в нем долж- 2.2. Базисные допустимые решения но быть у!=О для всех А; ( Я. Следовательно, у должно совпадать с х, т.

е. х — единственное оптимальное решение. ! ! Совсем не очевидно, однако, что любая задача ЛП обладает ба. зисиыми допусчимыми решениями. Например, если г"=Я, то, естественно, не может быть бдр Удобно, однако, пока исключить этот патологический случай. Позднее мы вернемся к нему и увидим, как можно убрать это предположение. Предположение 2.2. Множество Р допустимых точек не пусто. Теперь можно показать, что базисные допустимые решения обязательно существуют. Теорема 2.1. При предположениях 2.1 и 2.2 существует по крайней мере одно бдр.