Модели линейного и целочисленного программирования

Для создания модели должны быть определены переменные решения. В моделях математического программирования обычно используются переменные с индексами. Для представления решений в рассматриваемой задаче используются логические (двоичные) переменные А₁, А₂, … С₃ и С₄, каждая из которых принимает значение либо 0, либо 1. Представим условия задачи в виде таблиц:

Таблица 4.5. Таблица 4.6.

Доход	А	В	С
Уч 1
Уч 2
Уч 3
Уч 4

Затраты	А	В	С
Уч 1
Уч 2
Уч 3
Уч 4

Каждая строка задает номер участку застройки, а столбец – вариант проекта. При этом переменные будут составлять двоичную матрицу, представленную таблицей 4.7.

Таблица 4.7.

Альтернативы	А	В	С
Уч 1	А1	В1	С1
Уч 2	А2	В2	С2
Уч 3	А3	В3	С3
Уч 4	А4	В4	С4

Каждое сочетание «проект/участок» либо присоединяет свой вклад в чистый доход и бюджет (=1), либо нет (=0).

Задача линейного программирования будет иметь вид:

Цель: Max z = 6*A₁ + 7*A₂ + 9*A₃+... + 19*C₃ + 20*C₄.

При условии:

Затраты не превосходят бюджета:

13*A₁ + 20*A₂ + 24*A₃ +... + 48*C₃ + 55*C₄ 100.

Двоичные значения переменных: A₁, A₂,...,C₄ Î {0,1}.

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

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

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