Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

Контрольные вопросы и упражнения

Вопросы и упражнения частично позаимствованы из [37].

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

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

3. Какой геометрический смысл имеет введение дополнительного ограничения в методе Гомори?

4. Как при применении двойного симплекс-метода можно определить отсутствие допустимых целочисленных решений?

5. Можно ли методом Гомори получить приемлемое решение при прекращении вычислений до достижения оптимального решения?

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

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

8. Решите методом Гомори следующую целочисленную задачу

f = 4x1 + 6x₂ + 2x₃ → max;

4x1 – 4x2 ≤ 5;

–x1 + 6x2 ≤ 5;

–x1 + x2 + x₃ ≤ 5;

где x1, x2, x3 – неотрицательные целые числа.

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

9. Решите методом ветвей и границ следующую целочисленную задачу

f = x1 + x2 → max,

2x1 + 5x₂ ≤ 16;

6x1 + 5x₂ ≤ 30;

где x1, x2 – неотрицательные целые числа.

10. Рассмотрите задачу

f = 3x1 + 6x₂ + x3 → max,

x1 + 2x₂+ 2x₃ ≤ 8/5;

x1 + 2x₂ + 3x₃ ≤ 5/2,

где x1, x2, x3 – неотрицательные целые числа.

а) Каково оптимальное решение, если снять условие целочисленности переменных? Существует ли более одного оптимального решения?

б) Определите путем простого подбора оптимальное целочисленное решение и выясните округляется ли ответ, полученный в пункте (а) до этого решения?

в) Представьте задачу графически в пространстве решений, приняв x3 = 0 (то есть начертите ограничения на x1 и x2). Укажите все допустимые целочисленные решения.