Быстрый поиск

Контрольная работа: Розв'язок задачі лінійного програмування

Розв’язати графічно задачу лінійного програмування

Розв’язання:

Розглянемо на площині х1Оx2 сумісну систему лінійних нерівностей

(1)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою (i = 1, 2,...,т). Умови невід’ємності визначають півплощини відповідно з граничними прямими . Система сумісна, тому півплощини, як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожній із який є розв’язком даної системи (рис. 1.).

Рис. 1.

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

Якщо в системі обмежень (1) п = 3, то кожна нерівність геометрично представляє півпростір тривимірного простору, гранична площина котрого (i = 1, 2,...,т), а умови невід’ємності – півпростори з граничними площинами відповідно хі = 0 (і = 1,2,3). Якщо система обмежень сумісна, то ц півпростори, як опуклі множини, перетинаючись, утворять у тривимірному простор спільну частину, що називається багатогранником розв’язків. Багатогранник розв’язків може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (1) п > 3; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною (i = 1, 2,...,т),. Кожному обмеженню виду (3.7) відповідають гіперплощина та напівпростір, який лежить по один бік цієї гіперплощини, а умови невід’ємності – півпростори з граничними гіперплощинами хі = 0 (і = 1,2,3,...,n).

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

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

Цільову функцію в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.

Запишемо систему нерівностей у вигляді:

Розв’яжемо задачу графічно.

Побудуємо систему обмежень (1), (2), (3).

Побудуємо також лінії рівня: х1 + х2 = С. С = const.

Розв’язок на перетині Ох2 та (3):

Отже, розв’язок є точка , причому .

Задача 2

Розв’язати симплекс методом:

Розв’язання:

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості необхідно застосовувати загальний метод розв’язування задач лінійного програмування. З властивостей розв’язків задач лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (можливих допустимих планів задачі). Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів , отже загальна кількість опорних планів визначається кількістю комбінацій

Задачі, що описують реальні економічні процеси мають значну розмірність і простий перебір всіх можливих опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Отже необхідне використання методу, який дає можливість скоротити кількість обчислень. Такий метод запропоновано американським вченим Дж. Данцігом у 1949 році – так званий симплекс-метод.

Ідея методу полягає в здійсненні направленого перебору допустимих планів, таким чином, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який є хоча б не гіршим за попередній. Значення функціоналу при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).

Процес розв’язування задачі симплекс-методом має ітераційний характер: однотипові обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.

Отже, симплекс-метод — це поетапна обчислювальна процедура, яка дозволяє починаючи з відомого опорного плану за скінчену кількість кроків отримати оптимальний план задачі лінійного програмування.

Розглянемо задачу лінійного програмування подану в канонічній формі:

Не втрачаючи загальності припустимо, що система містить перш m одиничних векторів:

(1)

(2)

(3)

Система (1) у векторній формі матиме вигляд:

(4)

де

, ,..., ,

– лінійно незалежні одиничн вектори m-вимірного простору, що утворюють одиничну матрицю і складають базис цього простору. Тому в розкладі (4) базисними змінними будуть , інші – вільні змінні. Покладемо всі вільні змінні рівними нулю . Оскільки , а вектори – одиничні, отримаємо один із розв’язків системи (4), тобто допустимий план.

(5)

Такому плану відповідає розклад

(6)

де – лінійно незалежні і за властивістю 3 розв’язків задачі лінійного програмування план є кутовою точкою багатогранника розв’язків, а отже може бути початковим опорним планом.

Розглянемо, як виходячи з початкового опорного плану (5) перейти до наступного опорного плану, що відповідає процесу перебору кутових точок багатогранника розв’язків.

Оскільки є базисом m-вимірного простору, то кожен з векторів співвідношення (5) може бути розкладений за векторами базису причому єдиним чином:

Розглянемо такий розклад для довільного не базисного вектора, наприклад, для :

(7)

Припустимо, що у виразі (7) існує хоча б один додатній коефіцієнт .

Введемо до розгляду деяку поки що невідому величину , помножимо на неї обидві частини рівності (3.34) і віднімемо результат з рівності (3.33), маємо:

(8)

Таким чином вектор

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

(9)

З (3.36) отримуємо, що для шуканого має виконуватися умова . Отже вектор буде планом задачі для будь-якого q, що задовольняє умову

де мінімум знаходимо по тих i, для яких .

Опорний план не може містити більш ніж m додатних компонент, тому в плані необхідно перетворити в нуль хоча б одну з компонент. Припустимо, що

для деякого значення і, тоді відповідна компонента плану перетвориться в нуль. Нехай це буде перша компонента плану, тобто

Підставимо значення у вираз:

якщо позначити

, ,

то рівняння можна подати у вигляді розкладу:

якому відповідає наступний опорний план:

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

Узагальнюючи розглянутий процес, маємо – визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. Така процедура відповідає переходу від одного базису до ншого за допомогою методу Жордана-Гауса.

Необхідно відмітити, що для випадку коли вектор підляга включенню в базис, а в його розкладі всі , то, очевидно, не існує такого , який виключав би один з векторів розкладу (3.35). В такому випадку план містить m+1 додатних компонент, отже система векторів буде лінійно залежною і визнача не кутову точку багатогранника розв’язків, а функціонал не може в ній досягати свого максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.

Симплексний метод здійснює направлений перебір опорних планів, що дозволяє переходити від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням, що він надає функціоналу. Отже окремим питанням постає вибір вектору, який необхідно вводити в базис при здійсненн тераційної процедури симплексного методу.

Теорема 1. Якщо для деякого вектора виконується умова , то план не є оптимальним можливо побудувати такий план Х, для якого виконуватиметься нерівність .

Доведення. Помножимо (3.39) і (3.40) на і віднімемо результати відповідно з (3.37) та (3.38), отримаємо:

(*)

У співвідношенні до обох частин додається величина для , додатні, тому завжди можливо знайти таке , що всі коефіцієнти при векторах були невід’ємними, іншими словами отримати новий план задачі виду:

якому згідно відповідає значення функціоналу

Так як за умовою теореми

і , то .

Що і потрібно було довести.

Теорема 2. Якщо для деякого вектора виконується умова , то план не є оптимальним можливо побудувати такий план Х, для якого виконуватиметься нерівність .

Запишемо канонічну задачу:

Розв’яжемо симплекс-методом:

	1	1	0	-M	0	0
	x1	x2	x3	x4	x5	x6	B	T
x4	4	3	-1	1	0	0	12	3	**
x5	-1	2	0	0	1	0	4	–
x6	1	-1	0	0	0	1	4	4
F	-1	-1	0	0	0	0	0	0
Mf	-4	-3	1	0	0	0	-12	0
	**

	1	1	0	-M	0	0
	x1	x2	x3	x4	x5	x6	B	T
x1	1	0,75	-0,25	0,25	0	0	3	4
x5	0	2,75	-0,25	0,25	1	0	7	2,545	**
x6	0	-1,75	0,25	-0,25	0	1	1	–
F	0	-0,25	-0,25	0,25	0	0	3	0
Mf	0	0	0	1	0	0	0	0
		**

	1	1	0	-M	0	0
	x1	x2	x3	x4	x5	x6	B	T
x1	1	0	-0,1818	0,1818	-0,2727	0	1,091	–
x2	0	1	-0,09091	0,09091	0,3636	0	2,545	–
x6	0	0	0,09091	-0,09091	0,6364	1	5,455	60	**
F	0	0	-0,2727	0,2727	0,09091	0	3,636	0
Mf	0	0	0	1	0	0	0	0
			**