Решение задачи методом целочисленного линейного программирования

Решение задачи методом целочисленного линейного программирования. Метод ветвей и границ.

Начальные условия берутся из решения задачи ЛП (решение см. выше). 1.Вершина 1 x1 = 6,17 x2 = 0,9 x3 = 4,9 Z1 = 6048,24 Начнем ветвление по x1 = 6,17, тогда получаем дополнительные ограничения а) x1 6 (1 ветвь) б) x2 7 (2 ветвь). Решаем сначала ветвь 1. К ограничениям задачи ЛП добавляем ограничение а. Получаем седьмым ограничением ограничение x1 6; Решение: 2.Вершина 2 x1 = 6 x2 = 1,2 x3 = 4,8 Z2 = 6033,7212 Мы получили одно целочисленное решение x1 = 6, следовательно дальнейшее ветвление мы будем проводить по x2 или x3. Решаем ветвь 2. К ограничениям задачи ЛП добавляем ограничение б. Седьмым ограничением становится ограничение x1 7. Решение: Второй строкой является ограничение задачи ЛП по максимально возможному объему руды с 2 предприятия: 120x1 740 или x16,16666, что противоречит введенному нами условию 6 (б) x1 7. Дальнейшее ветвление из вершины 3 невозможно.

Продолжим ветвление из вершины 2. Как было уже сказано выше, мы можем продолжить ветвление по x2 или x3. Продолжим ветвление по x2. x2 = 1,2, следовательно восьмое ограничение для 1 ветви будет x2 1, а для другой x2. Движемся сначала по ветви 1 в вершину 4. Решение: X1 = 6 x2 = 1 x3 = 5 Z4 = 5993,3501 Мы получили, что все три переменных имеют целочисленное значение, но, чтобы данное решение являлось решением задачи ЦЛП необходимо и достаточно показать, что при ветвлении по ветви 2 в вершине 5 мы получим значение целевой функции Z5 < Z4. Найдем решение в вершине 5. Решение: Z5 = 5991,0396, следовательно Z5 < Z4, значит в вершине 4 мы получили решение задачи ЦЛП. Интерпретация решения с помощью блок – схемы: x1=6,1 Z1=6048 x2=0,9 x3=4,9 x16 x17 x1=6 x2=1,2 Система x3=4,8 несовместна x21 x22 x1=6 x1=5,6 x2=1 x2=2 x3=5 x3=4 Z=5993 Z=5991 Вершина Ограничение № ограничения 2 x16 7 3 x17 7 4 x1 6 x21 7 8 5 x16 x22 7 8 Вывод: В результате решения я получил, что целочисленное оптимальное решение получается в вершине 4, так как все значения x1=6, x2=1,x3=5 в этой вершине целочисленные и Z5(5991)<Z4(5993), следовательно получено оптимальное решение.

Висящая вершина 5 и прозондированные 1,2,3,4. Плановые задания: , где P – плановое задание тыс. тонн, q – производительность состава, x – количество составов, i – номер предприятия.

Для предприятия 1: тыс. тонн; Для предприятия 2: тыс. тонн; Для предприятия 3: тыс. тонн.