Оптимальное решение модели. - Методика решения задачи целочисленного программирования

Рис. 1

Шаг 1. Исходную задачу 1 заносим в дерево задач.

В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой функции берем в качестве нижней границы оптимального значения целевой функции:

Итерация 1.

Шаг 2. Выбираем единственную висячую вершину дерева задач - задачу 1.

Шаг 3. Решаем задачу линейного программирования, соответствующую задаче 1. Полученное решение имеет вид:

Шаг 4. Полученное оптимальное решение задачи линейного программирования не является целочисленным, поэтому переход на шаг 5.

Шаг 5. Выбираем переменную x3. Запишем в дерево задач две новые задачи - 2 и 3. Первая из них отличается от задачи 1 тем, что в ней добавляется новое ограничение x31, а вторая: x32 . Принимаем.

Итерация 2.

Шаг 2. Выбираем задачу 2.

Шаг 3. Находим оптимальное решение задачи линейного программирования, соответствующей задаче 2:

Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.

Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 4 с добавочным ограничением x10 и задачу 5 с ограничением x11. Принимаем Переходим на шаг 2.

Итерация 3

Шаг 2. Выбираем задачу 3.

Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 3, не имеет допустимого решения. Принимаем. Переходим на шаг 2.

Итерация 4

Шаг 2. Выбираем задачу 4.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.

Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 6 с добавочным ограничением x20, задачу 7 с ограничением x21.

Итерация 5

Шаг 2. Выбираем задачу 6.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Так как решение задачи линейного программирования целочисленно, то принимаем

Итерация 6

Шаг 2. Выбираем задачу 7.

Шаг 3. Задача линейного программирования не имеет допустимого решения. Принимаем

Итерация 7

Шаг 2. Выбираем задачу 5.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.

Шаг 5. Выбираем переменную x3. Вносим в дерево задач задачу 8 с добавочным ограничением x30, задачу 9 с ограничением x31.

Итерация 8.

Шаг 2. Выбираем задачу 8.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.

Шаг 5. Выбираем переменную x1. Вносим в дерево задач задачу 10 с добавочным ограничением x11, задачу 11 с ограничением x12.

Итерация 9.

Шаг 2. Выбираем задачу 9.

Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 9, не имеет допустимого решения. Принимаем. Переходим на шаг 2.

Итерация 10.

Шаг 2. Выбираем задачу 10.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.

Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 12 с добавочным ограничением x20, задачу 13 с ограничением x21.

Итерация 11.

Шаг 2. Выбираем задачу 11.

Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 11, не имеет допустимого решения. Принимаем. Переходим на шаг 2.

Итерация 12.

Шаг 2. Выбираем задачу 12.

Шаг 3. Оптимальное решение задачи линейного программирования:

Шаг 4. Так как решение задачи линейного программирования целочисленно, то принимаем

Итерация 13.

Шаг 2. Так как нерассмотренных ранее висячих вершин дерева задач больше нет, то выполнение алгоритма закончено: , так как. Оптимальное решение:

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

Похожие статьи




Оптимальное решение модели. - Методика решения задачи целочисленного программирования

Предыдущая | Следующая