- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача целочисленного линейного программирования. Метод ветвей и границ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП).
Найти вектор x=(x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 + ... + cnxn (13.1)
и удовлетворяет систему ограничений
a11x1 + . . . + a1n xn R1 a10
. . . . . . . . . . . . . . . . . . . . . . . (13.2)
am1x1 + . . . + amnxn Rm am0
xj0, j=1...,n (13.3)
xj — цели, j=1...,n. (13.4)
где символ Ri (i=1...,m) заменяет один из знаков: , =, .
Считается также, что многогранное множество, которое определяется соотношениями (13.2)–(13.3), ограниченная, а коэффициенты cjцелевой функции (13.1) — целые числа.
Дальше приводится алгоритм метода Ленд-Дойг, который представляет собой реализацию метода ветвей и границ для сформулированной выше задачи.
Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1). Если ее решение x(0;1) — целочисленный, то он же является и решением исходной ЦЗЛП. Иначе величина (0;1)=L(x(0;1)) дает нижнюю оценку (границу) целевой функции ЦЗЛП на множестве D(0;1)=D, что определяется соотношениями (13.2) (13.3).
Пусть некоторая координата xj(0;1) (j=1...,n) решения x(0;1) не является целочисленной. В этом случае осуществляется разветвление множества D(0;1) на два подмножества D(1;1) и D(1;2) добавлениемк ограничениям, которые задают D(0;1), ограниченийxj[xj(0;1)] но xj[xj(0;1)]+1 соответственно, где [z] — целая часть числа z. Дальше Решаются новые вспомогательные ЗЛП с ограничениями, которые определяются подмножествами D(1;1) и D(1;2), находятся границе (1;1) но (1;2) и т.д.
Для последующего разветвления выбирается перспективное множество D(k;r) с наименьшей границею (k;r). Процесс продолжается до тех пор, пока не будет получено решение, которое удовлетворяет условие целочисленности и для которого выполняется признак оптимума (см. п. 4 алгоритма). В результате ограниченности допустимого множества ЗЛП (конечности допустимого множества ЦЗЛП) метод Ленд-Дойга конечный.
Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления (см. пункт 5). На 0-м шаге возлагаемD(0;1)=D, гдеD задаетсяусловиями (13.2) (13.3).
2. Решаются вспомогательные ЗЛП на множествах D(k;r). Пусть x(k;r) — оптимальные решения указанных ЗЛП.
3. Вычисляются границы на множествах D(k;r) за формулой (k;r)= ]L(x(k;r))[, где ]z[ — наименьшее целое число, не меньше z.
4. Если существуют k, l такие, что x(k;l) — целочисленное решение и для всех веток r на k-у шаге выполняются соотношения
L(x(k;l))= (k;l) (k;r)
то x* = x(k;l) — оптимальное решение ЦЗЛП.
5. Разветвление осуществляется по нецелочисленной компоненте xj(k;r) (с минимальным j) решения x(k;r), что отвечаетперспективной ветке k;r (если такихветок несколько, то выбирается ветка с минимальным r), добавлениемк D(k;r) одного из подмножеств xj[xj(k;r)] или xj[xj(k;r)]+1.
Программное обеспечение.
Обучающий модуль, с помощью которого задача целочисленного линейного программирования. Решается в диалоге с пользователем за выбранным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
Решить методом ветвей и границ задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи (без использования программного обеспечения).
Во всех задачах выполняются условия: xj0, xj — целое, j=1,2.
1) |
x1 + x2 max |
2) |
–2 x1 – x2 min |
3) |
6 x1 + 4 x2 min | |
|
2 x1 + 11 x2 38 |
|
6 x1 + 4 x2 24 |
|
2 x1 + x2 3 | |
|
x1 + x2 7 |
|
x1 – x2 3 |
|
x1 – 2 x2 2 | |
|
4 x1 – 5 x2 5; |
|
– x1 + 3 x2 3; |
|
3x1 + 2x2 1; |
4) |
x1 + x2 min |
5) |
5 x1 + 7 x2 min |
6) |
2 x1 – x2 max |
|
– x1 – x2 – 1 |
|
– 10 x1 + x2 – 16 |
|
2 x1 + x2 8 |
|
– 2 x1 + 2 x2 – 2 |
|
– 3 x1 – 3 x2 – 12 |
|
x1 + 3 x2 6 |
|
– 4 x1 + 2 x2 – 1; |
|
– 6 x1 – 2 x2 – 17 |
|
3 x1 + x2 3; |
7) |
x1 + 4 x2 min |
8) |
–5 x1 – 7 x2 max |
9) |
x1 + 2 x2 min |
|
x1 – 3 x2 –1 |
|
2 x1 + x2 3 |
|
2 x1 + 2 x2 5 |
|
8 x1 – x2 6 |
|
20 x1 – x2 15 |
|
x1 – 3 x2 –1 |
|
3 x1 – 11 x2 –7; |
|
x1 – x2 –2; |
|
x1 – x2 2. |
Ответы:
1) x* = (3; 2) или x* = (2; 3), L(x*)= 5.
2) x* = (3; 1), L(x*)= –7.
3) x* = (1; 1), L(x*)= 10.
4) x* = (1; 0), L(x*)= 1.
5) x* = (4; 0), L(x*)=20.
6) x* = (3; 1), L(x*)= 5.
7) x* = (1; 1), L(x*)= 5.
8) x* = (1; 3), L(x*)= –26.
9) x* = (4; 2), L(x*)= 8.