План задачи линейного программирования называют целочисленным, если все его составляющие целые числа

Метод Гомори

Составим исходную симплексную таблицу.

Алгоритм решения канонической задачи ЛП

симплексным методом ( общий случай).

Запишем в общем случае алгоритм решения канонической задачи ЛП симплексным методом [1-4].

Дано:

при условиях:

;

.

Исходная симплексная таблица

		Коэффициенты при неизвестных
	…		…			…		…
F

2. Выберем разрешающий столбециз условия

(в задаче максимизации).

3. Выберем q – ю разрешающую строчку из условия

для

4. Формируем новую симплексную таблицу.

Пересчитываем элементы разрешающей q-й строки по формуле:

Если, затем исключим из 1-го и 3-го уравнений (точно также, как в методе Гаусса). Получим

Затем исключим аналогично из 1-го и 2-го уравнения. Придем к канонической системе, равносильной исходной.

Глава 3. Целочисленное линейное программирование.

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

К основной задаче ЛП добавим дополнительное условие – условие целочисленности неизвестных, в результате получим задачу ЛЦП. Можно, конечно, получить дробное оптимальное решение задачи ЛП и его округлить до ближайших целых значений. Но тогда может случиться, что мы будем либо близки к оптимальному плану задачи ЛЦП, либо далеки, либо вообще уйдем за пределы множества планов ЛЦП. Один из возможных методов решения задачи ЛЦП – метод Гомори. Идея метода базируется на представлении вещественного числа в виде суммы его целой и дробной частей. Как известно, целой частью вещественного числа «а» называется наибольшее целое число, не превосходящее Обозначение целой части [a]. Разность есть дробная часть числа Очевидно, например, что и Например:

Рассмотрим метод Гомори на примере (общая задача ЛП):

Для определения целочисленного решения задачи:

или в краткой форме:

можно использовать алгоритм Гомори, состоящий из следующих этапов.

Первый этап. Задача (7.1) - (7.3) решается симплекс-методом до получения оптимального плана.

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

составленное для i - ой строки следующим образом:

где

(Символом [ a ] обозначают целую часть числа a, то есть наибольшее целое число, не превосходящее a).

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

Примечания.

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

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

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

.

Схема решения задачи (7.1) – (7.4)

1. Исходную задачу решают симплекс-методом до получения оптимального решения без учета требования целочисленности его.

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

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

4. Введенную строку выбирают разрешающей.

5. Разрешающий элемент выбирают по принципу двойственного симплекс-метода.

6. С выбранным таким образом разрешающим элементом осуществляют переход (по известным правилам) к следующей симплекс-таблице.

7. В случае необходимости составляют еще одно дополнительное ограничение и процесс повторяют до получения целочисленного решения.

Дата добавления: 2014-01-04