Дополнительные логические ограничения

Вновь строительная фирма признает полученное решение недопустимым.

Во-первых, руководство фирмы позволяет проекту А быть размещенным на участках 1, 2, и/или 3, только, если он также используется на участке 4. (Этому требованию не удовлетворяют полученные выше решения.)

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

Первое наложенное условие, формирует ограничение следствия (импликации). Решение использовать проект на участках 1, 2 или 3 должно подразумевать, что проект A выбран для участка 4.

Алгебраическое линейное неравенство, выполнение которого эквивалентно данной импликации, имеет вид

A₁ + A₂ +A₃ ≤ 3*A₄.

Если любая из переменных A₁, A₂ или A₃ равна 1, то для выполнения условия переменная A₄ должна равняться 1. Ограничение не требует, чтобы одни из вариантов А₁, А₂, А₃ был выбран, если выбран вариант A₄ (A₄=1), потому что неравенство удовлетворяется при A₄=1 и А₁=А₂=А₃=0. Коэффициент 3 при A₄ позволяет не исключать выбора проекта А для других участков.

Второе условие требует, чтобы использовались все три проекта. Есть несколько способов достигнуть этого. Введем три новые двоичные переменные S_A, S_B, S_С, каждая из которых отражает факт выбора соответствующего проекта, хотя бы на одном участке:

если S_A = 1, то проект A используется, иначе – не используется;

если S_B = 1, то проект B используется, иначе – не используется;

если S_C = 1, то проект C используется, иначе – не используется.

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

A: A₁ + A₂ + A₃ + A₄ ≤ 4*S_A

B: B₁ + B₂ + B₃ + B₄ ≤ 4*S_B

C: C₁ + C₂ + C₃ + C₄ ≤ 4*S_C

Теперь добавляем ограничение, которое требует, чтобы все три проекта использовались (переменные были равны 1):

S_A + S_В + S_C = 3.

На рис. 4.12 представлена уточненная модель. Новые двоичные переменные S_A, S_В, S_C размещены в ячейках G9, H9, I9, соответственно. Их правые части ограничений по видам проектов – в ячейках G10, H10, I10 и заданы формулами G10=4*G9, G10=4*G9, G10=4*G9, соответственно. Сумма новых переменных – в ячейке J9. Количества реализованных проектов А, В, С вычислено в ячейках G6, H6, I6 по формулам СУММ(G2:G5), СУММ(H2:H5), СУММ(I2:I5), соответственно. Таким образом, заданы левые части огранияений по количеству проектов. Левая часть ограничения по проекту А вычислена в ячейке G7 = СУММ(G2:G4).

A

B

C

D

E

F

G

H

I

J

K

L

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

А

В

С

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

А

В

С

Сумма

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

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

Уч 1

Уч 1

Уч 2

Уч 2

Уч 3

Уч 3

Уч 4

Уч 4

Кол-во проектов

А1+А2+А3

Затраты

А

В

С

Доход

Sa

Sb

Sc

СуммаS

Уч 1

Уч 2

4S

Уч 3

Затраты

Бюджет

Уч 4

<=

Рис. 4.12. Дополнение элементов для новых логических ограничений

Задача ЦП с добавленными ограничениями, решается «Поиском решения» с настройками показными на рис.4.13. Отметим, что в окне «Ограничения» видны только вновь добавленные ограничения, а первые два ограничения «F12 ≤ H12» и «G2:I5=двоичное» скрыты за его пределами. Открыть их можно с помощью «движка» полосы прокрутки.

Рис. 4.13. Новые ограничения в «Поиске решения»

Результаты представлены на рис. 4.12:

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

У этого решения то же самое целевое значение как у решения, полученного без новых ограничений, таким образом, это - альтернативное оптимальное решение. Действительно, ЦП-модели часто имеют альтернативные оптимальные решения. Однако нет простого способа найти их все. Добавляя ограничения, которые лучше определяют цели ЛПР, можно найти наиболее приемлемое решение среди альтернативных оптимальных.

Отметим, что можно было смоделировать требование использования всех трех проектов с помощью ограничением S_A*S_B*S_C = 1. Оно недопустимо, потому является нелинейным относительно переменных задачи, хотя действительно достигает цели. Если использовать такое ограничение, придется решать задачу нелинейного целочисленного программирования, что требует значительно большего объема вычислений.

Введение логических переменных SA, SB, SC носит «тренировочный» характер, для освоения работы с такими переменными. Условие использования каждого проекта может быть задано добавлением в «Поиск решения» ограничения с использованием диапазона сумм столбцов таблицы изменяемых ячеек в виде G6:I6 >= 1. Такое ограничение логически эквивалентно ограничению J9=3.

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

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