Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП).
Найти вектор x= (x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 +... + cnxn (12.1)
и удовлетворяет систему ограничений
a11x1 +... + a1n xn = a10
....................... (12.2)
am1x1 +... + amnxn = am0
xj ³ 0, j=1...,n (12.3)
xj Î{ Xj1...,Xj,nj }, j=1...,p (p £ n) (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 (r £ p) такой, что Qr0 не удовлетворяет (12.4), к тому же Xrt < Qr0 < Xr,t+1 для некоторого t=1...,n r-1.
Тогда правильный відтин методу Дальтона-Ллевелiна имеет вид:
xn+1 – Dr,m+1 xm+1 –... – Drn xn = – (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..., ni - 1) 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.
Дата публикования: 2014-11-04; Прочитано: 2425 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!