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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Постановка задачи

Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида:

где все параметры модели должны быть определены из следующих условий:

Придумать оригинальную содержательную постановку задачи, которой соответствует модель из п.1.

Найти оптимальное решение модели, сформированной в п.1, используя метод ветвей и границ.

Записать математическую модель, отличающуюся от модели, сформированной в п.1, учетом следующих дополнительных условий:

а) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и 3;

б) выпуск продукции 2 возможен только в том случае, если запрещен выпуск продукции 1 и запрещен выпуск продукции 3.

Записать математическую модель транспортной задачи с учетом следующих дополнительных условий:

а) для любого из восьми пунктов транспортной сети могут использоваться не более двух дорог, связывающих его с соседними пунктами;

б) общая длина всех дорог транспортной сети не может превышать 40. (В качестве длины дороги между пунктами i и j следует взять число cij).

2. Решение

1. Формулируем модель

Данному варианту соответствуют следующие числа:

Таблица 1

Таблица 2

с учетом условий:

Таблица 3

Таблица 4

Таблица 5

модель целочисленного программирования имеет вид:

2. Содержательная постановка задачи.

Нефтеперерабатывающий завод производит три вида продукции: бензин, керосин и дизельное топливо. Процесс переработки нефти происходит в два этапа: этап первичной переработки - перегонка и этап вторичной перегонки - крекинг. Для каждого вида продукции затрачивается определенное время на каждый этап переработки, при этом работа оборудования по переработке имеет ограничение по времени работы: через определенное количество часов работы его необходимо проверять. Для полноты картины составляем таблицу:

Таблица 6

Стоимость партии каждого вида продукции составляет:

Бензин (1 тонна) - 4 тыс.р.

Керосин(1тонна) - 5 тыс.р.

Дизельное топливо (1 тонна) - 6 тыс.р.

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

Переменные хi являются видом продукции:

х1-- бензин. х2 -- керосин. х3 -- дизельное топливо.

Коэффициенты а11, а12, а13 , а21, а22, а23 - необходимое для переработки количество часов.

Коэффициенты b1 и b2 - почасовые ограничения работы оборудования на этапах переработки нефти.

Коэффициенты с1, с2, с3 - прибыльность произведенной продукции.

3. Оптимальное решение модели.

Рис. 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. Так как нерассмотренных ранее висячих вершин дерева задач больше нет, то выполнение алгоритма закончено: , так как . Оптимальное решение:

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

4. Математическая модель с учетом дополнительных условий

Вводим дополнительные ограничения в модель:

а) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и 3.

Данное условие можно записать в виде , тогда в случае запрета выпусков продукции 2 и 3 будет , то есть .

Для того, чтобы не привязывать количество производимой продукции 1 к количеству продукции 2 и 3, изменим условие следующим образом:

, где М - очень большое положительное число, которое в данной задаче достаточно принять М=10.

б) выпуск продукции 2 возможен только в том случае, если запрещен выпуск продукции 1 и запрещен выпуск продукции 3.

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

М - очень большое положительное число, которое необходимо для того, чтобы не ограничивать выпуск продукции 2 более уже имеющихся ограничений.

На основании вышесказанного запишем математическую модель:

5. Математическая модель транспортной задачи

На транспортную сеть накладываются дополнительные ограничения:

Рис. 2

для любого из восьми пунктов транспортной сети могут использоваться не более двух дорог, связывающих его с соседними пунктами;

общая длина всех дорог транспортной сети не может превышать 40. (В качестве длины дороги между пунктами i и j следует взять число cij).

Исходная модель:

Для введения новых ограничений, к исходной модели транспортной сети, необходимо ввести новые управляемые переменные.

Обозначим открытую дорогу между пунктами i и j, булевой переменной yij={0,1}.

При этом:

Первое дополнительное условие будет иметь вид:

т.е. для каждого пункта i открыто не более 2х дорог.

При этом yii=0, и кроме того, дорога односторонняя:

Второе дополнительное ограничение:

т.е. сумма длин всех открытых дорог не больше 40.

При этом в случае закрытой дороги нет и потока:

Запрограммируем это с помощью ограничения:

где:

U - достаточно большое число, чтобы неравенство выполнялось в любом случае при yij =1.

В итоге получаем модель:

Размещено на Allbest.ru