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

Задания для контрольной работы №2.

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

1-14. Найти полностью целочисленное решение следующих задач, сопровождая (где это возможно) решение графической иллюстрацией (предполагается, что все ).

15. Решить задачи 1-3, используя метод отсекающих плоскостей. Дать геометрическую интерпретацию решения.

16. Доказать, что дополнительное ограничение вида , где суммирование распространяется на все свободные переменные в оптимальном нецелочисленном решении задачи , является «сечением» для построения задачи .

17. Привести к целочисленной задачу максимизации в области, изображенной на рисунке 12.

18. Привести к задаче целочисленного программирования следующую задачу: максимизировать при условиях:

а) и либо , либо ;

б) и либо , либо .

19. Дана полностью целочисленная задача:

Докажите, что решение этой задачи нельзя получить методом округления.

20. На примере полностью целочисленной задачи

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

21-26. Решить следующие частично целочисленные задачи (предполагается, что все ).

27. Преобразовать в полностью целочисленные задачи 21 и 24 и сравнить их решение с предыдущим.

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

28. Составить модель задачи по определению оптимального плана производства n типов машин при заданных объемах ресурсов, нормах расхода i – го ресурса на производство одной k- той машины и величинах прибыли при реализации одной машины k- го типа. Предполагается, что к концу планируемого периода не должно быть незавершенного производства.

29. Имеется m типов машин (i = 1,…, m) и n видов работ , подлежащих выполнению в объемах . Задана матрица , где - производительность i - той машины на k - й работе, матрица , где - себестоимость выполнения единицы k – й работы машиной i – ого типа, и стоимость одной машины i – ого типа.

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

Указание: Ввести два вида переменных: - общее число машин i – го типа и - количество машин i – го типа, используемых на k – й работе; последние могут и не быть целочисленными, если производительность машин не кратна объему работы .

30. Имеются суда m типов в количествах , на каждом из которых имеются n грузовых емкостей (k = 1,2,…,n) с грузоподъемностью (некоторые могут быть равны нулю). Подлежат перевозке p видов грузов в количестве . Составить математическую модель задачи по выбору оптимального состава судов, если затраты по эксплуатации одного i – го типа равны .

31. Имеется n маршрутов, по каждому из которых необходимо совершить (k = 1,…,n) и m типов автомашин, каждая из которых может быть использована в течение ч (i = 1,…,m). На выполнение i –й машиной рейса по k – му маршруту требуется ч при затратах руб. Составить модель задачи оптимального распределения машин по маршрутам.

32. Требуется распилить a бревен, длиной каждое в 10 м, на брусьях трех размеров: 3,5; 4,5 и 5 м, которые должны быть изготовлены в ассортименте 2:1:1. Составить модель для определения оптимального плана распила из условия максимального использования каждого бревна.

33. (Задача об оптимальном назначении.) Имеется n работ (k – 1,2,…,n) и m механизмов (i – 1,…,m), способных выполнить эти работы. Задана матрица , элементы которой характеризуют эффективность выполнения i – м механизмом k – й работы. При этом в качестве дополнительного условия принимается, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом. Составить модель задачи оптимального распределения механизмом.