Постановка задачи целочисленного программирования.

По смыслу многих задач требуется, чтоб значения неведомых в рациональном плане выражались целыми числами. Это имеет место, когда разыскиваемыми величинами являются неразделимые объекты: поголовье скота, количество тракторов, тракторных агрегатов, автомашин, комплектов оборудования и т. д.

К обыкновенной формулировке задачки в этих случаях нужно добавлять условие целочисленности переменных. С таким дополнительным условием получим Постановка задачи целочисленного программирования. задачку целочисленного программирования. Она может быть как линейной, так и нелинейной. Разглядим решение линейной задачки.

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

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

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

Пусть требуется отыскать максимум функционала

(1)

при выполнении ограничений:

(2)

Условия неотрицательности переменных могут быть либо не быть, но все переменные должны выражаться целыми числами.

Если в системе (2) посреди Постановка задачи целочисленного программирования. коэффициентов ai}- и at есть дробные числа, то в каждом неравенстве приведем их к общему знаменателю и на этот знаменатель неравенство умножим. От этого смысл неравенства не нарушится, а все коэффициенты станут целыми. Потому, не нарушая общности, можно полагать все коэффициенты системы (2) целыми числами.

Приведем систему ограничений (2) к последующему Постановка задачи целочисленного программирования. виду:

(3)

Так как в системе (3) все коэффициенты и переменные целочисленны, значения переменных yi также окажутся целочисленными. Таким макаром, целочисленность переменных xj, независимо от того, будут они исключены из задачки либо нет, тянет за собой целочисленность переменных yt.Перевоплощенная в случае надобности задачка остается задачей целочисленного программирования.

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

Таблица 1

-y1 … -yl -xl+1 … -xn
x1= … xl= yl+1= … ym= b11 … b Постановка задачи целочисленного программирования.1l b1,l+1 … b1n ………………………………………… bl1 … bl bl,l+1 … bln bl+1,1 … bl+1,l bl+1,l+1 … bl+1,n …………………………………………. bm1 … bml bm,l+1 … bmn b1 ... bl bl+1 ... bm
z= q1 … ql ql+1 … qn Q


таблицы и в левом большем столбце ее будут стоять переменные обоих видов. По условию оптимальности плана все Постановка задачи целочисленного программирования. свободные члены b1,…,bm и коэффициенты z-строки q1,…,qn будут неотрицательными.

Если в приобретенной таблице все свободные члены целочисленны, то задачка решена. Если же посреди их есть хоть один дробный, части решение нужно продолжить.

Для удобства, последующих рассуждений обозначим все переменные, стоящие в левом большем столбце таблицы, эмблемой ( = 1, 2, ..., ), а все верхние Постановка задачи целочисленного программирования. переменные (j = 1, 2, ..., п). Тогда табл. 1 воспримет несколько другой вид (табл. 2).

Пусть дробным является свободный член bi. В этой же i-и строке посреди коэффициентов bij могут быть как целые, так и дробные. Обозначим буковкой п с надлежащими индексами наибольшее целое число, не превосходящее данный коэффициент. Так, к примеру, если Постановка задачи целочисленного программирования. bi = 1,7, то ni = 1; еслиbi1 = —1,4, то ni1 = — 2; если bi2 = 3, то и ni2 = 3 и т. д.

Таблица 2

- 1 … - … - n
= … = … = b11 … b1j … b1n ………………………………………… bl1 … bij … bin …………………………………………. bm1 … bmj … bmn b1 ... bi ... bm
z= q1 … qj … qn Q

Вычтем из каждого коэффициента i-й строчки его целую часть, обозначая Постановка задачи целочисленного программирования. разность буковкой , можем записать

(4)

Если коэффициент bijцелый, то nij = bij и соответственная разность bij равна нулю. Если же bij -число дробное, то разность bij будет правильной дробью. Так как nij как для положительных, так и для отрицательных коэффициентов всегда меньше bij, разность bij-nij положительна. Объединяя эти результаты, заключаем, что bij будет правильной Постановка задачи целочисленного программирования. положительной дробью либо нулем. Что все-таки касается разности , то она нулем быть не может, потому что biне является целым числом:

(5)

В силу критерий (5) величина , определяемая формулами (4), именуется дробной толикой соответственного числа b. Выпишем из табл. 2 выражение для :

Подставив сюда заместо bijи bi их выражения через Постановка задачи целочисленного программирования. целые и дробные части из формул (4), получим

либо

(6)

Перепишем равенство (6) в последующем виде:

Обозначим одну из частей буковкой si :

(7)

Установим, как будет вести себя величина si при обсужденных выше критериях.

Если и — целые числа, то в самой правой части выражения (7) будем иметь произведение целых чисел( ). Сумма таких произведений есть целое число, к ней алгебраически Постановка задачи целочисленного программирования. прибавляется еще два целых числа и , в конечном итоге получится целое число. Таким макаром, величина si будет целочисленной.

Так как и , в средней части выражения (7) имеем произведения неотрицательных чисел на отрицательные ( ); отрицательная сумма таких произведений будет положительным числом либо нулем. При прибавлении к хоть какому числу (в этом Постановка задачи целочисленного программирования. случае к ( )) положительного числа итог становится больше:

(от добавления нулевой суммы итог не поменяется, потому неравенство нестрогое). Отсюда .

Величина , согласно (5), есть верная положительная дробь. Точка ( ) на числовой оси расположится меж точками (—1) и 0 . Исследуемая величина si больше, чем ( ), и в то же время она целочисленна. Но меньшее целое число, большее Постановка задачи целочисленного программирования. ( ), есть нуль; как следует, si может принимать значения 0, 1, 2, 3 и т. д. Окончательный вывод: при всех целых неотрицательных и величина si будет принимать целые неотрицательные значения.

Введем в задачку дополнительное ограничение по первому равенству (7):

(8)

Коэффициентами в этом условии являются взятые с минусом дробные толики соответственных коэффициентов i-й строчки. Расширенную Постановка задачи целочисленного программирования. задачку запишем в табл. 3.

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

Таблица 3

- 1 … - … - n
= … = … = si= b11 … b1j … b1n ………………………………………… bl1 … bij … bin …………………………………………. bm1 … bmj … bmn - … - … - b1 ... bi ... bm
z= q1 … qj … qn Q

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

Для расширенной задачки обыденным методом отыскивается поначалу допустимый план, а потом – лучший. При использовании на этом шаге двоякого симплекс-метода положительность Постановка задачи целочисленного программирования. коэффициентов z-строки не нарушается и объем вычислений сокращается. Если в приобретенном плане снова окажется дробный свободный член, то по этой строке составляется новое дополнительное ограничение, задачка расширяется еще на одно условие и опять находится лучший план и т. д.

Потому что при целых неотрицательных и будет si целое Постановка задачи целочисленного программирования. неотрицательное, т. е. ,то существует хотя бы один набор целых , при котором si=0 . Это гласит о том, что гиперплоскость si=0 проходит по последней мере через одну целочисленную точку. Такая точка может и не принадлежать полиэдру. Но целочисленные точки полиэдра не отсекаются, и на каком-то шаге поначалу одна, а потом Постановка задачи целочисленного программирования. и другие дополнительные гиперплоскости пройдут через целочисленную точку, ближайшую к начальной хорошей верхушке (рис. 1). Эта точка через конечное число шагов непременно сама станет хорошей верхушкой. Потому можно утверждать, что построенный таким макаром метод конечен: через определенное число шагов находится лучший целочисленный план, если только такие планы имеются.

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

последующий: в какой-нибудь строке таблицы (не считая, естественно, z-строки) возникает дробный свободный член, а все остальные коэффициенты Постановка задачи целочисленного программирования. остаются целыми. Пусть это имеет место для i-й строчки табл. 2:

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

Несовместность начальной системы ограничений устанавливается по обыкновенному аспекту на исходной стадии решения задачки.

Аксиома:

Мотивированные функции основной и двоякой задач могут совпадать только для хороших планов.

Докажем аксиому Постановка задачи целочисленного программирования. поначалу на примере.

§2. Поиск целочисленного решения основной задачки.

Пример.

Доведем до целочисленного решения пример: отыскать максимум функционала (9) при критериях:

(10)

(11)

Составляем начальную таблицу и, сделав два шага измененных жордановых исключений, приходим к хорошему плану, записанному в табл. 4 .

Таблица 4

-y3 -y1 -x3
x2= y2= x1= -1/7 2/7 -1 -15/7 -5/7 -6 3/7 1/7 1 4/7 4/7 16/7
z= 5/7 4/7 4 36/7

Приобретенное среднее решение x1=16/7, x2=4/7, x3=0 нецелочисленно,

потому Постановка задачи целочисленного программирования. приступаем к отысканию целочисленного плана. Проведем его 2-мя способами: обыденным симплекс-методом и двояким.

Избираем посреди свободных членов дробный. Потому что в нашем

примере они все дробные, берем хоть какой из их, к примеру 4/7 из

первой строчки. По формулам (4) находим дробные толики коэффициентов b избранной первой строчки:

Дополнительное ограничение будет иметь Постановка задачи целочисленного программирования. вид

Вводим это ограничение в задачку и получаем табл.5.

План, записанный в таблице, стал недопустимым. Принимаем за разрешающий элемент число (-2/7), делаем шаг измененных жордановых исключений и приходим к таблице 6.

Отысканное решение допустимо и целочисленно, но, к огорчению, оно не нормально. Потому избираем разрешающий элемент (число 3) и делаем последующий Постановка задачи целочисленного программирования. шаг (табл.7).

Таблица 5

-y3 -y1 -x3
x2= y2= x1= s1= -1/7 2/7 -1 -15/7 -5/7 -6 3/7 1/7 1 -6/7 -2/7 0 4/7 4/7 16/7 -4/7
z= 5/7 4/7 4 36/7

Таблица 6

-y3 -s1 -x3
x2= y2= x1= y1= -1 1 -1 0 -5/2 -6 0 1/2 1 3 -7/2 0
z= -1 2 4

Сейчас решение нормально, но нарушилась его целочисленность. Берем дробный свободный член 2/3 опять в первой строке и по коэффициентам этой строчки формулируем аналогично предшествующему 2-ое дополнительное условие. Фактически оно составляется Постановка задачи целочисленного программирования. прямо в таблице, так как дробные толики коэффициентов просто рассчитываются в уме. Записывать их нужно со знаком минус (табл.8)

Таблица 7

-y1 -s1 -x3
x2= y2= x1= y3= 1/3 -1/6 -1 0 -5/2 -6 0 1/2 1 1/3 -7/6 0 2/3 2/3
z= 1/3 5/6 4 14/3

Таблица 8

-y1 -s1 -x3
x2= y2= x1= y3= s2= 1/3 -1/6 -1 0 -5/2 -6 0 1/2 1 1/3 -7/6 0 -1/3 -5/6 0 2/3 2/3 -2/3
z= 1/3 5/6 4 14/3

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

План, записанный в табл. 8, опять является недопустимым.

Избираем разрешающий элемент (-1/3) и делаем очередной

шаг (табл. 9). План, приобретенный в табл. 9, является Постановка задачи целочисленного программирования. допустимым, хорошим и целочисленным. Таким макаром, необходимое решение найдено: x1=2, x2=0, x3=0, zmax=4.

Типично, что таковой план у нас уже был в табл. 6, но там он оказался не хорошим. Это означает, что с одним дополнительным ограничением в полиэдре была еще верхушка

Таблица 9

-s2 -s1 -x3
x2= y2= x1= y3= y1= 1 -1 -1 0 -5/2 -6 0 1/2 1 1 -2 0 -3 5/2 0
z Постановка задачи целочисленного программирования.= 1 0 4

(2,2/3,0), доставлявшая функционалу большее значение, но

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

Применим сейчас для нахождения целочисленного плана двоякий симплекс-метод. Отличия начинаются с табл. 5. Принимаем в ней за Постановка задачи целочисленного программирования. разрешающую ту же четвертую строчку, но разрешающий элемент в ней определяем двоякими измененными отношениями. Они равны

5/7:(-6/7)=-5/6, 4/7:(-2/7)=-2;

меньше по модулю – 1-ое , потому за разрешающий принимаем элемент (-6/7). Делая с ним шаг измененных исключений, перебегаем от табл.5 к табл.10.

Таблица 10 тождественна табл. 7, которую мы получили из табл. 5 2-мя шагами. Так как целочисленный Постановка задачи целочисленного программирования. план не найден, составляем по первой строке дополнительное условие и вписываем его в строчку s2 табл. 10. Вычисляем для этой строчки двоякие измененные дела

5/6:(-5/6)=-1, 1/3:(-1/3)=-1.

Таблица 10

-s1 -y1 -x3
x2= y2= x1= y3= s2= -1/6 1/3 -1 -5/2 0 -6 1/2 0 1 -7/6 1/3 0 -5/6 -1/3 0 2/3 2/3 -2/3
z= 5/6 1/3 4 14/3

Они равны, но маленькая «прикидка» позволяет установить, что 2-ой столбец за разрешающий принять прибыльнее. Делая последующий шаг, получаем табл. 11 (тождественную Постановка задачи целочисленного программирования. табл. 9). в какой записан лучший целочисленный план. Двояким симплекс-методом он получен не 3-мя шагами, а 2-мя.

Таблица 11

-s1 -s2 -x3
x2= y2= x1= y3= y1= -1 -1 -1 -5/2 0 -6 1/2 0 1 -2 1 0 5/2 -3 0
z= 0 1 4


postanovlenie-plenuma-verhovnogo-suda-rf-ot-24-fevralya-2005-g-3.html
postanovlenie-plenuma-verhovnogo-suda-rossijskoj-federacii-4-ot-24-fevralya-2010-goda.html
postanovlenie-plenuma-verhovnogo-suda-rossijskoj-federacii-ot-22-noyabrya-2005-g-n-23.html