Задачи с неделимостью, решаемые методами целочисленного линейного программирования.
Задания для контрольной работы №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 – й работы. При этом в качестве дополнительного условия принимается, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом. Составить модель задачи оптимального распределения механизмом.