Примеры ЗЦЛП

По расчетам садовника требуется внести в почву комплексные удобрения в количестве 107 кг. Удобрения продаются только в расфасованном виде: 1) мешок весом 35 кг стоит 140 руб.; 2) мешок весом 24 кг стоит 120 руб. Необходимо определить вариант закупки удобрений с минимальными затратами.

Запишем модель задачи:

L= 140 x₁+ 120 x₂® min;

35 x₁+ 24 x₂ ³ 107;

x₁, x₂ ³ 0, int (целые).

Если пренебречь целочисленностью, то легко увидеть, что оптимальным будет решение

x₁= 3 , x₂= 0.

Если округлить его по правилам арифметики, то получим недопустимое решение. Округление в большую сторону (x₁= 4, x₂= 0) приводит к допустимости, но является ли такое решение оптимальным?

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

Таблица 1

x1	x2	L
		-
		-

Как видно из таблицы, оптимальным является решение x₁^*= 1, x₂^*= 3, которое принципиально отличается от непрерывного: закупать надо в основном мешки 2-го типа, тогда как по нерерывному решению – только 1-го типа. Кроме того, округленное допустимое решение оказалось далеким от оптимального: затраты в нем выше минимальных на 12%. ▲

Другую особенность свойств целочисленных задач покажем также на конкретном примере:

L= 21 x₁+ 11 x₂® max;

7 x₁+ 4 x₂ £ 13;

x₁, x₂ ³ 0, int.

Как и в задаче о садовнике, рассмотрим все возможные целочисленные решения. При этом сначала возьмем решение x₁= 1, x₂= 1 и решения, окружающие его (табл. 2). Целочисленные точки и ограничение показаны на рис.1.

Таблица 2

x1	x2	L
		-
		-
		-
		-

Из таблицы следует, что в точке (1, 1) имеет место локальный экстремум, а глобальный максимум достигается в точке (0, 3). В непрерывной линейной задаче любой локальный экстремум является глобальным. То что целочисленная задача может иметь локальные экстремумы, необходимо учитывать при использовании методов частичного перебора. ▲

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

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

Возьмем многогранное множество M (B):

; (1)

(2)

где все a_ij – фиксированные целые числа, B = (b ₁ ,b ₂,…, b_m)^Т и m<n (ранг матрицы [ a_ij ] равен m.) Для него справедлива следующая теорема.

Теорема. Для того чтобы все вершины многогранного множества M (B) при любом целочисленном векторе B были целочисленными, необходимо и достаточно, чтобы каждый минор порядка m матрицы условий [ a_ij ] был равен либо 0, либо +1 или –1.

Если вместо равенств (1) множество задается неравенствами, указанные в теореме значения относятся ко всем минорам матрицы [ a_ij ].

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

Для решения таких задач применяются различные подходы. Из точных методов можно назвать следующие:

1. методы отсечений;

2. метод ветвей и границ;

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

4. модификации динамического программирования;

5. методы последовательного анализа вариантов.

Последние 4 метода входят в группу комбинаторных методов.

Кроме точных методов имеется также большое число приближенных методов.

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

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