ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА

Постановка частично дискретной задачи линейного программирования (ЧДЗЛП).

Найти вектор x=(x₁...,xn), что минимизирует целевую функцию

L(x)= c₁x₁ + ... + c_nx_n (12.1)

и удовлетворяет систему ограничений

a₁₁x1 + . . . + a_1n x_n = a₁₀

. . . . . . . . . . . . . . . . . . . . . . . (12.2)

a_m1x1 + . . . + a_mnx_n = a_m0

x_j³0, j=1...,n (12.3)

x_jÎ{X_j1...,Xj,nj}, j=1...,p (p£n) (12.4)

где 0 = X_j1 <...< X_j,nj.

Изложение метода Дальтона-Ллевелiна.

Метод Дальтона-Ллевелина, как и методы Гомори, является одним из методов отсечения и заключается в следующем.

Решается вспомогательная ЗЛП (12.1)–(12.3), которую получают из исходной задачи (12.1)–(12.4) отбрасыванием условия дискретности переменных (12.4). Если ее решение удовлетворяет условие (12.4), то он же является и решением исходной ЧДЗЛП. Иначе от решенной ЗЛП переходят к новой вспомогательной ЗЛП присоединением линейного ограничения, которое удовлетворяют дискретные (в понимании условий (12.4)) развязки исходной ЧДЗЛП, но не удовлетворяет полученное решение исходной ЗЛП. Это дополнительное ограничение определяет некоторую отрезающую плоскость и зовется правильным відтином.

Присоединение новых правильных відтинів к начальной вспомогательной ЗЛП осуществляется до тех пор, пока на некотором шаге не будет получено дискретное решение вспомогательной ЗЛП, которое, очевидно, будет и оптимальным решением исходной ЧДЗЛП.

В методе Дальтона-Ллевелина правильный відтин строится таким образом. Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП ее непрямые ограничения приобрели вид:

x_i + Q_i,m+1 x_m+1 +...+ Q_in x_n = Q_i0, i=1...,m

и, следовательно, решением вспомогательной ЗЛП является вектор

x = (Q₁₀...,Qm0,0,...,0).

Пусть существует номер r (r£p) такой, что Q_r0 не удовлетворяет (12.4), к тому же X_rt< Q_r0< X_r,t+1для некоторого t=1...,n_r-1.

Тогда правильный відтин методу Дальтона-Ллевелiна имеет вид:

x_n+1 – D_r,m+1 x_m+1 –...– D_rn x_n = –(Q_r0 – X_rt) (12.5)

где x_n+1 ³ 0 — дополнительная переменная

 

(12.6)

Алгоритм метода Дальтона-Ллевелина.

1. Решаем вспомогательную ЗЛП (12.1)–(12.3). Пусть x(0) — ее оптимальное решение. Если эта задача не имеет решения, то исходная ЧДЗЛП также не имеет решения.

2. Пусть на s-й итерации решена вспомогательная ЗЛП, что имеет M ограничений та N переменных, x(s) — ее оптимальное решение.

Допустим, что x(s) определяется за каноничными ограничениями последней итерации, а именно:

x_i + Q_i,M+1 x_M+1 +...+ Q_iN x_N = Q_i0, i=1...,M

откуда выплывает, что

x(s)= (Q₁₀...,Q_M0,0,0,...,0).

3. Если Q_i0 (i=1...,p) удовлетворяет условие (12.4), то конец: x(s) является решением исходной ЧДЗЛП. Иначе

4. Находим r=min{i} по всем и (i=1...,p) таким, что при некотором t (t=1...,ni-1) X_it<Q_i0<X_i,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.