На этой странице представлено подробное исправленное упражнение задачи линейное программирование решается по алгоритму ветвь и связанный.
Владелец механического цеха планирует расширение за счет приобретения новых станков, прессов и токарных станков. Владелец подсчитал, что каждый купленный станок увеличит прибыль на 100 $ в день, а каждое вращение увеличит прибыль на 150 $ в день. Количество машин, которые может приобрести владелец, ограничено стоимостью машин и доступной площадью в мастерской. Цены на покупку машины и требования к пространству указаны ниже.
У владельца есть бюджет в размере 40 000 $ на покупку оборудования и 200 квадратных футов свободной площади. Владелец хочет знать, сколько машин каждого типа нужно купить, чтобы максимизировать ежедневное увеличение прибыли. Решить эту проблему.
Решение
Первым шагом является моделирование проблемы, это линейная задача целым числом (поэтому симплекс применить нельзя).
С x_1 количество нажатий и x_2 количество поворотов.
Мы начинаем метод ветвей и границ, сначала решая задачу как обычную модель линейного программирования без ограничений на целые числа (то есть ограничения на целые числа ослабляются или ослабляются). Модель линейного программирования для задачи и оптимальное упрощенное решение:
Расслабленное оптимальное решение: x_1=2,22 и x_2=5,56 с Z=1055,56.
Метод ветвей и границ использует диаграмму, состоящую из узлов и ветвей, в качестве основы для процесса решения. Первый узел на диаграмме ветвей и связей, показанной на рис. C-1, содержит упрощенное решение линейного программирования, показанное ранее, и округленное решение.
Мы обозначаем верхнюю границу результата ослабленного оптимального решения, а нижнюю границу результата оптимального решения в виде целого числа (округленного вниз).
Первое подключение
Создайте два ограничения (или подмножества), чтобы исключить дробную часть значения из решения, и посмотрите, какое из них дальше всего от округленного целочисленного значения (т. е. какая переменная имеет наибольшую дробную часть в абсолютном значении). Часть 0,56 от 5,56 является наибольшей дробной частью; таким образом, x_2 будет переменной, в которую мы собираемся «подключиться».
Другими словами, мы создадим две альтернативные линейные программы с учетом соответственно того, что x_2 должен быть меньше или равен 5 с одной стороны; а x_2 должен быть больше или равен 6, с другой стороны.
Итак, у нас есть следующая связь:
Решим задачу слева:
Это дает решение x_1=2,5, x_2=5 и Z=1000.
Решим систему справа:
Эта система имеет для решения x_1 = 1,33 и x_2 = 6, Z = 1033,33
С практической точки зрения мы сократили поле определения с ограничением x_2=6 и разрешили по обе стороны от ограничения, снятого линейной системой.
Давайте обновим наш график с новыми UB и LB каждой полученной системы.
Поскольку у нас пока нет оптимального и допустимого целочисленного решения, нам нужно продолжить разветвление (т. е. разбиение) модели либо из узла 2, либо из узла 3. Взгляд на рисунок показывает, что если мы разветвляемся из узла 2, максимальное значение, которое может быть достигнуто, составляет 1000 $ (верхняя граница).
Однако, если мы начнем с узла 3, возможно более высокое максимальное значение 1033 $. Таким образом, мы будем ответвляться от узла 3. В общем, всегда ответвляйтесь от узла с максимальной верхней границей.
Второе соединение
Теперь шаги ветвления, которые ранее выполнялись в узле 1, повторяются в узле 3. Сначала выбирается переменная, имеющая значение с наибольшей дробной частью. Поскольку x_2 имеет целочисленное значение, x_1 с дробной частью 0,33 — единственная переменная, которую мы можем выбрать. Таким образом, два новых ограничения развиваются из x_1.
Взяв узел 4, мы имеем следующую линейную программу:
Решение проблемы: x_1=1 и x_2=6,17 с Z=1025.
Вторая проблема:
Эта задача не допускает решения (нарушено первое ограничение). Таким образом, мы имеем следующий граф решения:
У нас все еще нет целочисленного решения, поэтому мы должны продолжить алгоритм ветвей и границ.
Третье соединение
Node 4 имеет лучший UB. Поскольку x_2 — единственная переменная, которая не является целым числом, мы перейдем к этой переменной.
После решения двух линейных программ в узлах 6 и 7 получаем полученные результаты следующий:
Решение узла 6 соответствует критериям исходной задачи (т.е. в целом числе). Только ветви в 3 и 4 имеют UB выше, чем узел 6, однако ветвь, которая дает узлы 5 и 7, не имеет допустимого решения. Делаем вывод, что оптимальное решение находится в узле 6.
Краткое изложение метода
Вот краткое изложение на английском языке метода, который мы только что использовали.
RU 
FR 
EN 
ES