Решение задачи целочисленного программирования

Уточним модель введением условия целочисленности изменяемых ячеек (Нажав «Добавить», в открывшемся окне задать диапазон G2:I5 и выбрать в списке знаков свойство «двоичное»).

Рис. 4.7. Дополнение условия «двоичности» изменяемых ячеек

Решение задачи ЦП имеет следующие значения (рис. 4.8.):

z = 40, A₁ = 1, A₃ = 1, B₃ = 1, B₄ = 1, C₁ = 1.

	A	B	C	D	E	F	G	H	I
	Варианты прибыли	А	В	С		Альтернативы	А	В	С
	Уч 1					Уч 1
	Уч 2					Уч 2
	Уч 3					Уч 3
	Уч 4					Уч 4
	Затраты	А	В	С		Доход
	Уч 1
	Уч 2
	Уч 3					Затраты		Бюджет
	Уч 4						<=

Рис.4.8. Результат замены ЛП-модели на ЦП-модель

Сравнивая полученные решения, видим что вариант А₃ заменил С₃ в множестве решений (А₃ имеет значение 1). Значение целевой функции (Прибыль) снизилась до 40. Соотношение, показывающее, что оптимальное значение целевой функции ЦП-решения не больше, чем оптимальное значение целевой функции ЛП-решения, выполняется всегда, поскольку требования к ОДР задачи ЦП более ограничительны, чем требования к ОДР задачи ЛП. Из-за дискретности решения F12 < H12 (бюджет используется не полностью).

Решение задачи ЛП обязательно находится в крайней точке ОДР, а целочисленное решение обычно не является крайней точкой, поэтому усложняется процесс их поиска^[3]. Принимая во внимание все возможные значения 0 или 1 для 12 переменным, можно построить множество решений для данной задачи, включающее 2¹²=4096 альтернатив. Отметим в заключение, что использование ограничений с «целыми» и «двоичными» числами в «Поиске решения», не всегда приводит к ожидаемым результатам, что иногда проявляется в невозможности найти требуемое решение с помощью данной надстройки.

Логические ограничения

При рассмотрении целочисленного решения модели,

z = 40, A₁ = 1, A₃ = 1, B₃ = 1, B₄ = 1, C₁ = 1,

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

Используя «двоичные» переменные эти ограничения можно смоделировать следующим образом:

Участок №1: A₁ + B₁ + C₁ 1

Участок №2: A₂ + B₂ + C₂ 1

Участок №3: A₃ + B₃ + C₃ 1

Участок №4: A₄ + B₄ + C₄ 1

Ограничения для участков 1, 3 и 4 называются взаимоисключающими ограничениями. Действительно, если выбран один вариант проекта для участка, то все другие должны быть отклонены. Математически это достигается ограничением сверху суммы двоичных переменных, моделирующих этот выбор (сумма не превосходит 1). Но выбор какого-либо варианта при этом не обязателен (все слагаемые в левой части могут равняться 0). Ограничение для участка 2 является ограничением обязательного выбора. Должно быть выбрано ровно столько вариантов, сколько задано правой частью равенства (в нашем случае ровно один вариант проекта из трех). Эти ограничения формируют логические условия для решения задачи. На основании такого подхода можно смоделировать и другие логические ограничения. Например, требование реализовать не менее одного проекта на участке 1, то есть равенства 1 по крайней мере одной из двоичных переменных в ограничении, приводит к указанию знака ‘ ≥ ’ вместо знака ‘≤’.

Добавляем ограничения к модели Excel и еще раз решаем ее без целочисленных ограничений. Для этого в ячейке J2 записываем формулу СУММ(G2:I2), которую затем «тиражируем» в диапазоне J3:J5. (Курсор наводим на нижний правый угол ячейки (курсор принимает вид +), нажимаем левую клавишу «мыши» и, удерживая её нажатой, «растягиваем формулу» на заданный диапазон.) В диапазоне К3:К5 задаем верхние границы ограничений, соответствующих участкам, а в диапазоне L3:L5 – нижние границы этих ограничений.

В «Поиске решения» (рис. 4.9) новые логические ограничения примут вид:

J3:J5 <= К3:К5,

J3:J5 => L3:L5.

Вновь решим вначале задачу ЛП, то есть исключим ограничения «двоичности».

Рис.4.9. «Поиск решения» с логическими ограничениями.

A

B

C

D

E

F

G

H

I

J

K

L

Варианты прибыли

А

В

С

Альтер-нативы

А

В

С

Сумма

Верх. граница

Нижн. граница

Уч 1

Уч 1

Уч 2

Уч 2

Уч 3

Уч 3

0,028

0,972

Уч 4

Уч 4

Затраты

А

В

С

Доход

Уч 1

39,6

Уч 2

Уч 3

Затраты

Бюджет

Уч 4

<=

Рис. 4.9. Решение задачи ЛП с логическими ограничениями.

Полученное решение задачи ЛП представлено на рис.4.9.

z = 39.6, A₁ = 1, A₂ = 1, B₃ = 0.028, B₄ = 1, C₃ = 0.972.

В решении проект А, реализуется на участках 1 и 2, и проект B - на участке 4. Две переменные оказываются дробными. Это можно интерпретировать так: на участке 3 реализуется «главным образом» проект C, но «частично» и проект B. Конечно, это невозможная ситуация.

Вновь восстановим требование «двоичности», добавив соответствующее ограничение в «Поиске решения», и получим ЦП-решение:

z = 38, A₁ = 1, A₂ = 1, B₃ = 1, C₄ = 1.

A

B

C

D

E

F

G

H

I

J

K

L

Варианты прибыли

А

В

С

Альтер-нативы

А

В

С

Сумма

Верх. граница

Нижн. граница

Уч 1

Уч 1

Уч 2

Уч 2

Уч 3

Уч 3

Уч 4

Уч 4

Затраты

А

В

С

Доход

Уч 1

Уч 2

Уч 3

Затраты

Бюджет

Уч 4

<=

Рис.4.10. Решение задачи с «двоичными» переменными

A

B

C

D

E

F

G

H

I

J

K

L

Варианты прибыли

А

В

С

Альтер-нативы

А

В

С

Сумма

Верх. Граница

Нижн. граница

Уч 1

Уч 1

Уч 2

Уч 2

Уч 3

Уч 3

Уч 4

Уч 4

Затраты

А

В

С

Доход

Уч 1

Уч 2

Уч 3

Затраты

Бюджет

Уч 4

<=

Рис. 4.11. Альтернативное решение с меньшими затратами

Альтернативное оптимальное решение, которое может быть получено при запуске «Поиска решения» с другими начальными условиями (значениями в диапазоне G2:I5 перед запуском «Поиска решения»), использует только два проекта и три участка:

z = 38, A₂ = 1, C₁ = 1, C₃ = 1.

При том, что все альтернативные оптимальные решения имеют одинаковые значения ЦФ, обратим внимание на то, что используют они различные «Затарты»:

z = 38, A₁ = 1, A₂ = 1, B₃ = 1, C₄ = 1, Затраты=100;

z = 38, A₁ = 1, A₄ = 1, B₃ = 1, C₂ = 1, Затраты=99;

z = 38, A₂ = 1, C₁ = 1, C₃ = 1, Затраты=98.

Казалось бы, последнее решение является наиболее выгодным в рамках заданных условий. Напрашивающееся включение «Затрат» в целевую функцию, может оказаться неприемлемым в реальной строительной ситуации, так как инвестируемые средства и получаемая прибыль, хоть и измеряются в одних и тех же денежных единицах, но имеют, вообще говоря, различную природу и ценность^[4]. Но если дополнить «Поиск решения» еще одним ограничением, например, F12≤ 98.9, то будет получен единственный результат: z = 38, A₂ = 1, C₁ = 1, C₃ = 1, Затраты=98. Таким образом, при наличии более одного оптимального решения возникает возможность учета дополнительных критериев, не входивших первоначально в условия задачи.

Дата добавления: 2015-07-15