2 курс. Ден. ФК, УП, ЕП 12 / Економіко математичні методи та моделі (Оптимізаційні методи) Ч.1 Ден. 2010

розв'язана. Інакше необхідно вибрати найбільшу за модулем компоненту

	bi	< 0 і відповідну змінну xi виключити з базису.
	3.	Якщо в l -тому рядку, що відповідає змінній xi , не міститься жодного
	aij	< 0, то		цільова функція			двоїстої	задачі	необмежена	на
	багатограннику розв'язків, а початкова задача розв'язку не має.
	4.	Якщо в l -тому рядку існують деякі aij						< 0, тоді для відповідних
	стовпчиків визначають аналогічно прямому симплекс-методу оцінки:
	5.	θ j = min		j		(aij < 0) , що	дозволяє вибрати		вектор, який	буде
				aij

включено в базис.

6.Виконують крок методу повних виключень Жордана-Гауса переходять до нової симплексної таблиці.

7.Переходять до п.2.

Завдання для самостійної роботи

1. Розв’яжіть графічним методом наступні задачі:

1.1. z = 3x1 + 4x2 (extr),

3x1 +4x2		≥12,
4x1 +3x2		≥12,
	0 ≤ x ≤5,
	1
	x2 ≥5.

1.3. z = -2x1 + 3x2 (extr),

x1 +2x2 ≥11,
4x		+2x	2	≤15,
	1
x1 +3x2 ≤ 20,
	0	≤ x	≤5,
		1
		x2 ≥ 0.

1.2. z = x1 + 4x2 + 2 (extr),

x1 + x2 ≤5,

4x1 + x2 ≥8,

x1 − x2 ≤ 0,

x1, x2 ≥ 0.

1.4. z = 2x1 – 25 (extr),

x1 +3x2				≤15,
				≤15,
5x1 + x2
	x1 + x2 ≥ 0,
x −5x		2		≥ 0,
	1
	x1, x2		≥ 0.

40

2. Знайдіть розв'язок таких задач лінійного симплекс-методом:

2.1. z = 2x1 − x2 +3x3 −4x4 (min),

2.2.

z = −3x1 −4x2 (min),

x1 + 2x2 −3x3 +4x4 ≤5,

x

≥10,

x

2

≥ 5,

− x

+ 2x

−3x

≥

2,

1

x

+ 2x

≤ 20,

4x

2

4

2

1

3

1

2x

+3x

2

−5x

+ x

4

=

8,

− x

+ 4x

≤

20,

1

3

2

1

x j ≥ 0,

j =1,2,3,4;

x2 ≥ 0;

2.3. z = −x1 + x2 − x3 + x4 (min)

2.4.

z = 2x1 − 2x2 + 4x3 (min),

x1 + 2x2 − x3 − x4 =1,

− x2 + 4x3 ≥1,

+ 2x2

+3x3 + x4 = 2,

− x1 +5x2 ≤1,

− x1

x

+5x

2

+ x

− x

4

= 5,

− x

+ 2x

+3x ≤ 9;

1

3

2

x j ≥ 0,

j =1,2,3,4;

1

3

Питання для самоконтролю

1.Сформулюйте економічну та математичну постановку задачі лінійного програмування (ЛП).

2.Які є форми запису задач лінійного програмування? Як звести задачу ЛП до канонічної форми?

3.Що таке цільова функція задачі ЛП ? Яка область називається областю допустимих планів ? Який план називається опорним ? Який опорний план називається невиродженим ?

4.За яких умов у задачі ЛП з необмеженою областю допустимих планів існує розв’язок. Що означає умова несумісності допустимих планів ?

5.В чому полягає геометрична інтерпретація множини допустимих розв'язків задачі лінійного програмування?

6.Як розв’язати розв'язати задачу лінійного програмування. з двома змінними графічно?

7.У чому полягає симплексний метод розв’язування задач ЛП?

8.В чому полягає збіжність симплекс-методу?

9.Опишіть М-метод, інші методи розв’язування задач лінійного програмування.

Бібліографічний список до теми

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

41

Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач

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

План вивчення теми

1.Основна та двоїста задачі як пара взаємоспряжених задач ЛП. Правила побудови двоїстих задач.

2.Економічна інтерпретація пари двоїстих задач. Основні теореми двоїстості задач та їх економічний зміст.

3.Післяоптимізаційний аналіз задач ЛП. Аналіз розв’язків лінійних економіко-математичних моделей.

4.Оцінка рентабельності продукції, яка виробляється, і нової продукції.

5.Аналіз обмежень дефіцитних і недефіцитних ресурсів. Аналіз коефіцієнтів цільової функції. Аналіз коефіцієнтів технологічної матриці для базисних і вільних змінних.

6.Приклади практичного використання двоїстих оцінок у аналізі економічних задач.

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

Методичні рекомендації до самостійної роботи

При вивченні цього питання слід звернути увагу не те, що двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

42

2.Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.

3.Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі – на визначення найменшого значення (min), і навпаки.

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

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

6.Матриця, що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків – рядками.

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

Для виробництва n виробів продукції використовується m видів ресурсів, запаси яких обмежені значенням bi (i =1,m) . Норма витрат кожного ресурсу на одиницю продукції становить aij ( j =1,n;i =1,m).

Ціна одиниці продукції j-го виду дорівнює c j ( j =1,n). Математична

модель задачі має такий вигляд:

n

max Z = max ∑c j x j ;

j =1

43

n

∑aij ≤ bi (i =1, m);

j=1

x j ≥ 0(j =1.n).

Пряма задача полягає у визначення такого оптимального плану виробництва продукції X * = (x1*, x2* ,..., xn* ), який дає найбільший дохід.

Двоїста задача до поставленої прямої буде така:

m

F= ∑bi yi → min;

i=1

m

∑aij yi ≥ c j (i =1,n);

i=1

yi ≥ 0(i =1,m).

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

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

недефіцитним. Якщо ж двоїста оцінка yi > 0 , то і-й ресурс використовується для оптимального плану виробництва продукції повністю і називається дефіцитним. У цьому разі величина двоїстої оцінки показує, на скільки збільшиться значення цільової функції Z, якщо запас відповідного ресурсу збільшити на одні умовні одиницю.

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

44

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

продукцію не вигідно, вона нерентабельна і в оптимальному плані прямої задачі відповідна x j = 0 . Якщо ж загальна оцінка всіх ресурсів

дорівнює ціні одиниці продукції, то виготовляти таку продукцію доцільно, вона рентабельна і в оптимальному плані прямої задачі відповідна змінна x j > 0 .

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

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

-склад змінних та їх значення в оптимальному плані не змінюються;

-склад змінних залишається попереднім, але їх оптимальні значення змінюються;

-змінюються склад змінних та їх значення в оптимальному плані задачі.

2.Уведення додаткового обмеження в математичну модель задачі впливає на допустимість розв'язку і не може вплинути на поліпшення значення цільової функції.

3.Уведення нової змінної в математичну модель задачі впливає на оптимальність попереднього лану і не погіршує значення цільової функції.

45

Завдання для самостійної роботи

1. Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплекс-методом і визначити оптимальний план іншої задачі.

Z = −30x1 +10x2 → max;

за умов

2x1 − x2 − x3 ≥ −2,−3x1 +2x2 − x3 ≤ 3,

xj ≥ 0, j =1,3.

2.Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплекс-методом і визначити оптимальний план іншої задачі.

Z = 4x1 +3x2 + x3 → min;

за умов

4x1 −3x2 + x3 ≥ 2,x1 + x2 + x3 ≤5,

xj ≥ 0, j =1,3.

3.Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплекс-методом і визначити оптимальний план іншої задачі.

Z =3x1 +2x2 +5x3 → max;

за умов

x1 +2x2 + x3 ≤50,
	3x1 + x3 ≥15,
	x	+4x	2	≤ 40,
	1
	x j	≥ 0,	j =
					1,3.

46

4. Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплекс-методом і визначити оптимальний план іншої задачі.

Z = 2x1 + x2 +3x3 + x4 → max

за умов

	+ 2x2 +5x3 − x4 = 4
x1
x1 − x2 − x3 + 2x4 =1 .
x		x	4	≥ 0
1,...,

5. Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплекс-методом і визначити оптимальний план іншої задачі.

Z = 6x1 + x2 +4x3 −5x4 → max

за умов

3x1 + x2 − x3 + x4 = 4

5x1 + x2 + x3 − x4 = 4

x1,..., x4 ≥ 0

6.У наведеної далі задачі виконати дії:

1)записати математичні моделі прямо та двоїстої задач

2)записати оптимальні плани прямої та двоїстої задач, подати їх економічний аналіз;

3)визначити статус ресурсів, що використовуються для виробництва продукції, та рентабельність кожного виду продукції;

4)обчислити інтервали стійкості двоїстих оцінок стосовно зміни запасів дефіцитних ресурсів;

5)розрахувати інтервали можливих змін ціни одиниці рентабельної продукції.

Підприємство виготовляє три види продукції А, В і С, використовуючи для цього три види ресурсів 1, 2, 3. Норми витрат усіх ресурсів на одиницю продукції та запаси ресурсів наведено в таблиці:

47

Ресурс		Норма витрат на одиницю продукції			Запас
			за видами
					ресурсу
		А	В	С
1		18	15	12	360
2		6	4	8	192
3		5	3	3	180
Відома		ціна одиниці	продукції кожного	виду: А – 9	ум.од, В – 10

ум.од. і С – 16 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший дохід.

Остання симплекс-таблиця даної задачі має такий вигляд:

Базис		Сбаз	План	9	10	16	0	0	0
				х1	х2	х3	х4	х5	х6
Х2		10	8	1	1	0	1/9	-1/6	0
Х3		16	20	¼	0	1	-1/18	5/24	0
Х6		0	96	5/4	0	0	-1/6	-1/8	1
	j	≥ 0	400	5	0	0	2/9	5/3	0

Питання для самоконтролю

1.У чому сутність двоїстості у лінійному програмуванні?

2.Які взаємосопряжені задачі називаються симетричними, які – несиметричними?

3.Сформулюйте алгоритм побудови двоїстих задач.

4.Як за розв’язком прямої задачі знайти розв’язок двоїстої задачі?

5.Скільки змінних та обмежень має двоїста задача відповідно до прямої?

6.Сформулюйте теореми двоїстості та наведіть їх економічне тлумачення.

7.Як за розв’язком прямої задачі ЛП знайти розв’язок двоїстої ?

8.Дайте економічну інтерпретацію прямої та двоїстої задач.

9.Як визначити, що ресурс є дефіцитним (недефіцитним)? Як визначити, що продукція є рентабельна (нерентабельна)?

10.Як впливає на оптимальній план введення нової змінної?

11.Як визначити статус ресурсів прямої задачі та інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів?

12.Як визначити план виробництва продукції та зміну доходу

48

підприємства, якщо збільшити (зменшити) обсяг ресурсів?

13. Як визначити рентабельність кожного виду продукції, що виготовляється на підприємстві?

Бібліографічний список до теми

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

Тема 5. Транспортна задача

Мета: опрацювання питань згідно запропонованого плану вивчення теми, вивчення постановки транспортної задачі та методів її розвязання.

План вивчення теми

1.Постановка транспортної задачі, особливості її структури та її властивості. Знаходження опорних планів транспортної задачі.

2.Метод потенціалів знаходження розв’язків транспортної задачі.

3.Економічний аналіз транспортних задач.

4.Застосування транспортних моделей для розв’язування деяких економічних задач.

Методичні рекомендації до самостійної роботи

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

Математична модель транспортної задачі має такий вигляд:

m n
Z = ∑∑cij * xij → min	(9)

i=1 j=1

за обмежень

49