Постановка задачі лінійного програмування

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ

 

Навчально-методичний посібник

для студентів денної та заочної форми навчання за напрямком

0502 - менеджмент

 

Київ-2003

 

 

Навчально-методичний посібник розроблений доц. Доценко С.І. та ст.викл. Онищенко В.В., обговорений і затверджений на засіданні кафедри вищої математики ДУІКТ від 03.01.2003 р., протокол № 8.

 

Рецензент:

доктор фізико-математичних наук

професор кафедри інформаційних систем

факультету кібернетики

Київського Національного

університету імені Тараса Шевченка

Попов Юрій Дмитрович

 

 

У навчальному посібнику висвітлюються основні теоретичні аспекти математичного програмування згідно з програмою цього курсу для студентів денної та заочної форми навчання ДУІКТ за напрямком: 0502 – менеджмент.

До кожної теми подаються докладні теоретичні відомості, практичні приклади їх застосування, що супроводжуються розгорнутими поясненнями.

Посібник містить добірку задач для контрольних робіт студентів.

 

 

ДУІКИ, 2003

Програма дисципліни

(назва тем, короткий перелік основних питань)

1. Лінійне програмувння (ЛП):

1.0. Вступ. Загальна характеристика дисципліни;

1.1. Загальна постановка задачі ЛП (ЗЛП);

1.2. Графічний метод розв’язку ЗЛП;

1.3. Теоретичні основи ЛП;

1.4. Алгоритм симплекс-методу;

1.5. Двоїстість у ЛП.

2. Транспортна задача ЛП (ТЗЛП):

2.1. ТЗЛП;

2.2. Методи побудови опорних планів ТЗ:

2.2.1. Метод північно-західного кута;

2.2.2. Метод мінімального елемента;

2.2.3. Метод подвійної переваги;

2.3. Метод потенціалів.

3. Цілочисельне програмування (ЦП):

3.1. Постановка задачі ЦП (ЗЦП);

3.2. Область застосування ЗЦП у плануванні та промисловому менеджменті;

3.3. Геометрична інтерпритація ЗЦП;

3.4. Загальна характеристика методів розв’язання ЗЦП;

3.5. Методи відтинання. Метод Гоморі.

4. Динамічне програмування (ДП):

4.1. Багатокроковий процес прийняття рішень;

4.2. Метод рекурентних співвідношень. Принцип оптимальності;

4.3. Реалізація обчислювального методу

багатокрокової задачі оптимізації.

5. Нелінійне програмування (НП):

5.1. Постановка задачі НП (ЗНП);

5.2. Геометрична інтерпритація ЗНП;

5.3. Загальні питання НП.

6. Елементи теорії матричних ігор:

6.1. Основні поняття теорії ігор;

6.2. Гра в чистих стратегіях;

6.3. Гра в змішаних стратегіях;

6.4. Геометрична інтерпритація розв’язку матричної гри з двома гравцями.

ПЕРЕЛІК ЗАПИТАНЬ ДО ІСПИТУ:

1. Предмет математичне програмування (МП).

2. Класифікація задач МП.

3. Особливості застосування МП в менеджменті.

4. Приклади ЗЛП.

5. Загальна постановка ЗЛП.

6. Графічний метод розв’язання ЗЛП. Ідея СМ.

7. Геометрична інтерпретація ЗЛП.

8. Стандартна ЗЛП. Базисні розв’язки ЗЛП.

9. Канонічна ЗЛП.

10. Властивості розв’язків ЗЛП.

11. Симплекс метод.

12. Метод жорданових перетворень.

13. Метод штучних змінних.

14. М-метод.

15. Графічно проілюструйте всі випадки розв’язання ЗЛП.

16. Як в симплекс методі проводиться вибір першого опорного плану, його оцінка та перехід до кращого плану?

17. Коли потрібно користуватись методом штучного базису?

18. Поняття двоїстості. Правила побудови двоїстих задач.

19. Зв’язок між розв’язками взаємоспряжених задач.

20. Лема та теореми двоїстості, їх економічний зміст.

21. Двоїстий симплекс метод.

22. Алгоритм двоїстого симплекс методу.

23. Постановка ТЗЛП. Особливості структури ТЗ.

24. Умови розв’язності ТЗ.

25. Властивості опорних планів ТЗ.

26. Метод північно-західного кута.

27. Метод мінімального елемента.

28. Метод подвійних переваг.

29. Метод потенціалів.

30. Розв’язок задач з урахуванням часу транспортування.

31. Постановка задачі ЦП (ЗЦП).

32. Область застосування ЗЦП у плануванні та промисловому менеджменті.

33.Геометрична інтерпритація ЗЦП.

34.Загальна характеристика методів розв’язання ЗЦП.

35.Загальна постановка задач ДП.

36.Багатокроковий процес прийняття рішень.

37.Метод рекурентних співвідношень. Принцип

оптимальності.

38.Постановка задачі НП. Геометрична інтерпретація

ЗНП.

39.Загальні питання НП.

40.Матричні ігри двох осіб.

 

1. ЛІНІЙНЕ ПРОГРАМУВАННЯ

В загальній формі (ЗЗЛП)

Знайти вектор x =(x₁,...,x_n), що мінімізує цільову функцію

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

і задовольняє систему обмежень

a₁₁x₁+...+a_1nx_n R a₁₀

............................

a_m1x₁+...+a_mnx_n R a_m0

x_j³0, j=1,...,k

(де R - один з знаків відношення =, £ або ³, а умову додатності накладено не обов’язково на всі змінні).

Приклад 1.

Знайти графічний розв’язок ЗЛП:

, (1)

, (2)

. (3)

y

 

 

D

 

 

F

2 K

N x O 2 M (1) L (2)

Рис.1

 

1. В (1), (2) замінюємо знаки нерівностей на знаки строгих рівностей: 3x+y=21, x+2y=10. Для спрощення побудови доцільно поділити обидві частини рівності на праву частину. Отримаємо:

або , (1*)

або . (2*)

Рівняння (1*) перетинає вісі координат в M(7,0), D(0,21), а (2*) – в L(10,0), F(0,5).

Будуємо графіки прямих (1*), (2*) (рис.1).

2. Кожна з побудованих прямих поділяє площину системи координат на дві півплощини. Координати точок однієї задовольняють нерівність, що розглядається, а іншої – не задовольняють. Щоб визначити необхідну півплощину (на рис.1 її напрям позначено стрілками), потрібно взяти будь-яку точку і перевірити, чи задовольняютьїї координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. У протилежному разі таким зображенням є інша півплощина. Умова невід’ємності змінних (3) обмежує ОДР задачі першим квадрантом системи координат. Переріз усіх півплощин визначає ОДР задачі.

 

3. OFKM – чотирикутник розв’язків ЗЛП.

4. Будуємо вектор компонентами якого є коефіцієнти при змінних

у цільовій функції задачі. Вектор завжди виходить із початку координат і напрямлений до точки з координатами .

5. Побудуємо лінію, що відповідає, наприклад, значенню Це буде пряма

, яка перпендикулярна до вектора і проходить через початок

координат.

6. Переміщуючи пряму , в протилежному напрямі вектора (оскільки задача мінімізації), бачимо (з рис.1), що останньою спільною точкою прямої цільової функції та многокутника OFKM, є точка K. Координати цієї точки визначають оптимальний розв’язок задачі, що мінімізує значення цільової функції.

7. Координати точки К визначаються перетином прямих (1) і (2):

Розв’язавши цю систему рівнянь, отримаємо:

.

Обчислюємо екстремальне значення цільової функції в К(6,4; 1,8):

.

Симплекс-метод (СМ)

Основні означення:

 

1. Вектор x =(x₁,...,x_n) називається допустимим розв’язком ЗЛП, якщо його компоненти задовольняють обмеження (1.2)-(1.3)

2. Ненульовий допустимий розв’язок x -базисний (ДБР), якщо його додатнім компонентам x_j відповідають лінійно незалежні вектори умов A_j (нульовий допустимий розв’язок будемо завжди вважати базисним).

3. Система m лінійно незалежних векторів умов, що включає вказані вектори A_j називається базисом.

4. Вектори базису утворюють базисну матрицю.

5. ЗЛП називається канонічною, якщо її обмеження (1.2) мають канонічну форму:

x₁+ + a_1,m+1 x_m+1+...+a_1nx_n=a₁₀

.......................................................

x_j+ +a_j,m+1 x_m+1+...+a_jnx_n=a_j0

........................................................

x_m + a_m1x_m+1+...+a_mnx_n=a_m0

x_j³0, j=1,...,n

6. Щоб перетворити задачу із загальної у стандартну форму, треба зробити наступну послідовність дій:

1) у нерівність £ з (1.2) потрібно ввести додаткову змінну y_j (яка також називається базисною) з коефіцієнтом 1. При цьому нерівність перетворюється в рівність, коефіцієнт в цільовій функції при новій змінній дорівнює нулю і на нову змінну накладається умова невід’ємності.

2) у нерівність ³ з (1.2) потрібно ввести додаткову змінну y_j з коефіцієнтом -1 (всі інші дії аналогічні п.1).

3) якщо на деяку змінну x_j не накладено умову невід’ємності, то ця змінна замінюється різницею двох змінних y_k-y_k+1, на які вже накладено умову невід’ємності. При цьому заміну x_j® y_k-y_k+1 потрібно зробити в цільовій функції (1.1) і в системі обмежень (1.2).

 

Приклад 2.

Нехай потрібно звести до стандартної форми наступну задачу:

x₁+ 2x₂ - 3x₃®min

x₁+ x₂ = 8

2x₁ + x₃ £ 6

x₁ +2x₃ ³ 2

x₁, x₂ ³ 0

Перше обмеження залишаємо без змін. У друге обмеження додаємо змінну x₄ зі знаком +, а у третє- змінну x₅ зі знаком -. Оскільки на змінну x₃ не накладено умову невід’ємності, то замінюємо її різницею двох невід’ємних змінних (наприклад x₃-x₆). Таким чином, задача приймає наступний вигляд:

x₁+ 2x₂ -3x₃ + 3x₆®min

x₁ + x₂ =8

2x₁ +x₃ +x₄ -x₆ =6

x₁ +2x₃ -x₅-2x₆ =2

x_j ³0, j=1,..,6

 

Стандартна ЗЛП (1.1)-(1.3) може також зводитись до канонічної форми за допомогою так званого методу штучних змінних, суть якого полягає у наступному. Розглядається допоміжна задача (назвемо її y-задачею) з такою ж самою системою обмежень, як і М-задача, але цільова функція має вигляд:

L*(x)=y₁+...+y_m®min.

Допоміжна задача розв’язується симплекс-методом. При цьому можуть виникнути такі випадки:

1) Для оптимального розв’язку L*(x)=0 (тобто жодна з y_j не є базисною). Тоді відкидаємо всі y_j і розв’язуємо одержану задачу симплекс-методом (оскільки для неї вже побудовано початковий допустимий базисний розв’язок).

2) Для оптимального розв’язку L^*( x )>0 (тобто принаймні одна з y_j не є базисною). Тоді вихідна ЗЛП не має розв’язків.

 

Перед застосуванням М-методу або методу штучного базису можна зробити декілька жорданових перетворень вихідної матриці умов. Діючи таким чином, можна зменшити кількість штучних змінних, а іноді й уникнути застосування вказаних методів.

Жорданові перетворення робляться таким чином:

1) Для деякого стовбця k обчилюється для a_ik>0 відношення q_i=a_i0/a_ik і визначається і, що задовольняє співвідношенню

i=argmin q_i,

i: a_ik>0.

2) Елемент a_ik вибирається за розв’язуючий і робиться перетворення Жордана-Гауса.

3) Розглядається інший стовбець, який не є базисним і для нього визначається i (як описано в п. 1). Якщо визначене i не співпадає з номерами рядків, в яких вже є базисні змінні, то переходимо до п. 2, а якщо співпадає - то вибираємо інший небазисний стовбець.

Якщо в результаті послідовності дій 1)-3) одержано m базисних змінних, то застосовувати метод штучного базису або M-метод не потрібно і одразу переходимо до розв’язку задачі симплекс-методом. Якщо кількість одержаних базисних змінних менша за m, то штучні змінні додамо лише у рядки, в яких немає базисних змінних, і застосовуємо метод штучного базису або M-метод.

Алгoритм симплекс-метoду

 

На кожному кроцi СМ виконуються такі дії (розрахункові формули наводяться лише для першого кроку).

1. Розглядається ДБР x=(a₁₀,...,a_m0,0,...,0).

Обчислюються відносні оцінки (симплекс-рiзницi) D_j небазисних змінних x_j, j=m+1,...,n, за формулою:

D_j=c_j – (c_б, A_j),

де c_б=(c₁,...,c_m), A_j — вектор умов, що відповідає змінній x_j (відносні оцінки базисних змінних дорівнюють нулю).

Якщо для всіх j=1,...,n, виконується умова D_j³0, то ДБР x є оптимальним розв'язком КЗЛП. Якщо до того ж усі штучні змінні дорівнюють нулю, то, відкидаючи їх, отримаємо оптимальний розв'язок вихідної ЗЛП; інакше вихідна ЗЛП не має розв'язкiв (її допустима область порожня).

Якщо існує таке j, що D_j<0, а вектор умов A_j не має додатніх компонент, то ЗЛП не має оптимального розв'язку (її цільова функція L(x) не обмежена знизу на допустимому многограннику розв'язкiв). Кiнець обчислень.

2. Якщо існують індекси j, для яких Dj<0, а відповідні вектори умов Aj мають

додатні компоненти, то знаходять k за формулою

k=argminD_j,

j: D_j<0

i, обчислюючи для a_ik>0 відношення q_i=a_i0/a_ik, визначають i, що задовольняє співвідношення

i=argminq_i,

i: a_ik>0

3. Переходять до нового ДБР, шляхом уведення до базису вектора A_k i виведення з базису вектора A_i. Такий перехід здійснюється за допомогою симплекс-перетворень (елементарних перетворень Жордана-Гаусса) з ведучим елементом a_ik над елементами розширеної матриці умов (1.2). Перехiд до пункту 1.

 

Далі буде розглянуто декілька прикладів розв’язку задач (в усіх задачах, що розглядаються нижче, всі змінні невід’ємні).

 

Задача 1.

x₁+x₂+x₃®min

x₁ -x₄ -2x₆=5

x₂ + 2x₄-3x₅+ x₆=3

x₃+2x₄-5x₅+2x₆=5

 

Складаємо симлекс-таблицю:

 

	Cj
CБ	XБ	X1	x2	x3	x4	x5	x6	A0	Q
	x1				-1		-2		-
	x2				(2)	-3			3/2
	x3					-5			5/2
	D				-3		-1
	x1		½			-3/2	-3/2	13/2
	x4		½			-3/2	½	3/2
	x3		-1			-2
	D		3/2			7/2	½

 

На першому кроці базисними змінними є x₁,x₂ та x₃, отже вектор С _Б має координати (1,1,1). Оцінки при базисних змінних дорівнюють нулю. Для інших змінних оцінки треба обчислити за формулою D_j=c_j-( С _Б, X _j). Таким чином,

D₄=0-((1,1,1),(-1,2,3))=-3;

D₅=0-((1,1,1),(0,-3,-5))=8;

D₆=0-((1,1,1),(-2,1,2))=-1.

Далі вибираємо стовпчик з максимальною за модулем від’ємною оцінкою (тобто 4-й). Для 4-го стовпчика визначаємо мінімальне

Q: ,

мінімум досягається для i=2. Вибираємо елемент (2;4) за розв’язуючий та робимо перетворення Жордана-Гауса. У другій таблиці всі , тобто знайдено оптимальний розв’язок, який знаходимо із стовпця A₀ останньої таблиці:

X_опт=(13/2; 0; 2; 3/2; 0; 0; 0),

F_min=13/2+2=17/2.

Нехай треба знайти максимум цільової функції для цієї ж самої задачі. У цьому випадку треба замінити знак коефіцієнтів цільової функції на протилежний і симплекс-таблиці матимуть такий вигляд:

 

	Cj	-1	-1	-1
CБ	XБ	X1	x2	x3	X4	x5	x6	A0	Q
	x1				-1		-2
	x2					-3
	x3					-5
	D					-8

З першої таблиці видно, що D ₅ <0, однак всі інші елементи 5-го стовпця від’ємні, зачить цільова функція необмежена на допустимій області.

Задача 2.

 

x₁+ 2x₂+ x₄®min

x₁+ x₂+2x₃- x₄ = 2

2x₁+ x₂- 3x₃+x₄ = 6

x₁+ x₂+ x₃+x₄ = 7

 

У цій задачі, на відміну від попередньої, немає початкового допустимого базисного розв’язку. Розглянемо три методи його пошуку.

 

1) Метод жорданових перетворень.

Þ

Таким чином, побудовано початковий допустимий базисний розв’язок і задача повністю підготовлена до застосування симплекс-методу:

	Cj
CБ	XБ	X1	x2	x3	X4	A0	Q
	x1		8/11
	x4		1/11
	x3		2/11
	D		13/11

Оскільки всі D³0, то знайдений допустимий базисний розв’язок є оптимальним,

X_опт=(3; 0; 1; 3),

F_min=3+1=4.

2) Метод штучних змінних.

Допоміжна задача для побудови допустимого базисного розв’язку вихідної задачі має вигляд:

 

y₁+ y₂+ y₃®min

x₁+ x₂+2x₃ -x₄ + y₁ =2

2x₁+ x₂ -3x₃+x₄ + y₂ =6

x₁+ x₂+ x₃+x₄ +y₃=7

	Cj
CБ	XБ	X1	x2	x3	X4	y­1	y­2	y­3	A0	Q
	y1	1			-1
	y2			-3
	y3
	D	-4	-3		-1
	x1	1			-1					-
	y2		-1	-7	(3)	-2				2/3
	y3			-3		-1				5/2
	D				-5
	x1	1	2/3	-1/3		1/3	1/3		8/3	-
	x4		-1/3	-7/3		-2/3	1/3		2/3	-
	y3		2/3	(11/3)		1/3	-2/3		11/3
	D		-2/3	-11/3		2/3	5/3
	x1	1	8/11			4/11	3/11	1/11	8/3
	x4		1/11			-5/11	-1/11	7/11	2/3
	x2		2/11			1/11	-2/11	1/11	11/3
	D

Таким чином, всі D³0, отже знайдено розв’язок допоміжної задачі, при цьому всі y_j виведено з базису, отже відкидаючи стовпці y_j, маємо ДБР для вихідної задачі (який, доречі, співпадає з ДБР, який було знайдено методом жорданових перетворень). Знайдений розв’язок задачі симплекс-методом повністю співпадає з наведеним вище.

 

3) М-метод.

Допоміжна М-задача має такий вигляд:

x₁+ 2x₂+ x₄+ My₁+My₂+ My₃®min

x₁+ x₂+2x₃-x₄ + y₁ =2

2x₁+x₂-3x₃+x₄ + y₂ =6

x₁+ x₂+ x₃+x₄ +y₃=7

тобто штучні змінні y_j вводяться в нерівності і водночас вводяться в цільову функцію з коефіцієнтами M (де М-деяке достатньо велике число).

 

Послідовність симплекс-таблиць має вигляд:

 

	Cj					M	M	M
CБ	XБ	X1	x2	x3	x4	y­1	y­2	y­3	A0	Q
M	y1	1			-1
M	y2			-3
M	y3
	D	-4M+1	-3M+2		-M+1
	x1	1			-1					-
M	y2		-1	-7	(3)	-2				2/3
M	y3			-3		-1				5/2
	D		M+1	8M-2	-5M+2	4M-1
	x1	1	2/3	-1/3		1/3	1/3		8/3	-
	x4		-1/3	-7/3		-2/3	1/3		2/3	-
M	y3		2/3	(11/3)		1/3	-2/3		11/3
	D
	x1	1	8/11			4/11	3/11	1/11	8/3
	x4		1/11			-5/11	-1/11	7/11	2/3
	x2		2/11			1/11	-2/11	1/11	11/3
	D		9/11			M-1/11	M+2/11	M-10/11

 

Таким чином, всі D³0, отже знайдено оптимальний розв’язок допоміжної задачі, при цьому в базисі немає штучних змінних, отже знайдено оптимальний розв’язок вихідної задачі, який співпадає зі знайденим у попередньому випадку.

 

Задача 3.

x₁- 2x₂+ 3x₃®min

2x₁+ 3x₂+4x₃ =1

-2x₁+ x₂ +3x₃ =2

Метод штучних змінних

Складаємо допоміжну задачу:

y₁+ y₂®min

2x₁+ 3x₂+4x₃ + y₁ =1

-2x₁+ x₂ +3x₃ + y₂ =2

 

	Cj
CБ	XБ	X1	x2	x3	Y­1	y­2	A0	Q
	Y1							1/4
	Y2	-2						2/3
	D		-4	-7
	X3	2/4	¾		1/4		1/4
	Y2	-14/4	-2		-3/4		5/4
	D	14/4	5/4		7/4

 

На останній ітерації всі всі D³0, отже знайдено оптимальний розв’язок допоміжної задачі, при цьому в базисі є штучна змінна y₂, отже вихідна задача не має розв’язку.

 

M-метод

 

Складаємо допоміжну задачу:

 

x₁ -2x₂+3x₃ +My₁+ My₂®min

2x₁+ 3x₂+4x₃ + y₁ =1

-2x₁+ x₂ +3x₃ + y₂ =2

	Cj		-2		M	M
CБ	XБ	x1	x2	x3	Y­1	Y­2	A0	Q
M	Y1			4*				1/4
M	Y2	-2						2/3
	D	-1	-4M-2	-7M+3
	X3	2/4	¾		1/4		1/4
M	Y2	-14/4	-5/4		-3/4		5/4
	D

 

Висновки повністю співпадають з попереднім випадком.

Задача 4.

6x₁+ 4x₂ ®min

2x₁+ x₂ ³ 3

x₁ - x₂ £ 1

Щоб привести задачу до стандартного вигляду, треба додати у обмеження-нерівності додаткові (або балансові змінні) і перетворити їх таким чином на обмеження-рівності. При цьому у неріності £ балансові змінні додаються зі знаком +, а в ³ зі знаком -.

Таким чином, система обмежень набуває вигляду

2x₁+ x₂ -x₃ = 3

x₁ - x_2­ +x₄ =1

Якщо всі нерівності мали знак £, то перетворена задача мала б канонічну форму. В іншому разі треба звести задачу до неї одним з наведених вище методів. В данному випадку достатньо зробити одне жорданове перетворення:

Þ

 

	Cj
CБ	XБ	x1	x2	x3	x4	A0	Q
	x2			-1			3/2
	x4	(3)		-1	1		4/3
	D	-2
	x2			-1/3	-2/3	1/3
	x1			-1/3	1/3	4/3
	D			10/3	2/3

 

Оптимальний розв’язок має вигляд:

x₁=4/3, x₂=1/3,

F_min=6*(4/3)+4*(1/3)=28/3

 

Двоїстість у ЛП

Поняття двоїстості.

Пряма задача Двоїста задача

Симетричні

Несиметричні

Приклад 3.

До наведеної ЗЛП записати двоїсту задачу:

За відповідними правилами побудуємо двоїсту задачу:

Зауважимо, що задачі несиметричні, і тому змінна що відповідає рівнянню в системі обмежень прямої задачі, може мати будь-який знак, а змінна - лише невід’ємна.

 

Приклад 4.

До наведенної ЗЛП записати двоїсту задачу:

Перш ніж записати двоїсиу задачу, необхідно пряму задачу звести до відповідного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то вони повинні мати знак “ ”. Тому перше обмеження моделі помножимо на (-1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Тепер за відповідними правилами складемо двоїсту задачу:

Записані задачі симетричні.

 

 

Двоїстий симплекс-метод

Двоїстий симплекс-метод (ДСМ) безпосередньо застосовується до розв'язування майже канонічної задачі лінійного програмування (МКЗЛП), яка формулюється таким чином:

Знайти вектор x = (x1,...,xn), що мiнiмiзує лінійну функ