- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача целочисленного линейного программирования. Метод гомори-1
Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 + ... + cnxn (9.1)
и удовлетворяет систему ограничений
a11x1 + . . . + a1n xn = a10
. . . . . . . . . . . . . . . . . . . . . . . (9.2)
am1x1 + . . . + amnxn = am0
xj0, j=1...,n (9.3)
xj — цели, j=1...,n. (9.4)
Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем.
Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9.4) отбрасыванием условия целочисленности переменных (9.4). Если оптимальное решение вспомогательной ЗЛП — целочисленный, то он будет и решением исходной ЦЗЛП. Если же полученное решение вспомогательной задачи не является целочисленным, то от развязанной ЗЛП переходят к новой вспомогательной ЗЛП присоединением линейного ограничения, которое удовлетворяют целочисленные развязки исходной ЦЗЛП и которое не удовлетворяет полученное нецелочисленное решение вспомогательной ЗЛП. Упомянутое дополнительное линейное ограничение определяет некоторую отрезающую плоскость и называется правильным відтином (ограничением). Присоединение новых правильных ограничений рассмотрена к начальной вспомогательной ЗЛП осуществляется до тех пор, пока на некотором шаге не будет получено целочисленное решение вспомогательной задачи, которое, очевидно, будет оптимальным решением исходной ЦЗЛП. В методе Гоморi-1правильный ограничение строится таким образом.
Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП непрямые ограничения этой задачи приобрели вид:
xi + аі,m+1 xm+1+...+ аin xn = аi0, i=1...,m
и, таким образом, решением вспомогательной ЗЛП будет вектор
x = (а10..., аm0,0...,0 ).
Пусть существует номер r такой, что аr0 — дробь, и, как всегда {z} — дробная часть z. Тогда правильный відтин методу Гомори-1задается неравенством:
{ аr,m+1} xm+1+...+ { аrn} xn { аr0} .
Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также не имеет оптимального решения.
2. Пусть на s-й итерации развязана вспомогательная ЗЛП, что имеет M ограничений и N переменных, x(s) — ее оптимальное решение.
Будем считать, что x(s) определяется каноничными ограничениями последней итерации, то есть:
xi + bi,M+1 xM+1 +...+ biN xN = bi0, i=1...,M
Откуда
x(s)= ( b10...,bM0,0,...,0 ).
3. Если bi0 (i=1...,M) — цели, то — конец, x(s) является оптимальным решением исходной ЦЗЛП. Если существует хотя бы одно и такое, что bi0 — дробь, то переход к пункту 4.
4. Находим r=min{i}по всем и таким, что bi0 — дробь и строим дополнительное ограничение
xN+1 – {br,M+1} xM+1 –...– {brN} xN = – {br0}
где xN+1 0 — дополнительная переменная.
5. Расширяем симплекс-таблицу за счет (M+1) -ой строки (дополнительное ограничение) и (N+1) -го столбца, что отвечает дополнительной переменной xN+1.
6. Решаем расширенную таким образом ЗЛП двойственным симплекс-методом и переходим к пункту 2 с заменой s на s+1. Если при этом на какой-либо итерации двойственного симплекс-метода одна из дополнительных переменных задачи повторно становится базисной, то исключаются из последующего рассмотрения соответствующие ей строка и столбец.
Программное обеспечение.
Обучающий модуль, с помощью которого полностью целочисленная задача линейного программирования Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.
Задание.
Решить методом Гомори-1 задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые и целые.
1) |
5 x1 + 6 x2 + 6 x3 min |
2) |
6 x1 + 4 x2 min |
|
2 x1 + 4 x2 10 |
|
2 x1 + x2 3 |
|
3 x1 + 2 x2 + 2 x3 10; |
|
x1 – x2 1; |
3) |
6 x1 + 4 x2 min |
4) |
x1 + x2 min |
|
2 x1 + x2 3 |
|
– x1 – x2 + x5 = –1 |
|
x1 – 2 x2 2 |
|
–2 x1 + 2 x2 + x3 = –2 |
|
3 x1 + 2 x2 1; |
|
–4 x1 + 2 x2 + x4 = –1; |
5) |
6 x1 + 4 x2 min |
6) |
2 x1 + 3 x2 min |
|
2 x1 + x2 3 |
|
x1 + 2 x2 16 |
|
x1 – x2 1; |
|
2 x1 + x2 16; |
7) |
5 x1 – 3 x2 max |
8) |
5 x2 + 7 x4 min | |
|
3 x1 + 2 x2 6 |
|
– 10 x2 + x3 + x4 = –16 |
|
|
2 x1 – 3 x2 – 6 |
|
x1 – 3 x2 – 3 x4 = –12 | |
|
x1 – x2 4 |
|
– 6 x2 – 2 x4 + x5 = –17; |
9) |
– 5 x4 – 7 x5 max |
10) |
8 x1 + 2 x2 max |
|
x1 – x4 – 2 x5 = – 7 |
|
x1 – 4 x2 + x3 = 4 |
|
– x3 + 3 x4 – 6 x5 = – 3 |
|
– 4 x1 + x2 + x4 = 4 |
|
x2 – x4 – 4 x5 = –11; |
|
x1 + x2 + x5 = 6. |
Ответы:
1) x* = (3; 1; 0), L(x*)= 21.
2) x* = (1; 1), L(x*)= 10.
3) x* = (1; 1), L(x*)= 10.
4) x* = (1; 0; 0; 3; 0), L(x*)= 1.
5) x* = (2; 0), L(x*)= 12.
6) x* = (6; 5), L(x*)= 27.
7) x* = (18; 14), L(x*)= 48.
8) x* = (0; 4; 24; 0; 7), L(x*)= 20.
9) x* = (0; 0; 0; 3; 2), L(x*)= 29.
10) x* = (5; 1; 0; 0; 0), L(x*)= 42.
Лабораторная работа 10.