Лабораторная работа №23 «Целочисленное программирование»

Теоретическая часть

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

Огромное число экономических задач носят целочисленный характер, что связано, прежде всего, с физической неделимостью многих расчетов: нельзя построить 2, 5 завода, купить 1, 5 трактора, задействовать на работу 3, 3 человека, построить 100, 7 скотомест и т.п. В большинстве случаев практическую задачу решают обычным симплексным методом, а затем округляют до целых чисел. Это оправдано в том случае, если дробная часть составляет очень малую часть от целого. Но иногда такой подход может внести большие изменения. Например, довольно существенно выбрать покупку одного или двух тракторов, если в результате решения без условия целочисленности переменная приняла значение 1, 5.

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

Алгоритм метода Гомори для решения задач целочисленного программирования на максимум целевой функции

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

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

3. Вводится дополнительное ограничение.

Правила введения дополнительного ограничения:

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

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

· тип нового ограничения " ³ ";

· чтобы ввести дополнительное ограничение в симплексную таблицу, надо привести его к типу " =" (каноническая форма записи) и умножить на " -1";

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

4. Новая строка таблицы (введенное дополнительное ограничение) принимается за разрешающую строку.

5. Для этой строки подсчитываются двойственные симплексные отношения, т.е. отношения неотрицательных оценок (D_j) к строго отрицательным коэффициентам разрешающей строки. Если в разрешающей строке нет ни одного строго отрицательного элемента при переменных, то система ограничений не совместна в области целочисленных решений.

6. По наименьшему по абсолютной величине отношению (по наибольшему отрицательному отношению) выбирается разрешающий столбец.

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

Далее алгоритм повторяется с пункта 2 до получения оптимального целочисленного решения. Алгоритм метода Гомори конечен.

Для решения задачи на минимум целевая функция умножается на " -1" и в дальнейшем используется алгоритм решения задачи на максимум. При записи оптимального решения значение целевой функции умножается на минус единицу, то есть переходим от максимума целевой функции к минимуму.

Пример

Найти maxZ=x₁+3x₂, при условиях

x₁+x₂ ³ 1

x₁+2x₂ £ 4

-x₁+2x₂ £ 2

x₁ ³ 0; x₂ ³ 0

x₁, x₂ - целые

 

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

maxZ=x₁+3x₂ +0x₃ +0x₄ +0x₅ –My₁

x₁+x₂ – x₃+y₁ =1

x₁+2x₂ +x₄ = 4

-x₁+2x₂ +x₅ = 2

x_j ³ 0, j=1¸ 5, y₁ ³ 0

 

№1	Cj							-M
Сi	П Б	ai0	x1	x2	x3	x4	x5	y1
-M	y1				-1
	x4
	x5		-1
Z	Dj	-M	-M-1	-M-3	M

 

В четвертой симплексной таблице получено оптимальное решение задачи.

№4	Cj							-M
Сi	П Б	ai0	x1	x2	x3	x4	x5	y1
	x2	3/2				1/4	1/4
	x1					1/2	-1/2
	x3	3/2				3/4	-1/4	-1
Z	Dj	11/2				5/4	1/4	M

 

Так как искусственная переменная y₁=0, то можно исключить ее из таблицы и в дальнейшем не рассматривать.

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

Определим коэффициенты дополнительного ограничения:

а_i0 = 3/2 – 1 =1/2 ( 1 – максимальное целое число, не превышающее 3/2);

а_i1 = а_i2 = а_i3 = 0 (0-0=0; 1-1=0)

а_i4 = 1/4-0=1/4

а_i5 =1/4-0=1/4

Получим дополнительное ограничение: 1/4х₄+1/4х₅≥ 1/2

Приводим это ограничение к каноническому виду:

1/4х₄+1/4х₅ – х₆ =1/2;

умножаем на " -1": -1/4х₄-1/4х₅ + х₆ = -1/2 и заносим в последнюю симплексную таблицу.

№4а	Cj
Сi	П Б	ai0	x1	x2	x3	x4	x5	x6
	x2	3/2				1/4	1/4
	x1					1/2	-1/2
	x3	3/2				3/4	-1/4
	x6	-1/2				-1/4	-1/4	1	i*
Z	Dj	11/2				5/4	1/4
ДСО	-	-	-	-5	-1	-
					j*

 

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

№5	Cj
Сi	П Б	ai0	x1	x2	x3	x4	x5	x6
	x2
	x1							-2
	x3							-1
	x5
Z	Dj

 

В таблице 5 получено оптимальное решение (все D_j ³ 0) с целочисленными значениями переменных: Х*(2, 1, 2, 0, 2, 0). MaxZ(X*)=5.

Общая постановка задачи

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

⇐ Предыдущая12345Следующая ⇒

Поделиться: