- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
Найти вектор x=(x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 + ... + cnxn (12.1)
и удовлетворяет систему ограничений
a11x1 + . . . + a1n xn = a10
. . . . . . . . . . . . . . . . . . . . . . . (12.2)
am1x1 + . . . + amnxn = am0
xj0, j=1...,n (12.3)
xj{Xj1...,Xj,nj}, j=1...,p (pn) (12.4)
где 0 = Xj1<...< Xj,nj.
Изложение метода Дальтона-Ллевелiна.
Метод Дальтона-Ллевелина, как и методы Гомори, является одним из методов отсечения и заключается в следующем.
Решается вспомогательная ЗЛП (12.1)–(12.3), которую получают из исходной задачи (12.1)–(12.4) отбрасыванием условия дискретности переменных (12.4). Если ее решение удовлетворяет условие (12.4), то он же является и решением исходной ЧДЗЛП. Иначе от решенной ЗЛП переходят к новой вспомогательной ЗЛП присоединением линейного ограничения, которое удовлетворяют дискретные (в понимании условий (12.4)) развязки исходной ЧДЗЛП, но не удовлетворяетполученное решение исходной ЗЛП. Это дополнительное ограничениеопределяет некоторую отрезающую плоскость и зовется правильным відтином.
Присоединение новых правильных відтинів к начальной вспомогательной ЗЛП осуществляется до тех пор, пока на некотором шаге не будет получено дискретное решение вспомогательной ЗЛП, которое, очевидно, будет и оптимальным решением исходной ЧДЗЛП.
В методе Дальтона-Ллевелина правильный відтин строится таким образом. Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП ее непрямые ограничения приобрели вид:
xi + Qi,m+1 xm+1 +...+ Qin xn = Qi0, i=1...,m
и, следовательно, решением вспомогательной ЗЛП является вектор
x = (Q10...,Qm0,0,...,0).
Пусть существует номер r (rp) такой, что Qr0 не удовлетворяет (12.4), к тому же Xrt < Qr0 < Xr,t+1для некоторого t=1...,nr1.
Тогда правильный відтин методу Дальтона-Ллевелiна имеет вид:
xn+1 – Dr,m+1xm+1 –...– Drnxn = –(Qr0 – Xrt) (12.5)
где xn+1 0 — дополнительная переменная
(12.6)
Алгоритм метода Дальтона-Ллевелина.
1. Решаем вспомогательную ЗЛП (12.1)–(12.3). Пусть x(0) — ее оптимальное решение. Если эта задача не имеет решения, то исходная ЧДЗЛП также не имеет решения.
2. Пусть на s-й итерации решена вспомогательная ЗЛП, что имеет M ограничений та N переменных, x(s) — ее оптимальное решение.
Допустим, что x(s) определяется за каноничными ограничениями последней итерации, а именно:
xi + Qi,M+1 xM+1 +...+ QiN xN = Qi0, i=1...,M
откуда выплывает, что
x(s)= (Q10...,QM0,0,0,...,0).
3. Если Qi0 (i=1...,p) удовлетворяет условие (12.4), то конец: x(s) является решением исходной ЧДЗЛП. Иначе
4. Находим r=min{i}по всем и (i=1...,p) таким, что при некотором t (t=1...,ni1) Xit<Qi0<Xi,t+1, и строим дополнительное ограничение за формулами (12.5)–(12.6) при m=Mи n=N.
5. Расширяем симплекс-таблицу за счет (M+1) -ой строки (дополнительное ограничение) и (N+1) -го столбца, что отвечает дополнительной переменной xN+1.
6. Решаем расширенную ЗЛП с помощью двойственного симплекс-метода (ДСМ) и переходим к пункту 2 с заменой s на s+1, M на M+1, N на N+1. Если на некоторой итерации ДСМ одна из дополнительных переменных задачи опять становится базисной, то из последующего рассмотрения исключаются соответствующие ей строка и столбец и при переходе к пункту 2 заменяется лишь s на s+1.
Программное обеспечение.
Обучающий модуль, с помощью которого задача частично дискретного линейного программирования решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.
Задание.
Решить методом Дальтона-Ллевелина задачи частично дискретного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.
1) |
2 x1 + 3 x2 min |
2) |
5 x1 + 3 x2 max |
3) |
x1 + x2 max |
|
–3 x1 – 2 x2 –6 |
|
3 x1 + 5 x2 15 |
|
x1 + 2 x2 10 |
|
x1 + 4 x2 4 |
|
5 x1 + 2 x2 10 |
|
2 x1 + x2 10 |
|
x1 {0,1,3,4} |
|
x1 {0,1,2} |
|
x1 {0,3,4} |
|
x2 {0,2,3,5}; |
|
x2 {0,2,3}; |
|
x2 {0,1,2,4}; |
4) |
– 2 x1 + 3 x2 max |
5) |
– x1 – 3 x2 min |
6) |
x1 – 2 x2 min |
|
4 x1 + 5 x2 20 |
|
x1 + x2 5 |
|
x1 – x2 2 |
|
2 x1 + x2 6 |
|
– x1 + 2 x2 – 4 |
|
x1 + x2 3 |
|
x1 {0,2,4} |
|
x1 {0,2,4} |
|
x1 {0,1,2,4} |
|
x2 {0,1,2,5}; |
|
x2 {0,1,3,6}; |
|
x2 {0,2,4}; |
7) |
x1 – x2 max |
8) |
– x1 – x2 min |
9) |
3 x1 + 4 x2 max |
|
2 x1 – 2 x2 –5 |
|
– x1 + 4 x2 12 |
|
– x1 + 2 x2 4 |
|
2 x1 + 2 x2 7 |
|
4 x1 – x2 12 |
|
3 x1 – x2 7 |
|
x1 {0,2,3} |
|
x1 {0,1,4} |
|
x1 {0,1,3,5} |
|
x2 {0,1,3}; |
|
x2 {0,1,3,5}; |
|
x2 {0,2,3,5}. |
Ответы:
1) x* = (1; 2), L(x*)= 8.
2) x* = (1; 2), L(x*)= 11.
3) x* = (4; 2), L(x*)= 6.
4) x* = (2; 2), L(x*)= 2.
5) x* = (2; 3), L(x*)= –11.
6) x* = (0; 2), L(x*)= –4.
7) x* = (2; 0), L(x*)= 2.
8) x* = (1; 3), L(x*)= –4.
9) x* = (3; 3), L(x*)= 21.
Лабораторная работа 13.