Вопросы для самоконтроля по теме 4

1. Каким образом составить двойственную задачу к задаче линейного программирования?

2. Какие ограничения называются нормальными?

3. В чем суть первой теоремы двойственности?

4. Как определить решение двойственной задачи?

5. Что показывает решение двойственной задачи?

6. Как связано решение прямой задачи и двойственной?

7. В чем суть двойственного симплекс-метода?

8. Как выбирается переменная, покидающая базис, и переменная, входящая в базис, при решении задачи двойственным симплекс-методом?

9. Какие задачи можно решить двойственным симплекс-методом?

Вопросы для самостоятельного изучения по теме 4

1. В чем суть второй теоремы двойственности (теоремы о дополняющей нежесткости)?

2. Какая задача называется нормальной?

3. Как определить возможные диапазоны изменений коэффициентов целевой функции при небазисной переменной?

4. Как определить возможные диапазоны изменений коэффициентов целевой функции при базисной переменной?

5. Как определить возможные диапазоны изменений правых частей несвязующих ограничений?

6. Как определить возможные диапазоны изменений правых частей связующих ограничений, при которых остаются справедливыми текущие теневые цены?

7. Как определить, изменится ли оптимальное решение при изменении колонки коэффициентов при небазисной переменной?

8. Как определить изменится ли оптимальное решение при появлении возможности выпуска нового вида продукции?

Тема 5 целочисленное программирование

5.1. Понятие задачи целочисленного программирования

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

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

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

Задача целочисленного программирования, которая получается путем отмены ограничений на целочисленность или ограничений типа «0 или 1», называется линейно-ослабленной задачей.

Утверждение 1. Решение задачи целочисленного программи­рования всегда не лучше, чем решение линейно-ослабленной задачи. Для задачи на максимум , а для задачи на минимум: .

Утверждение 2. Если ОДЗ линейно-ослабленной задачи является ограниченным множеством, то ОДЗ целочисленной задачи содержит конечное число точек.

Отсюда следует 3 подхода к решению целочисленных задач:

1. Путем прямого перебора и сравнения всех точек. Очевидно, что применение этого метода весьма ограничено. Во-первых, если ОДЗ линейно-ослабленной задачи является неограниченным множеством, то количество точек целочисленной задачи будет бесконечным, во-вторых, даже при конечном числе точек прямой перебор может оказаться очень длительной и неэффективной процедурой.

2. Путем округления решения линейно-ослабленной задачи до целых. Из примера 5.1 видно, что этот метод тоже далеко не всегда применим, а решение задачи, полученное путем округления, может оказаться далеким от оптимального. Применяется этот метод, если переменные принимают достаточно большие значения, например, если получилось, что нужно выпускать 1003,4 единиц продукции, то округление до 1003 может быть вполне приемлемым.

3. Путем построения дополнительных ограничений в рамках имеющегося ОДЗ с целью отсечения нецелочисленных значений переменных. На этом подходе основано два метода решения задач целочисленного программирования, которые будут рассмотрены в п.п. 5.2 и 5.3: метод ветвей и границ и метод отсекающих плоскостей.

Пример 5.2. Рассмотрим задачу:

x_1,2 – целые.

ОДЗ представляет собой 6 точек: (0;0), (0;1), (0;2), (0;3), (1;0), (1;1). Методом перебора легко получить, что оптимальное решение (0;3) и Z = 66 (рис. 5.1).

Р ис. 5.1. Решение графическим способом задачи примера 5.2

Оптимальное же решение линейно-ослабленной задачи будет (1 6/7; 0) и Z = 78.

Очевидно, что округление решения линейно-ослабленной задачи в меньшую сторону (1; 0) с Z = 42 – далеко от оптималь­ного, округление же в большую сторону (2; 0), вообще является недопустимой точкой.