Мегаобучалка Главная | О нас | Обратная связь

Решение частично целочисленной задачи




Максимизировать целевую функцию вида:

При ограничениях:

; - целoе.

a) Метод Гомори для частично целочисленных задач.

Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

 

Таблица 2.2.1
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8
x5 -5 -2
x1 9/2 -1 -1/2
x2 7/4 -2 1/4 -1 1/2
x3 5/4 -1 -1/4 1/2
Y -16

Значения целевой функции и переменных:

Значение переменной не удовлетворяет требованиям целочисленности.

В соответствии с правилами формирования коэффициентов ограничений метода Гомери для частично целочисленных задач имеем:

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

Выражаем новое ограничение в форме Куна-Таккера:

Решаем новую расширенную задачу линейного программирования:

 

Таблица 2.2.2
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 -5 -2
x1 9/2 -1 -1/2
x2 7/4 -2 1/4 -1 1/2
x3 5/4 -1 -1/4 1/2
x9 -1/2 -1 -1/2
Y -16

 

Таблица 2.2.3
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 -5 -2
x1 -1
x2 3/2 -5/2 -1 1/2 ½
x3 3/2 -1/2 1/2 -1/2
x6 -2
Y -17

Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной .

Ответ: .

 

б) Метод ветвей и границ.

Проанализировав ограничения определим границы следующим образом:

Т.к. о целевой функции ничего не известно, примем .

Решаем Задачу 1 – исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

 

Таблица 2.2.4
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8
x5 -5 -2
x1 9/2 -1 -1/2
x2 7/4 -2 1/4 -1 1/2
x3 5/4 -1 -1/4 1/2
Y -16

Значения целевой функции и переменных:



Принимаем

Полученное решение не удовлетворяет требованиям целочисленности для переменной .

Поэтому составляем относительно первой задачи две новых порожденных задачи:

Задача 2.

Максимизировать целевую функцию вида:

При ограничениях:

;

- новое ограничение.

Преобразуем новую систему ограничений Задачи 2, введя свободные переменные и приведя их к форме Куна-Таккера:

Воспользуемся симплекс методом и решим Задачу 2.

 

 

Таблица 2.2.5
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 -3 -1 -2
x6 -9 -2
x7 -5 -1 -1
x8 -2 -1 -1
x9
Y -3

 

 

Таблица 2.2.6
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 3/2 -2 -1 -1/2
x1 9/2 -1 -1/2
x7 -1/2 -1 -1/2
x8 5/2 -2 -1/2
x9 -1/2 1/2
Y -18 -3

 

Таблица 2.2.6
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
x5 5/2 -2 -3 1/2 -2
x1 9/2 -1 -1/2
x2 ½ -1 -1 1/2 -1
x8 5/2 -2 -1/2
x9 -1/2 1/2
Y -37/2 -2 3/2

 

Допустимого решения Задачи 2 не существует.

Поэтому примем

Выбираем и решаем Задачу 3.

Максимизировать целевую функцию вида:

При ограничениях:

;

- новое ограничение.

Преобразуем новую систему ограничений Задачи 3, введя свободные переменные и приведя их к форме Куна-Таккера:

Воспользуемся симплекс методом и решим Задачу 2.

 

Таблица 2.2.7
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x5 -3 -1 -2
x6 -9 -2
x7 -5 -1 -1
x8 -2 -1 -1
x9 -5 -1
x10
Y -3

 

Таблица 2.2.8
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x5 3/2 -2 -1 -1/2
x1 9/2 -1 -1/2
x7 -1/2 -1 -1/2
x8 5/2 -2 -1/2
x9 -1/2 -1 -1/2
x10 3/2 1/2
Y -18 -3

 

Таблица 2.2.8
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x5 5/2 -2 -3 1/2 -2
x1 9/2 -1 -1/2
x2 1/2 -1 -1 1/2 -1
x8 5/2 -2 -1/2
x9 -1/2 -1 -1/2
x10 3/2 1/2
Y -37/2 -2 3/2

 

Таблица 2.2.9
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x5 -2 -4 -2
x1 -1
x2 -1 -2 -1
x8 -1 -1
x6 -2
x10
Y -20 -2

 

Таблица 2.2.10
БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x5 -5 -2
x1 -1
x2 3/2 -5/2 -1 1/2 1/2
x3 3/2 -1/2 1/2 -1/2
x6 -2
x10
Y -17

Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной . Поэтому принимаем

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

Ответ:

Рис 2.2.1 Блок схема решения.

 

На основе полученных результатов решения задачи методом Гомори и методом ветвей и границ, можно сделать вывод о том, метод Гомори менее трудоемок. Однако, стоит учесть простоту решаемой задачи, в которой требование целочисленности наложено всего на одну переменную из трех. Метод Гомори в данном случае позволяет получить оптимальное решение с использованием всего одного уравнения отсекающей плоскости и решением одной расширенной задачи. Используя метод ветвей и границ, приходится решать уже две порожденных задачи, т.е. использование этого метода в данном случае менее эффективно. Таким образом можно сделать вывод о том, что метод ветвей и границ вообще мало эффективен для решения простых задач, где не требуется получение всех локальных оптимумов. В таких случаях разумнее воспользоваться методом Гомори для частично целочисленных задач.





Читайте также:





Читайте также:
Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ...
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...

©2015 megaobuchalka.ru Все права защищены авторами материалов.

Почему 3458 студентов выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.011 сек.)