- •Введение
- •1. Линейное программирование
- •1.1 Решение задачи 1.1
- •1.2 Решение задачи 1.2
- •1.3 Решение задачи 1.3
- •1.4 Выводы к Главе 1
- •2. Целочисленное программирование
- •2.1 Решение полностью целочисленных задач Решение задачи методом отсекающих плоскостей
- •Решение задачи методом ветвей и границ
- •2.2 Решение частично целочисленной задачи
- •Глава 3. Нелинейное программирование
- •1) Критерий Сильвестра.
- •2) Метод характеристических чисел.
- •3.2Квадратичный симплекс метод (метод Била)
- •3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией
- •3.4 Решение задачи сепарабельным симплекс-методом
- •3.5 Определение погрешности решения
- •3.6. Выводы к главе 3
2.2 Решение частично целочисленной задачи
Максимизировать целевую функцию вида:
При ограничениях:
;- целoе.
a) Метод Гомори для частично целочисленных задач.
Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:
Таблица 2.2.1 | |||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
x2 |
7/4 |
0 |
1 |
0 |
-2 |
0 |
1/4 |
-1 |
1/2 |
x3 |
5/4 |
0 |
0 |
1 |
-1 |
0 |
-1/4 |
0 |
1/2 |
Y |
-16 |
0 |
0 |
0 |
5 |
0 |
1 |
1 |
1 |
Значения целевой функции и переменных:
Значение переменной не удовлетворяет требованиям целочисленности.
В соответствии с правилами формирования коэффициентов ограничений метода Гомери для частично целочисленных задач имеем:
Вводим дополнительную свободную переменную:
Выражаем новое ограничение в форме Куна-Таккера:
Решаем новую расширенную задачу линейного программирования:
Таблица 2.2.2 | ||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
0 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
x2 |
7/4 |
0 |
1 |
0 |
-2 |
0 |
1/4 |
-1 |
1/2 |
0 |
x3 |
5/4 |
0 |
0 |
1 |
-1 |
0 |
-1/4 |
0 |
1/2 |
0 |
x9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
Y |
-16 |
0 |
0 |
0 |
5 |
0 |
1 |
1 |
1 |
0 |
Таблица 2.2.3 | ||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
0 |
x1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
x2 |
3/2 |
0 |
1 |
0 |
-5/2 |
0 |
0 |
-1 |
1/2 |
½ |
x3 |
3/2 |
0 |
0 |
1 |
-1/2 |
0 |
0 |
0 |
1/2 |
-1/2 |
x6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
Y |
-17 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
1 |
2 |
Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной .
Ответ: .
б) Метод ветвей и границ.
Проанализировав ограничения определим границы следующим образом:
Т.к. о целевой функции ничего не известно, примем .
Решаем Задачу 1 – исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:
Таблица 2.2.4 | |||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
x2 |
7/4 |
0 |
1 |
0 |
-2 |
0 |
1/4 |
-1 |
1/2 |
x3 |
5/4 |
0 |
0 |
1 |
-1 |
0 |
-1/4 |
0 |
1/2 |
Y |
-16 |
0 |
0 |
0 |
5 |
0 |
1 |
1 |
1 |
Значения целевой функции и переменных:
Принимаем
Полученное решение не удовлетворяет требованиям целочисленности для переменной .
Поэтому составляем относительно первой задачи две новых порожденных задачи:
Задача 2.
Максимизировать целевую функцию вида:
При ограничениях:
;
- новое ограничение.
Преобразуем новую систему ограничений Задачи 2, введя свободные переменные и приведя их к форме Куна-Таккера:
Воспользуемся симплекс методом и решим Задачу 2.
Таблица 2.2.5 | ||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
x6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
x7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
x8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
x9 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
Таблица 2.2.6 | ||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
x7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
x8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
x9 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
1 |
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
Таблица 2.2.6 | ||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x5 |
5/2 |
0 |
0 |
-2 |
-3 |
1 |
1/2 |
-2 |
0 |
0 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
x2 |
½ |
0 |
1 |
-1 |
-1 |
0 |
1/2 |
-1 |
0 |
0 |
x8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
x9 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
1 |
Y |
-37/2 |
0 |
0 |
-2 |
7 |
0 |
3/2 |
1 |
0 |
0 |
Допустимого решения Задачи 2 не существует.
Поэтому примем
Выбираем и решаем Задачу 3.
Максимизировать целевую функцию вида:
При ограничениях:
;
- новое ограничение.
Преобразуем новую систему ограничений Задачи 3, введя свободные переменные и приведя их к форме Куна-Таккера:
Воспользуемся симплекс методом и решим Задачу 2.
Таблица 2.2.7 | |||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
x6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
x7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
x8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
x9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
x10 |
6 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Таблица 2.2.8 | |||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
x7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
x8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
x9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
x10 |
3/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
1 |
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
Таблица 2.2.8 | |||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x5 |
5/2 |
0 |
0 |
-2 |
-3 |
1 |
1/2 |
-2 |
0 |
0 |
0 |
x1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
x2 |
1/2 |
0 |
1 |
-1 |
-1 |
0 |
1/2 |
-1 |
0 |
0 |
0 |
x8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
x9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
x10 |
3/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
1 |
Y |
-37/2 |
0 |
0 |
-2 |
7 |
0 |
3/2 |
1 |
0 |
0 |
0 |
Таблица 2.2.9 | |||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x5 |
2 |
0 |
0 |
-2 |
-4 |
1 |
0 |
-2 |
0 |
1 |
0 |
x1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
x2 |
0 |
0 |
1 |
-1 |
-2 |
0 |
0 |
-1 |
0 |
1 |
0 |
x8 |
3 |
0 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
x6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
x10 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
Y |
-20 |
0 |
0 |
-2 |
4 |
0 |
0 |
1 |
0 |
3 |
0 |
Таблица 2.2.10 | |||||||||||
БП |
СЧ |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
0 |
0 |
x1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
x2 |
3/2 |
0 |
1 |
0 |
-5/2 |
0 |
0 |
-1 |
1/2 |
1/2 |
0 |
x3 |
3/2 |
0 |
0 |
1 |
-1/2 |
0 |
0 |
0 |
1/2 |
-1/2 |
0 |
x6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
x10 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
Y |
-17 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
1 |
2 |
0 |
Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной . Поэтому принимаем
Т.к. список задач, подлежащих решению пуст, то можно сделать вывод о том, что решение задачи целочисленного программирования завершено.
Ответ:
Рис 2.2.1 Блок схема решения.
На основе полученных результатов решения задачи методом Гомори и методом ветвей и границ, можно сделать вывод о том, метод Гомори менее трудоемок. Однако, стоит учесть простоту решаемой задачи, в которой требование целочисленности наложено всего на одну переменную из трех. Метод Гомори в данном случае позволяет получить оптимальное решение с использованием всего одного уравнения отсекающей плоскости и решением одной расширенной задачи. Используя метод ветвей и границ, приходится решать уже две порожденных задачи, т.е. использование этого метода в данном случае менее эффективно. Таким образом можно сделать вывод о том, что метод ветвей и границ вообще мало эффективен для решения простых задач, где не требуется получение всех локальных оптимумов. В таких случаях разумнее воспользоваться методом Гомори для частично целочисленных задач.