Метод Гомори

Ответы.

Опорного плана, решить следующие задачи.

Используя метод искусственного базиса для нахождения исходного

Ответы.

Задачи.

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

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

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

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

1. Дано

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

;

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

.

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

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

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

для

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

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

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

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

Решить симплекс-методом следующие задачи:

№ 1	№ 2	№ 3
№ 4	№ 5	№ 6
№ 7	№ 8	№ 9
№ 10	№ 11

№ 1.

№ 2.

№ 3.

№ 4.

№ 7.

№ 8.

№ 9.

№ 10.

№ 11. Линейная форма не ограничена.

№ 12	№ 13
№ 14	№ 15
№ 16	№ 17

№ 12.

№ 13. Линейная форма не ограничена.

№ 14.

№ 15.

№ 16.

№ 17.

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

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

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

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

Снимем условие целочисленности.

Max Z = x₁ + 2 x₂

при условиях: x₁ - 2 x₂ + x₃ = 2

- 2x₁ + x₂ + x₄ =2

x₁ + x₂ + x₅ =3

.

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

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
			-2
		-2
Z		-1	-2

Итерация 1

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
		-3
		-2
					-1
Z		-5

Итерация 2

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
Z	= 5

Задача ЛП решена. Решение нецелочиcленное.

Добавляем неравенство Гомори к итерации 2. Получим задачу ЦЛП:

Max Z = x₁ + 2 x₂

при условиях: x₃ + x₄ + x₅ = 7

x₂ + x₄ + x₅ =

x₁ - x₄ + x₅ =

- x₄ - x_{5 ≤}

.

.

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

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
					S2
S2
Z	= 5

Итерация 1

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных	S2
						-1
							-1
S2							-3
Z

  Получили оптимальное и целочисленное решение L(max) = 5. Дадим геометрическую интерпретацию решения данной задачи. Из рис. 1 видно, что максимально значение целевая функция принимает в точке, то есть решение является оптимальным, но без учета требования целочисленности.    

X₁

B

A max

A^*

D

C

X₂

I

.

.

x₂=2

.

.

.

III

  II

Рис. 1

С учетом требования целочисленности решение не является оптимальным, поэтому используем дополнительное ограничение

или. Значения переменных x4 и x5 подставим из второго и третьего уравнений системы ограничений,. В результате получим. Этому неравенству на рис. 1 соответствует полуплоскость, ограниченная прямой, отсекающей от многоугольника допустимых решений треугольник АДА*. В новом многоугольнике допустимых решений ОДА*ВС найдем точку А*(1,2), в которой целевая функция принимает максимальное значение. Так как координаты точки А* – целые числа, то решение является оптимальным планом исходной задачи.

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