Розв’язання. Зведемо ЗЛП до канонічного вигляду, помноживши перше рівняння на –1

Зведемо ЗЛП до канонічного вигляду, помноживши перше рівняння на –1.

Оскільки в рівняннях обмежень відсутні базисні змінні, то введемо штучні базисні змінні , і розв’яжемо М-задачу в симплекс-таблиці 19.

Таблиця 19– Симплекс-таблиця М-задачі

		с		-1	-5	-3	М	М
хб	сб	xi	x1	x2	х3	х4	x5	х6	Q
х5	М		-1						7/3

Продовження таблиці 19

x6	М				-1				6/3
без М			-2						∆'j
с М									∆''j
х5	М		-5/3	5/3	10/3			-1/3	1,5
х4	-3		2/3	1/3	-1/3			1/3
без М		-6	-4					-1	∆'j
с М			-5/3	5/3	10/3			-4/3	∆''j
x3	-5	1,5	-0,5	0,5			0,3	-0,1
х4	-3	2,5	0,5	0,5			0,1	0,3
без М	f	-15	-1	-3			-1,8	-0,4	∆'j
с М							-1	-1	∆''j

Оскільки , то отриманий план З Л П: не цілочисловий. Застосуємо метод Гоморі і знайдемо розв’язання З Ц П.

Складемо правильне відсічення

.

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

Одержимо

Додамо це обмеження новим рядком до симплекс-таблиці 20.

Оскільки Dj , то отриманий план: , оптимальний, цілочисловий,

Таблиця 20 – Симплекс-таблиця

				-1	-5	-3
Хб	Сб	Xі	X1	X2	X3	X4	X5	Q
x3	-5	1,5	-0,5	0,5

Продовження таблиці 20

х4	-3	2,5	0,5	0,5				0,5
х5		-0,5	-0,5	-0,5
f	=	-1,5	-1	-3				Dj
x3	-5						-1
х4	-3
x1							-2
f	=	-14		-2			-2	Dj

Зауваження. Якщо розв’язувати З Ц П. на максимум функції мети f, тоді штучні базисні змінні додаються до функції мети з коефіцієнтами – М.

Завдання 6 Розв’язати задачу про розподіл капіталовкладень між чотирма підприємствами

Знайти оптимальний план розподілу капіталовкладень S= 25 грош. один. між чотирма підприємствами, якщо приріст випуску продукції для i-го підприємства, r_i(x), і=1,…,4, залежно від обсягу капіталовкладень, x, відомий і заданий у таблиці 21.

Розв΄язок. Нехай x_k–обсяг капітальних вкладень, виділених k-му підприємству, k=1,2,3,4, x – обсяг капітальних вкладень, виділених на n підприємств, f_n(x)– сумарний максимальний прибуток від n-підприємств при виділенні їм капіталовкладень обсягу х.

Тоді функціональні рівняння Беллмана:

.

Таблиця 21–Обсяг капіталовкладень і приріст випуску продукції для підприємств

Обсяг кап. вкладень X	Приріст продукції по i-му підприємству
r1(x)	r2(x)	r3(x)	r4(x)

Продовження таблиці 21

Перший етап: n=1 , тому що r₁(x) – зростаюча функція. Значення функції f₁(x) наведені у таблиці 22.

Таблиця 22 – Значення функції f₁(x)

x
f1(x)

Другий етап: n=2, .

Усі обчислення для знаходження значень функції f₂(x) наведемо у таблиці 22.

Таблиця 22– Результати розрахунків другого етапу

x2 x							f2(x)	x2^*
	0+18	20+0	-	-	-	-
	0+20	20+18	21+0	-	-	-
	0+27	20+20	21+18	31+0	-	-
	0+31	20+27	21+20	31+18	37+0	-
	0+40	20+31	21+27	31+20	37+18	40+0

x₂^* – оптимальне значення обсягу капітальних вкладень, виділених 2-му підприємству, при 0 ≤ х₂ ≤ х.

Третій етап: n=3, .

Усі обчислення для знаходження значень функції f₃(x) наведемо у таблиці 23.

Таблиця 23– Результати розрахунків третього етапу

x3 x							f3(x)	x3^*
	0+20	16+0	-	-	-	-
	0+38	16+20	27+0	-	-	-
	0+40	16+38	27+20	34+0	-	-
	0+49	16+40	27+38	34+20	40+0	-
	0+55	16+49	27+40	34+38	40+20	41+0

х₃^* – оптимальне значення обсягу капітальних вкладень, виділених 3-му підприємству, при 0 ≤ х₃ ≤ х.

Четвертий етап: n=4, .

Усі обчислення для знаходження значень функції f₄(x) наведемо у таблиці 24.

Таблиця 24– Результати розрахунків четвертого етапу

x4 x							f4(x)	x4^*
	0+20	20+0	-	-	-	-		0;5
	0+38	20+20	23+0	-	-	-
	0+54	20+38	23+20	26+0	-	-
	0+65	20+54	23+38	26+20	31+0	-
	0+72	20+651	23+54	26+38	31+20	40+0

х₄^* – оптимальне значення обсягу капітальних вкладень, виділених 4-му підприємству, при 0 ≤ х₄ ≤ х.

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

- четвертому підприємству 5 грош. один., що забезпечить приріст продукції 20 грош. один.;

- третьому підприємству з 20 грош. один., які залишилися, – 10 грош. один., що забезпечить приріст продукції у 27 грош. один.;

- другому підприємству з 10 грош. один., які залишилися, – 5 грош. один., що забезпечить приріст продукції у 20 грош. один.;

- першому підприємству 5 грош. один., які залишилися, що забезпечить приріст продукції у 18 грош. один..

Перевірка: 20 + 27 + 20 + 18 = 85 = f₄(x).

Задача7 Про заміну устаткування без урахування його залишкової вартості

Постановка задачі. Нехай r(t)– вартість продукції, виробленої за рік на одиниці устаткування, вік якого t років; L(t) – щорічні витрати на обслуговування цього устаткування; S(t)=0 – залишкова вартість устаткування; Р=11грош. один. – вартість нового обладнання. Уведемо функцію φ(t)=R(t)-L(t), різниця між вартістю виготовленої продукції та експлуатаційними витратами. Значення функціі φ(t) за роками наведені у таблиці 25.

Визначити оптимальний цикл заміни устаткування за період часу тривалістю

Таблиця 25– Значення функції φ(t) за роками

t
φ(t)

шість років, причому за ці роки прибуток f₆(t) повинен бути максимальним.

Розв΄язок. Функціональне рівняння Беллмана:

прибуток .

Умови заміни:

;

.

Усі обчислення проведемо за формулами для різних N=1,…..,6:

;

;

;

;

;

.

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

Висновки. Якщо спочатку обладнання нове (), то за шість років роботи прибуток складе 63 грошові одиниці. Причому заміна обладнання не виконується.

Дата добавления: 2015-05-23