Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный технический университет Украины «Киевский политехнический институт»

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

MMDO_Metod

.pdf

Скачиваний:

Добавлен:

12.05.2015

Размер:

689.07 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 75 6 7 > Следующая >>>

отриманий в результаті перетину півплощин, і найбільше значення цільової

функції досягається в його вершині.

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

I.Визначити простір розв’язків і знайти оптимальний розв’язок задачі,

вважаючи, що кожна із зазначених нижче умов замінює (а не доповнює)

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

–Максимальний попит на фарбу I дорівнює 3 т.

–Попит на фарбу I не менш як 2 т.

–Попит на фарбу I рівно на одну тону перевищує попит на фарбу Е.

–Допустимі витрати вихідного продукту В не менш, як 8 тон на добу.

–Допустимі витрати вихідного продукту В не менш, як 8 тон на добу, а

попит на фарбу I перевищує попит на фарбу Е не менш, ніж на одну тону.

II.Знайти оптимальний розв’язок при таких цільових функціях:

–z 3xE xI;

–z 3xE 1.5xI ;

– z xE 3xI .

Приклад 6.	Розв’язати ЗЛП графічно.
Максимізувати	z = 2x1 + 2x2,
при обмеженнях	x1 + x2 ≤ 8;		(10)
	x1 – 4x2 ≤ 2;		(11)
	x2	≤ 5;	(12)
	x1	≥ 1;	(13)
	x1	≥ 0;	(14)
	x2	≥ 0	(15)

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

Не удаетсяотобразить связанный рисунок. Возможно,этот файл был перемещен,переименован или удален.Убедитесь, что ссылка указывает на правильный файл и верное размещение.

Рис. 8

Область допустимих розв’язків задачі – багатокутник ABCDE (рис. 8).

Коефіцієнти цільової функції пропорційні коефіцієнтам обмеження (10): 2 2,

1 1

отже, оптимальний розв’язок задачі – відрізок CD.

Знайдемо координати т. D:

	x2 5							x1 3,
			x2						5.
	x1		x2				8	x2	5.
Знайдемо координати т. C:
								x				34		,
								x						,
	x		x				8	1
	x		x			2	8				5
		1				2					5
	1x1 4x2 2										6		.
								x2					.
											5
Відповідь:	x				3			34						0 ≤ λ ≤ 1; z=16.
Відповідь:	1						(1 )				5 ,			0 ≤ λ ≤ 1; z=16.
									6
	x2				5				6
										5
Приклад 7. Розв’язати ЗЛП графічно.
Максимізувати	z			3	x1		x2,
Максимізувати	z				x1		x2,
при обмеженнях			2
при обмеженнях	– x1 + x2 ≤ 1;													(16)
	x1 + x2 ≥ 2;													(17)
	x1 – 4x2 ≤ 1;													(18)
	x1 ≥ 0;													(19)
	x2 ≥ 0.													(20)
										44

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

Рис. 9

Відповідь: Задача не має розв’язку. Область допустимих розв’язків та цільова функція є необмеженими.

Приклад 8. Розв’язати ЗЛП графічно.


Максимізувати	z		3	x1 x			2,
Максимізувати	z			x1 x			2,
при обмеженнях		2
при обмеженнях	–x1 x2					1;		(21)
	x1			3	x2		8;	(22)
	x1				x2		8;	(22)
		2
	x1 –4x2 1;							(23)
	x1	≥ 0 ;						(24)
	x2	≥ 0.						(25)

Рис. 10

Відповідь: Задача не має розв’язку. Обмеження задачі – несумісні.

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

2.3. Завдання до контрольної роботи

Розв’язати ЗЛП графічно.
1. max z = 2x1 + 1x2 ;		(1)	2. max z = 6x1 + 10x2;		(1)	3. max z = x1 – 2x2 ;			(1)
1x1 – 10x2 10;			–1x1 + 1x2 5;			1x1	– 2x2 4;
2x1 – 2x2 20;		(2)	–1x1 + 5x2 40;		(2)	5x1	+ 2x2 10;		(2)
–10x1 + 1x2 10;		(3)	3x1	+ 5x2 75;	(3)	4x1	– 3x2 12;		(3)
2x1 – 1x2 50;		(4)	5x1	– 1x2 60;	(4)	7x1	+ 4x2 28;		(4)
x1 , x2 0.			2x1	– 5x2 15;	(5)	x1 , x2 0.
			x1 , x2 0.
4. max z = 1x1 + 1x2 ;		(1)	5. max z = 2x1 + 1x2 ;		(1)	6. max z = x1 + 2x2 ;			(1)
5x1	– 2x2 10;		1x1 – 1x2 4;			1x1		– 5x2 5;
–1x1	+ 1x2 5;	(2)	1x1 + 1x2 10;		(2)	–3x1		+ 1x2 3;	(2)
1x1	+ 1x2 6;	(3)	4x1 – 1x2 12;		(3)	–4x1		+ 5x2 20;	(3)
–1x1	+ 1x2 = 1;	(4)	7x1 + 1x2 7;		(4)	–1x1		+ 2x2 10;	(4)
x1 , x2 0.			x1 , x2 0.			x1 , x2 0.
7. max z = 10x1 – 4x2 ;		(1)	8. max z = 2x1 – 4x2 ;		(1)	9. max z = 2x1 + 3x2 ;			(1)
–2x1	+ 1x2 10;		8x1 – 5x2 16;			–2x1		+ 1x2 4;
4x1	+ 5x2 60;	(2)	1x1 + 3x2 2;		(2)	3x1		– 8x2 24;	(2)
5x1	– 2x2 60;	(3)	2x1 + 7x2 9;		(3)	x2	3;		(3)
2x1	– 5x2 40;	(4)	x1 , x2 0.			x1	, x2 0.
x1 , x2 0.
10. max z = –2x1 + 1x2 ;			11. max z = 1x1 + 1x2 ;			12. max z = –2x1 + 1x2 ;
2x1	+ 1x2 8;	(1)	1x1	+ 1x2 1;	(1)	2x1		+ 1x2 8;	(1)
1x1	+ 1x2 6;	(2)	–5x1 + 1x2 0;		(2)	1x1		+ 3x2 6;	(2)
–3x1	+ 2x2 3;	(3)	–1x1 + 5x2 0;		(3)	3x1		+ 1x2 3;	(3)
1x1	1;	(4)	1x1 + 1x2 6;		(4)	–1x1		+ 1x2 = 3;	(4)
x1 , x2 0.			x1 , x2 0.			x1 , x2 0.
13. max z = 11x1 + 11x2 ;			14. max z = 5x1 + 2x2 ;			15. max z = x1 – 2x2 ;
1x1	+ 1x2 4;	(1)	2x1	+ 1x2 11 ;	(1)	–3x1		+ 2x2 9 ;	(1)
2x1	+ 5x2 5;	(2)	–3x1 + 2x2 10 ;		(2)	3x1		+ 4x2 27;	(2)
5x1	+ 2x2 5;	(3)	3x1	+ 4x2 12 ;	(3)	2x1		+ 1x2 12;	(3)
1x1	3;	(4)	1x1	– 2x2 4 ;	(4)	1x2		= 6;	(4)
1x2	2;	(5)	x1 , x2 0.			x1	, x2 0.

x1 , x2 0.

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

16. max z = 2x1;		(1)	17 max z = 10x1 + 2x2 ;		(1)	18 max z = 2x1 + 3x2 ;		(1)
1x1	+ 1x2 10;	(1)	4x1	– 2x2 5 ;	(1)	–2x1	+ 1x2 2;	(1)
–3x1	+ 2x2 6;	(2)	–1x1 + 2x2 5 ;		(2)	1x1	+ 2x2 6;	(2)
1x1	+ 1x2 3;	(3)	1x1	+ 1x2 4 ;	(3)	1x1	+ 2x2 2;	(3)
1x1	3;	(4)	1x1	+ 1x2 2 ;	(4)	3x1	+ 2x2 6;	(4)
1x2	5;	(5)	x1 , x2 0.			x1 , x2 0.
x1 , x2 0.
19. max z = 2x1 – 1x2 ;		(1)	20. min z = 5x1 + 2x2 ;		(1)	21. max z = 7x1 – 1x2 ;		(1)
–1x1	+ 1x2 4 ;	(1)	1x1	+ 7x2 7;	(1)	1x1	+ 1x2 3;	(1)
6x1	+ 6x2 36;	(2)	–2x1 + 1x2 5;		(2)	5x1	+ 1x2 5;	(2)
2x1	– 3x2 6;	(3)	2x1	+ 5x2 10;	(3)	1x1	+ 5x2 5;	(3)
1x1	+ 1x2 4;	(4)	5x1	+ 2x2 10 ;	(4)	1x1	4;	(4)
1x1	+ 1x2 = 5;	(5)	7x1	+ 1x2 7;	(5)	1x2	5;	(5)
x1 , x2 0.			1x1	5;	(6)	x1 , x2 0.
			1x2	5;	(7)
			x1 , x2 0.
22. min z = 2x1 + 4x2 ;		(1)	23. max z = 2x1 + 2x2 ;		(1)	24. max z = 7x1 + 6x2 ;		(1)
3x1	+ 1x2 9;	(1)	–3x1 + 2x2 6;		(1)	1x1	+ 1x2 14;	(1)
1x1	+ 2x2 6;	(2)	1x1	+ 1x2 3;	(2)	3x1	– 5x2 15;	(2)
1x1	– 1x2 3;	(3)	1x1	3;	(3)	6x1	+ 3x2 24;	(3)
1x2	5;	(4)	1x2	5;	(4)	1x1	= 15;	(4)
x1 , x2 0.			4x1	+ 5x2 20;	(5)	1x2	10;	(5)
			x1 , x2 0.			x1 , x2 0.

25.Сконструювати дві ЗЛП (записати систему обмежень та розв’язати графічно),

у яких поєднання “вид ОДР” – “оптимальний розв’язок” не збігався би із завданнями, отриманими згідно з варіантом. (Кількість обмежень ЗЛП – не менше 3-х).

26.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – відрізок, оптимум – точка.

27.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – відрізок, оптимум – альтернативний.

28.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – промінь, оптимум – точка.

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

29.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – промінь, оптимум – альтернативний.

30.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – багатокутник, оптимум – точка.

31.Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в

якій ОДР – багатокутник, оптимум – альтернативний.

32.Навести приклади можливих видів множин допустимих розв’язків ЗЛП та

видів множин оптимальних розв’язків у R2 (дати їх графічну ілюстрацію).

Варіанти контрольної роботи подані в табл. 32.

			Таблиця 32
Номер варіанта	Завдання	Номер варіанта	Завдання
1	1, 24, 25	14	11, 14, 25
2	2, 23, 25	15	9, 15, 25
3	3, 22, 25	16	10, 13, 25
4	4, 21, 25	17	8, 16, 25
5	5, 20, 25	18	7, 17, 25
6	6, 19, 25	19	3, 22, 25
7	7, 18, 25	20	4, 18, 25
8	8, 16, 25	21	5, 20, 25
9	9, 17, 25	22	6, 19, 25
10	10, 14, 25	23	2, 11, 25
11	11, 15, 25	24	1, 15, 25
12	12, 13, 25	25	3, 12, 25
13	11, 24, 25	26	1, 21, 25

Домашнє завдання. “Основи аналізу на чутливість”. Побудувати математичну модель, розв’язати та виконати постоптимальний аналіз моделі із завдання 1, розд. 1.3.

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

3.ПОСТОПТИМАЛЬНИЙ АНАЛІЗ МОДЕЛЕЙ

3.1.Аналіз моделей після знаходження оптимального розв’язку

Постоптимальний аналіз (аналіз моделей на чутливість) – це процес,

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

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

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

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

3.2. Перша задача аналізу на чутливість

На скільки зменшити або збільшити запаси ресурсів?

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

Відзначимо, що нерівності моделі типу “ ” звичайно можуть бути інтерпретовані, як обмеження на використання лімітованого ресурсу. А

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

“обмеження на використання ресурсу”, а праві частини обмежень називати

“запасами ресурсів”.

При аналізі змін запасів ресурсів особливо важливі такі два аспекти:

–На скільки можливо збільшити (зменшити) запас деякого ресурсу для

покращення отриманого оптимального значення цільової функції z?

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

– На скільки можливо зменшити (збільшити) запас деякого ресурсу при

зберіганні отриманого оптимального значення цільової функції z?

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

Перш за все класифікуємо обмеження лінійної моделі на

–зв’язуючі (активні);

–незв’язуючі (неактивні).

Пряма, яка представляє зв’язуючі обмеження, проходить через оптимальну

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

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

ресурсів (тобто таких, що є у деякому залишку).

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

–гранично допустиме збільшення (зниження) запасу дефіцитного ресурсу,

що дозволяє покращити знайдений оптимальний розв’язок (у випадку обмеження “ ” питання стоїть таким чином: визначити гранично допустиме збільшення рівня запасу ресурсу, що дозволяє покращити знайдений раніше оптимальний розв’язок, а у випадку обмеження “ ”

визначається гранично допустиме зниження вимог, яке дозволяє покращити знайдений раніше оптимальний розв’язок);

–гранично допустиме збільшення (зниження) запасу недефіцитного

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

випадку обмеження “ ” визначається гранично допустиме зниження

запасу ресурсу, яке не змінює знайденого раніше розв’язку, а у випадку

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

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

Розглянемо Задачу про фарби, що графічно розв’язана в пiдроздiлi 2.2. В

цій задачі продукти А i В є дефіцитними, оскільки обмеження (4) i (5) є

зв’язуючими. Ресурси (6) i (7) є недефіцитними. Для покращення значення цільової функції рівень запасів дефіцитних ресурсів повинен бути трохи збільшений. При деякому зниженні рівня запасів недефіцитних ресурсів значення цільової функції не змінюється.

3.2.1. Гранично допустиме збільшення запасу дефіцитного ресурсу

Ресурс А. При збільшенні запасу цього ресурсу пряма (4) (або відрізок CD)

пересувається наверх паралельно сама собі, поступово “стягуючи” в точку трикутник CDK.

Рис. 11

При цьому:

–зв’язуючими стають обмеження (5) і (7);

–оптимальному розв’язку відповідає точка K;

–простором допустимих розв’язків стає багатокутних ABKEF;

–обмеження (4) стає надлишковим і будь-яке подальше зростання запасу ресурсу А не впливає ні на простір розв’язків, ні на оптимальний розв’язок.

Означення. Обмеження є надлишковим, якщо його виключення не впливає

ні на простір розв’язків, ні на оптимум.

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

Таким чином, обсяг ресурсу А не потрібно збільшувати понад тієї границі,

коли відповідне йому обмеження (4) стає надлишковим, тобто пряма (4)

проходить через нову оптимальну точку. Визначимо цей граничний рівень:

– встановимо координати точки K, розв’язавши відповідну систему рівнянь.

Отримаємо: xE 3, xI 2;

–визначимо максимально допустимий запас ресурсу А, підставивши координати точки K у ліву частину обмеження (4):

b1(K) xE 2xI 3 2 2 7 (т);

значення цільової функції в точці К: z(K) 13 (тис. грн.).

Ресурс В. Розглянемо тепер питання про доцільність збільшення дефіцитного ресурсу (5) (початкового продукту В).

Рис. 12

При збільшенні запасу цього ресурсу пряма (5) (чи відрізок CB)

переміщується вправо паралельно сама собі, поступово “стягує” в точку трикутник CBJ. Новою оптимальною точкою стає точка J, де перетинаються прямі (4) і (9). Тепер:

–простір допустимих розв’язків – багатокутник AJDEF;

–встановимо координати точки J, розв’язавши відповідну систему рівнянь:xE 6, xI 0;

–визначимо максимально допустимий запас ресурсу B, підставивши координати точки J у ліву частину обмеження (5):

You created this PDF from an application that is not licensed to print to novaPDF printer (http://www.novapdf.com)

<<< < Предыдущая 1 2 3 45 / 75 6 7 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
11.08.2019135.17 Кб9MK-Lekziy-1.doc
#
15.08.2019105.98 Кб6Mk-Lekziy-4.doc
#
21.11.2019217.09 Кб6MKR1.doc
#
21.11.201991.65 Кб4MKR1_1-17.doc
#
17.03.2016263.68 Кб11MKR_TEC.doc
#
12.05.2015689.07 Кб42MMDO_Metod.pdf
#
12.05.20151.15 Mб36MMDO_МетодВказівки_ПММ+ГрС+ПОА_.doc
#
12.05.2015876.42 Кб11modi2.pdf
#
17.03.201658.16 Кб38Modul_2_kurs_1_semestr.docx
#
31.08.2019678.4 Кб43MOJ_OTChET1.doc
#
24.11.20191.43 Mб14Mol_fizyka.doc