Способ построения правильных отсечений гарантирующий конечность процедуры решения

Методы отсечения

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

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

(3.23)

x₀ ≡ = max;

(3.25)

(3.24)

= b_j; i = 1, 2, . m;

(3.26)

x_j ³ 0; j = 1, 2, . n;

При n₁ = n задача (3.23) – (3.26) является полностью, а при n₁ ц . Для сокращенного обозначения задачи (3.23) – (3.26) применяется запись (L ц , c), где с – вектор-столбец, состоящий из элементов с_i. Оптимальное решение или оптимальный план обозначается через х (L ц , c). Наряду с оптимальным планом x_опт = = (x_1опт, x_2опт, . x_nопт) будет рассматриваться расширенный оптимальный план

x₀ =.

Сокращенно оптимальный расширенный план обозначается как

х‘ (L ц , c).

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

Основная идея методов отсечения заключается в построении такой эквивалентной задачи линейного программирования (А, с), при которой исходная задача целочисленного программиро-вания (L ц , c) сводится к ее решению. Иногда это называют линейной аппроксимацией целочислен-ного программирования (L ц , c).

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

х (L, c) Ë L ц .

(3.27)

Математически правильное отсечение означает выбор такого числа β, при котором неравенство

выполняется при условиях

(3.28)

ах(L, c) > β;

(3.29)

<х (L ц , c)|ах Ј β> Ì L ц ,

где а – вектор-строка, состоящая из элементов.

Метод отсечений позволяет построить процедуру последовательного выделения оптимального решения целочисленной задачи по известному решению соответствующей линейной задачи, в которой исключены требования целочисленности. Эта процедура решения задачи (L ц , c) может быть описана следующим образом:

1. На k-м этапе решается вспомогательная задача линейного программирования (L_k, c), k = 0, 1, 2, где L₀ = L.

2. Если на k-м этапе оптимальное решение x(L_k, c), удовлетворяет условию целочисленности, то оно будет также оптимальным решением x(L₀ ц , c) исходной задачи (L₀ ц , c), так как на всех этапах множества целочисленных точек совпадают, т.е.

что является специальным условием при отсечении.

3. Если на k-м этапе решение не удовлетворяет условиям целочисленности, то x(L_k, c) не является оптимальным решением исходной целочисленной задачи. В этом случае переходят от k-го этапа к (k + 1)-му, добавляя к линейным ограничениям задачи (L_k, c) условие правильного отсечения

(3.30)

a k x≤ β k ,

которое превращает многогранник (множество) L_k в многогранник L_k+1. Каждый конкретный метод имеет свой способ задания отсечения, но в алгоритмах Гомори гарантируется конечное число процедур.

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

Источник

Метод Гомори

Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.

Рубрика	Математика
Вид	курсовая работа
Язык	русский
Дата добавления	25.11.2011

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

Первый методов решения целочисленной задачи линейного программирования отсечением был предложен Гомори и получил название алгоритма Гомори.

1. Постановка задачи

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

1.1 Каноническая форма

Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности:

Условие целочисленности существенно осложняет задачу линейного программирования (1.1), (1.2). Так может случиться, что задача (1.1)-(1.3) обладает допустимыми (целочисленными) планами, целевая функция ограничена на допустимом множестве, однако ее максимум не достигается. Например в задаче:

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

В связи со сказанным, при обосновании численных алгоритмов решения задач типа (1.1)-(1.3) приходится накладывать различные дополнительные условия.

I. Будем считать, что множество X планов задачи (1.1), (1.2) (без условия целочисленности) ограничено, то есть является многогранником.

Из этого условия вытекает, что множество X * всех целочисленных планов задачи (1.1)-(1.3) конечно.

II. Будем предполагать, что все коэффициенты c_j, j=1, 2, …, n, целевые функции — целые числа.

Из условия II вытекает, что для всякого целочисленного плана x X * значение максимизируемой линейной формы — целое число. В этом случае говорят, что гарантирована целочисленность целевой функции.

Хотя условия I и II на задачу (1.1) — (1.3) довольно жесткие, ослабить их, для получения необходимых результатов, можно лишь немного.

1.2 Приведение к канонической форме

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

От подобной записи к (1.2) можно перейти, прибавив к каждому уравнению по одной новой переменной, тогда ограничения примут вид

Добавленные переменные будут иметь нулевой вес в целевой функции.

Отметим, что для получения, в зависимости от вида неравенства, следует не только прибавлять, но и вычитать переменную в зависимости от знака неравенства, учитывая условие (1.3).

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

2. Общие идеи методов отсечения

Существует принципиальная возможность свести решение задачи (1.1) — (1.3) к нахождению оптимального плана некоторой задачи линейного программирования (без условия целочисленности переменных). Пусть X — многогранное множество, определяемое условиями (1.1), (1.2). Через X * обозначим множество всех целочисленных векторов x * , лежащих в X. Другими словами X * задается условиями (1.1)-(1.3), т.е.

По определению X * X. Будем обозначать через X z выпуклую оболочку множества X * . Тогда X z X.

Таким образом, мы сопоставили многогранному множеству X некоторое выпуклое множество X z X согласно следующему правилу: X z есть минимальное выпуклое множество, содержащие все целочисленные векторы из X.

По предположению I, X является многогранником, следовательно множество X * конечно. Тогда выпуклое множество X z так же является многогранником, а следовательно, имеем, что X z можно задать конечным числом линейных неравенств.

Чтобы подчеркнуть основное отличие множества X z от множества X, дадим следующее определение.

Определение 1. Многогранник, все крайние точки которого целочисленны (т.е. все их координаты целые числа), называются целочисленным многогранником.

Очевидно, что многогранник X z — целочисленный, по скольку его крайними точками являются лишь точки множества X * целочисленных планов.

Оправданием для изучения соответствия X X z является следующий простой факт.

Теорема 1. Любой оптимальный опорный план задачи линейного программирования является решением задачи (1.1)-(1.3).

Доказательство. Пусть x * — оптимальный опорный план задачи (2.1), x * — какое то решение исходной задаячи (1.1)-(1.3). x * X z X, то

С другой стороны, так как x * — целочисленный план, то x * X * X z , и поэтому

Доказательство теоремы закончено.

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

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

Изложим идею методов отсечения. Допустим, что удалось построить последовательность <L_r>, r = 0, 1, 2, …, задач линейного программирования, каждая из которых определяется своим многогранником X_r и одной для всех целевой функцией :

при чем эта последовательность задач обладает следующими свойствами:

3) если при решении задачи L_r полученный оптимальный вектор x_r * не удовлетворяет условию целочисленности, то он не является планом задачи L_r+1, т.е. x_r * X_r+1.

Отметим, что если на каком то шаге r вектор x_r * — решение задачи L_r — оказался целочисленным, то он является решением исходной задачи (1.1)-(1.3) в силу свойства 2) последовательности L_r.

Интуитивно ясно, что последовательное построение задач L_r, r=1,2, …, дает в некотором смысле аппроксимацию множества X z с помощью множества X_r.

Способы построения последовательности <L_r>, обеспечивают конечность процесса решения задачи (1.1)-(1.3), были впервые предложены Гомори.

3. Описание метода Гомори

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

3.1 Понятие правильного отсечения и простейший способ его построения

алгоритм гомора линейное программирование

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

Определение 2. Пусть x* — оптимальный план задачи (1.1), (1.2), не являющийся целочисленным. Неравенство

где = (₁, ₂, …, _n), называется правильным отсечением, если оно удовлетворяет требованиям:

а) для вектора x * неравенство не выполняется, т.е. * > ₀ (условие отсечения).

б) если x — целочисленный план задачи (1.1), (1.2) ( т.е. план задачи (1.1)-(1.3)), то x — удовлетворяет (3.1) (условие правильности).

Понятно, что добавление неравенства (3.1) к условиям (1.1), (1.2) сужает допустимое множество X, сохраняя при этом все его целочисленные точки. Тем самым последовательное применение этого приема дает как бы многоэтапную аппроксимацию многогранника X z с помощью линейных ограничений.

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

Отметим, что второе требование является довольно тонким. В качестве подтверждения рассмотрим способ построения правильного отсечения, предложенный Данцигом.

Пусть x * — опорный оптимальный план задачи (1.1), (1.2), и — списки номеров соответственно базисных и не базисных переменных, отвечающих некоторому базису плана x * . Тогда x_j * = 0 при j. С учетом этого свойства нетрудно построить правильное отсечение для плана x*, если он является не целочисленным: в качестве такого может служить неравенство

В самом деле, условие отсечения тривиально выполняется, поскольку . Условие правильности так же соблюдено, так как если x = (x₁, x₂ , …, x_n) — целочисленный план задачи (1.1), (1.2), то величина с учетом условий x_j 0, j , может быть меньше единицы лишь в том случае, когда x_j = 0 при всех j . Но в таком случае план x — опорный, и в качестве его базиса можно принять базис плана x * . Опорный план однозначно определяется своим базисом, откуда получаем, что из неравенства вытекает x=x * . Последнее, однако, невозможно, так как x — целочисленный вектор, а x * таковым не является.

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

3.2 Построение правильного отсечения методом Гомори

Опишем способ построения правильного отсечения, предложенный Гомори. Для произвольного числа , через [ ] будем обозначать его целую часть, т.е. [ ] есть наибольшее целое число k непревосходящее число .

Дробной частью > числа называется число > = — [ ]. Отметим очевидное свойство дробной части произвольного числа: 0 > * — опорное решение задачи (1.1), (1.2), не являющееся целочисленным, — его базис и B — соответствующая симплекс-таблица в координатной форме.

Рассмотрим приведенную систему уравнений, отвечающую данному базису (и таблице B) плана

Пусть s — такой индекс ( 0 s n ), что число x_s * — не целое. Рассмотрим s-ю строку в симплексной таблице B (s-е уравнение в системе (3.2), (3.3)) и составим выражение

Теорема 2. Если xX * — целочисленный план задачи (1.1), (1.2), то

Доказательство. Используя соотношение

В левой части данного неравенства стоит целое число, следовательно, число

также целое. Из того, что x_j 0, j, используя свойство дробной части, получаем

Следствие. Если x_s * ( = _s0 ) — нецелое число и Множество X * планов целочисленной задачи (1.1)-(1.3) непусто, то среди чисел _sj>, j=1, 2, …, n, есть положительные.

В самом деле, все числа _sj>, очевидно неотрицательны. Допустим, что _sj> = 0, j = 1, 2, …, n.

Теорема 3. Если число x_s * — нецелое, то неравенство

является правильным отсечением.

Доказательство. Проверим условие отсечения в определении 2. Так как x_s * = _s0, то из того, что x_s * — нецелое, получаем неравенство _s0> > 0. Поскольку x_j * = 0 при j , то

и поэтому вектор x * не удовлетворяет неравенству (3.5). Условие правильности следует из утверждения z_s(x) 0 в теореме 2.

3.3 Первый алгоритм Гомори

Перейдем к изложению первого алгоритма Гомори.

Обозначим задачу (1.1), (1.2) через L₀. Гомори предложил на первом этапе своего алгоритма находить лексикографический максимум задачи L₀. Будем обозначать через

(n+1)-мерный вектор такой, что (x₁(0), x₂(0), …, x_n(0)) — решение лексикографической задачи L₀, а x₀(0) = — значение линейной формы. В тех случаях когда это не вызывает недоразумения, будем называть x(0) — оптимальным планом лексикографической задачи L₀ (хотя по общепринятой терминологии планом называется вектор, составленный из последних n координат вектора x(0)).

Отметим также, что x(0) будет являться опорным планом, а так же строго допустимым псевдопланом задачи L₀.

Если x(0) — целочисленный вектор, то он, очевидно, и является решением задачи (1.1) — (1.3).

В противном случае отыскивается минимальный индекс s, 0 s n, для которого величина x_s(0) не является целой. Пусть B(0) — симплексная таблица в координатной форме, соответствующая вектору x(0). С помощью коэффициентов s-й строки этой таблицы (т.е. коэффициентов приведенной системы (3.2), (3.3)) приемом, описанным выше, строится правильное отсечение.

Вводится вспомогательная переменная x_n+1 и рассматривается задача L₁:

Следующий этап состоит в нахождении лексикографического максимума задачи L₁. Важным достоинством алгоритма Гомори является тот факт, что начальный допустимый строгий псевдоплан для применения двойственного симплекс-метода к задаче L₁ находится без труда. Действительно, легко видеть, что в качестве такого псевдоплана можно взять вектор

В самом деле, очевидно, что y(1) удовлетворяет ( вместе с вектоорм x(0) ) ограничениям (3.6), (3.7) задачи L₁, а из ограничений (3.8) нарушается лишь одно: x_n+1(0)= — <_s0> j , j, таблицы B(0) лексикографически положителен: j > 0, j. Отсюда вытекает, что и в симплексной таблице в координатной форме, отвечающей опорному вектору y(1), всякий столбец (кроме первого, совпадающего с y(1)) лексикографически положителен:

Таким образом, имея в своем распоряжении решение x(0) лексикографической задачи L₀ и соответствующую симплекс таблицу в координатной форме B(0), без каких либо дополнительных вычислений находим начальный строго допустимый псевдоплан y(1) для задачи L₁ и строим соответствующую ему симплексную таблицу в координатной форме.

Может случиться, что лексикографическая задача L₁ не имеет решения. В этом случае решение целочисленной задачи (1.1) — (1.3) следует прекратить поскольку имеет место

Теорема 4. Если в задаче L₁ не существует лексикографического максимума, то множество X * целочисленных точек задачи (1.1) — (1.3) пусто.

Доказательство. Поскольку множество X векторов, удовлетворяющих условиям Ax = b, x 0, согласно предположению I ограничено, то ограниченным является и множество планов задачи L₁. Поэтому единственной причиной, по которой эта задача может не иметь лексикографического минимума, может быть только то что множество ее планов пусто. Покажем что в таком случае множество X * также пусто.

Предположим противное, т.е. что X * , и пусть x* = (x₁ * , x₂ * , …, x_n * ) X*. По теореме 2 получаем, что величина

неотрицательна. Но это означает, что вектор = (x₁ * , x₂ * , …, x_n * , x_n+1 * ) является планом задачи L₁, в противоречие с вышесказанным. Теорема доказана.

Пусть x(1) = (x₀(1), x₁(1), …, x_n(1), x_n+1(1)) — решение лексикографической задачи L₁. Отправляясь от задачи L₁ и вектора x(1), аналогичным образом строятся задачи L_r, r = 2, 3, …, и решения x(r) n +1+ r соответствующим им лексикографическим задач.

Заметим, что алгоритм Гомори однозначно определяет последовательность x(r), r = 0, 1, 2, …, что следует из однозначности выбора s. Обратим так же внимание на то, что индекс s всегда не превосходит n: 0 s n. В самом деле, если все x_j(r) при j = 0, 1, 2, …, n — целые числа, то из теоремы 2 вытекает, что x_n+1(r), x_n+2(r), … — также целые.

Если на каком — то шаге r вектор

оказывается целочисленным, то вектор (x₀(r), x₁(r), …, x_n(r)) является решением задачи (1.1) — (1.3). Доказательство этого утверждения очевидно.

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

3.4 Доказательство конечности алгоритма

Основной вопрос, относящийся к первому алгоритму Гомори таков: всегда ли за конечное число больших итераций можно получить целочисленный вектор x(r).

Докажем конечность первого Алгоритма Гомори. Будем использовать следующие обозначения:

где ( x₁(0), …, x_n(0) ) — решение лексикографической задачи L0, а x(0) = — соответствующее значение линейной формы (целевой функции).

вектор y(1) служит начальным строго довпустимым псевдопланом при решении задачи L1 двойственным симплексным методом в координатной форме: y(1) = (y₀(1), y₁(1), …, y_n(1), y_n+1(1) ) — вектор, получающийся из y(1) в результате первой (малой) итерации двойственного симплекс метода в координатной форме.

Аналогично вводятся обозначения

Из свойств двойственного симплекс метода в координатной форме следует

Лемма 1. Пусть s — минимальный индекс, для которого число xs(0) — не целое. Тогда

Доказательство. Поскольку из (3.9) следует y(1) >y(1), то возможно два случая:

В случае 1 утверждение леммы выполняется тривиально по определению лексикографического порядка.

Рассмотри случай 2. Согласно правилам двойственного симплекс-метода на первой (малой) итерации решения задачи L₁ выводу из числа базисных подлежит переменная x_n+1, поскольку в векторе y(1) x_j(0) 0, j , x_n+1 j , j , симплекс таблицы B(0) лексикографически положительны; в частности _k > 0 . Следовательно, координата _sk данного столбца должна быть неотрицательной. Заметим, что _sk = _sk ( т.е. 0 s n и s ), по условию (3.10) число _sk — не нуль. Поэтому

По формуле преобразования симплекс-таблицы имеем

Вспоминая, что xs(0) = s0, получаем:

С учетом (3.11) получим оценку:

Замечание. Если исходная задача (1.1) — (1.3) допустима, то согласно следствию из теоремы 2 индекс k, удовлетворяющий условию (3.10), существует.

Следствие. Справедливо соотношение

Действительно при r = 1 это неравенство вытекает из леммы и второго неравенства (3.9) . Что бы получить это утверждение при произвольном r, нужно воспользоваться тем, что y_j(r) = x_j(r) при 0 j n, и неравенством y(r) x(r) в (3.9).

Теорема 5. Если выполнены предположения I и II, то первый алгоритм Гомори требует лишь конечного числа больших итераций.

Что бы убедиться в истинности теоремы, необходимо показать, что при некотором r вектор x(r) = (x₀(r), x₁(r), …, x_n+r(r)) — целочисленный. Для этого, в свою очередь, достаточно доказать целочисленность вектора (x₀(r), x₁(r), …, x_n(r)), поскольку из теоремы 2 тогда вытекает, что все числа x_n+1(r), x_n+2(r), …, x_n+r(r) также целые. Вспомним также, что минимальный индекс s, при котором число xs(r) — нецелое , всегда не превосходит n: 0 s n. Прежде чем переходить к основному доказательству докажем следующую лемму:

Доказательство. Пусть s, 0 s n, — минимальный индекс для которого утверждение Леммы не выполняется. Обозначим

В том случае когда s = 0, положим R = 0.

В таком случае s — минимальный индекс, для которого число x_s(r) — нецелое. По следствию из леммы 1 имеем [x_s(r)] x_s(l).

Учитывая, что x_s(l) — не целое число, имеем x_s(l) > [x_s(l)], откуда и получаем нужное утверждение. Поскольку множество X планов задачи (1.1) — (1.3) ограничено, то ограничена любая величина x_s(r), 0 s n, r = 1, 2, … . Поэтому бесконечной цепочки неравенств вида [x_s(r)] > [x_s(l)] > … существовать не может, а, следовательно, в последовательности x_s(r), r = 0, 1, …, не может быть бесконечно много нецелых чисел. Аналогично доказывается, что в этой последовательности не может быть бесконечно много различных целых чисел.

Вернемся к доказательству теоремы. Пусть

где числа R_j фигурируют в формулировке леммы 2. Тогда согласно этой лемме все числа x_j(R), 0 j n, — целые. Из теоремы 2 получаем, что вектор x(R) — целочисленный. Следовательно алгоритм Гомори требует не более R итераций.

3.5 Замечания по практической реализации первого алгоритма Гомори

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

1) В ходе решения задачи L_r двойственным симплексным методом на каждой малой итерации следует пользоваться уточненным правилом вывода из числа базисных векторов для решения задач линейного программирования симплекс-методом: если в первом столбце симплексной таблицы имеется несколько отрицательных элементов _i0 ( = x_i), i =1, 2, …, n, …, n + r, то выводить из числа базисных надо переменную с минимальным номером.

2) Если в ходе очередной малой итерации при реализации задачи L_r все основные переменные x₁, x₂, …, x_n оказались неотрицательными, то дальнейшее применение двойственного симплекс-метода к задаче L_r следует прекратить, несмотря на то, что ее лексикографический максимум, быть может, еще не достигнут. Если при этом все переменные x_j, j = 1, 2, …, n, оказались целочисленными, то по теореме 2 все вспомогательные переменные x_n+k, k = 1, 2, …, r, целочисленны и неотрицательны. Это означает, как уже известно, что вектор ( x₀, x₁, x₂, … , x_n ) является решением исходной целочисленной задачи. В противном случае переходим к новой большой итерации.

3) Строка симплексной таблицы, соответствующая вспомогательной переменной x_n+r, удаляется, как только переменная x_n+r объявляется небазисной. Напомним, что это происходит на первой же малой итерации решения задачи L_r.

4) Если в ходе решения задачи L_r переменная x_n+r вновь попадает в число базисных, то то соответствующая ей строка не восстанавливается.

Понятно, что при выполнении правил 3), 4) размеры симплексной таблицы в первом алгоритме Гомори не увеличиваются — в каждой таблице содержится n + 2 строк, отвечающие основным переменным x₀, x₁, … , x_n и текущей вспомогательной переменной x_n+r в момент ее введения) и n — m +1 столбцов ( поскольку число n — m небазисных переменных не меняется ).

5) На первой малой итерации решения задачи L_r+1 в качестве переменной, выводимой из базиса, выбирается именно x_n+r+1, не смотря на то, что значения остальных вспомогательных переменных в этот момент так же могут быть отрицательными.

Заметим, что правило 5) на самом деле избыточно, поскольку при выполнении правил 3) и 4) мы ничего не знаем о значении остальных переменных x_n+1, …, x_n+r в момент перехода к задаче L_r+1. Данное правило выделено лишь для того, чтобы подчеркнуть отличие рассматриваемых алгоритмов.

Отметим, что при использовании правила 2) возникающая последовательность x‘(r) может не быть лексикографическим максимумом задачи L_r, поскольку значения некоторых из вспомогательных переменных могут быть отрицательными.

Тем не менее, для последовательности x‘(r), r = 0, 1, 2, …, получаемой с использованием правил 1) и 2), сохраняется важное свойство: эта последовательность единственна.

Осталось лишь доказать, что при использовании правил 1) — 4) алгоритм Гомори остается конечным, поскольку его конечность и будет означать, что он приводит к цели — нахождению целочисленного решения задачи (1.1) — (1.3). В самом деле, конечность числа R больших итераций означает, что вектор x‘(R) целочисленный.

Отметим, во-первых, что при использовании правила 2) число малых итераций решения задачи L_r конечно — не больше, чем требуется для нахождения ее лексикографического максимума.

Теорема 6. Последовательность x'(r), возникающая в процессе применения алгоритма Гомори, уточненного правила 1) — 4), конечна.

Доказательство. Заметим, что в доказательстве теоремы 5 о конечности последовательности x(r) использовались лишь два обстоятельства, регулирующие возникновение этой последовательности: способ построения правильного отсечения и тот факт, что во всякой текущей симплекс-таблице вс столбцы _j, j, лексикографически положительны. Таким образом, удаление строки, соответствующей вспомогательной переменной, может повлиять лишь на последнее обстоятельство. Этого, однако, так же быть не может, как показано в следующей лемме.

Лемма 3. В любой симплекс-таблице, возникающей в ходе алгоритма Гомори, уточненного правилами 1) — 4), для любого столбца

имеет место неравенство

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

По определению симплексной таблицы в координатной форме, имеем

Для любого x R n +1+ r , если утверждение леммы нарушается в ходе решения задачи L_r. Формула (3.13) с учетом (3.12) означает, что изменение значения переменной x_k не влияет на значение x_i, i = 0, 1, 2, …, n. Другими словами, при одном и том же наборе величин x_i, 0in, переменная x_k может принимать произвольное значение. Отсюда следует, во-первых, что k n + 1, а во-вторых, что принятое допущение (3.13) неверно, поскольку поскольку значение любой вспомогательной переменной x_k, k n + 1, как вытекает из (3.7), однозначно определяется значениями основных переменных.

Поскольку удаление строк, соответствующих вспомогательных переменным, не влияет на свойство столбцов _j, j , быть лексикографически положительными, то эти строки вообще не нужны. Действительно, с учетом правил 1) — 2) переменная x_n+r, попав в число базисных, так и остается базисной до конца вычислений, и ее строка не потребуется для определения переменной, вводимой в базис согласно правилам симплекс-метода.

Таким образом, элементы строки, соответствующие переменной x_n+r, не участвуют в формулах двойственного симплекс-метода для вычисления значений всех остальных переменных.

Поскольку, как отмечалось, индекс s, регулирующий формирование правильного отсечения, не превосходит n, 0 s n, то и для этих целей вспомогательные переменные не потребуются.

4. Реализация на ЭВМ

В данном курсовом проекте программа предназначена для нахождения решения целочисленной задачи линейного программирования методом Гомори.

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

Ввод данных в программном модуле производится из файла. Вывод результатов работы программы может производится в файл, на дисплей или на принтер. Формат входного файла:

где n — количество переменных, m — количество ограничений, c₁, c₂, … , c_n — коэффициенты максимизируемой линейной формы, a_ij — элементы матрицы A, b_j — компоненты вектора b. A, b — характеризуют ограничения [см. (1.2)].

Пример входного файла:

2 5 0 0 0 0 0 0 0

-1 3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. — Л.: Изд-во ЛГУ, 1981. -328 с.

2. Белоусова Г.С. Линейное программирование. Учебное пособие. -Красноярск: Наука, 1975. -107 с.

3. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. — 2-е изд., перераб. и доп. -М.: Высшая школа, 1980. -300 с.

4. Ашманов С.А., Линейное программирование. М.: Наука. 1969. -240 с

5. Габасов Р.И. Кириллова Ф.М., Методы линейного программирования. Минск: Наука. 1977. -174 с

Подобные документы

Теоретические основы метода отсечения, его назначение и функции в решении задач целочисленного линейного программирования. Сущность и практическая реализация первого и второго алгоритма Гомори. Применение алгоритма Дальтона, Ллевелина и Данцига.

курсовая работа [208,1 K], добавлен 12.10.2009

Целочисленные задачи математического программирования. Постановка транспортной задачи по критерию стоимости в матричной форме. Задача о назначении (проблема выбора, задача о женихах и невестах). Алгоритм метода Гомори. Формирование правильного отсечения.

курсовая работа [868,8 K], добавлен 05.12.2012

Симплексный метод как универсальное решение задач линейного программирования. Применение метода Жордана-Гаусса для системы линейных уравнений в канонической форме. Опорное решение системы ограничений. Критерий оптимальности. Задача канонической формы.

презентация [2,0 M], добавлен 11.04.2013

Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.

курсовая работа [65,3 K], добавлен 30.11.2010

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

курсовая работа [1,2 M], добавлен 14.11.2010

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

курсовая работа [37,2 K], добавлен 01.05.2011

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

контрольная работа [156,9 K], добавлен 30.01.2011

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

контрольная работа [79,4 K], добавлен 04.06.2010

История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.

курсовая работа [166,7 K], добавлен 17.07.2002

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

задача [656,1 K], добавлен 01.06.2016

Источник