Риклади розв’язування задач.

ема 1. "Побудова математичних моделей задач лінійного програмування".

адача 1.

Для виготовлення чотирьох видів продукції , необхідно використати 3 типи обладнання А,В,С. Витрати часу на обробку одного виробу для кожного типу обладнання, ресурси обладнання і прибуток від реалізації кожного виробу приведені в таблиці

Тип обладнання	Термін часу на 1 виріб.	Ресурс обладнання
Р1	Р2	Р3	Р4
А В С
Прибуток

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

адача 2.

В ливарному цеху для отримання сплаву необхідного хімічного складу і якості в рідкий метал додається 4 хімічних елемента А,В,С,D. На 1т рідкого металу потрібно не менше 0,8 кг елемента А; 1, 2 кг елемента В; 0,4 кг елемента С; 0,9 кг елемента D. В якості присадок використовують 2 природні речовини, одна з яких вартістю 5 у.о./кг містить в одному кілограмі 0,2 кг елемента А, 0,2 кг елемента В; 0,6 кг елемента D, а друга вартістю 6 у.о./кг містить в одному кілограмі 0,2 кг елемента А; 0,4 кг – В і 0,4 кг – С. Встановити оптимальну пропорцію (кількість) речовин, щоб отримати із 1т рідкого металу сплав при забезпеченні мінімальної необхідної маси елементів при мінімальних витратах на придбання обох речовин.

адача 3.

Фірма спеціалізується на виробництві парникової суміші, що складається із землі, торфу і гумусу. Земляна суміш містить ці компоненти в пропорції 3:6:1, а суперсуміш у співвідношенні 4:3:3. Щомісячно фірма може замовити 10,4 т землі, 15 т торфу та 6,8т гумусу. 1т суміші приносить прибуток 280 грн., а 1т суперсуміші – 480 грн. Яку кількість суміші і суперсуміші треба виготовити, щоб отримати максимальний прибуток?

адача 4.

Фірма випускає продукцію двох видів. Кожний з цих видів вимагає певного часу на виготовлення і монтаж. Виріб першого виду потребує 5 годин на виготовлення і 2 години на монтаж. Виріб другого виду вимагає 3 годин на виготовлення і 4 години на монтаж. За робочий тиждень фірма має 126 годин на виготовлення і 80 годин на монтаж виробів. Прибуток від реалізації виробів першого виду 200 грн., а другого – 150 грн. Яку кількість виробів кожного виду протягом тижня потрібно виготовити, фірмі, щоб отримати найбільший прибуток?

адача 5.

Фірма складає телевізори, відеомагнітофони і відеоплеєри, використовуючи комплектуючи вузли трьох видів А, В, С. Запаси комплектуючих вузлів А,В,С, на складі відповідно становлять 800, 450 і 600 шт. Продаж телевізора, відеомагнітофона та відеоплеєра приносить прибуток 75 грн., 50 грн. і 35 грн., відповідно. Витрати комплектуючих вузлів на кожний тип виробів задаються таблицею:

Товар	Комплектуючі
А	В	С
Телевізор
Відеомагнітофон
Відеоплеєр

Знайти оптимальний план випуску продукції виробів, який максимізує прибуток фірми.

адача 6.

Фермер вирощує озиму пшеницю і цукровий буряк на площі не більше 20 га, виділивши під цукровий буряк не менше 5 га. Витрати праці (людино-дні) по кожній культури та наявний ресурс відповідно на 1 га складають 5, 25 і 270. Витрати обладнання (людино - дні) по кожній культурі та наявний ресурс відповідно на 1 га складають 2,8 і 80. Прибуток від реалізації з 1 га урожаю озимої пшениці і цукрового буряка 0,7 та 1,0 тис грн., відповідно. Знайти оптимальний план посіву за умови максимального прибутку від реалізації урожаю.

адача 7.

Невелика птахоферма має розрахувати кормовий раціон на 1000 курчат, яких вирощують до 8-тижневого віку. Нехтуючи тим, що тижневі витрати кормів для курчат залежать від їхнього віку, вважатимемо, що в середньому за 8 тижнів вони досягають маси 500г. З цією масою кормовий раціон курчат має задовольняти певні вимоги поживності. Сформулюємо ці вимоги у спрощеному вигляді, враховуючи лише 2 поживні речовини: білок і клітковину, що міститься у кормах 2 видів – зерні та соєвих бобах. Вміст поживних речовин у кожному кормі та їх вартість задано таблицею.

Корм	Вміст поживних речовин	Вартість корму у.о./кг
Білок	Клітковина
Зерно			0,4
Соєві боби			0,9

Готова суміш має містити не менше як 20% білка і не більше, як 5% клітковини.

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

адача 8.

Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає дві моделі збірних книжкових полиць А та В. Полиці обох моделей оброблюють на верстатах 1 та 2. Тривалість обробки полиць кожної моделі на першому верстаті 30 і 15 хв відповідно, на другому – 12 і 36 хв. Термін роботи кожного верстата складає відповідно 40 та 36 год. на тиждень. Прибуток фірми від реалізації полиці А складає 50 у.о., полиці В 30 у.о. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці А ніколи не перевершує попиту на полиці В більше, як на 30 одиниць, а попит на полиці моделі В не перевершує 80 одиниць на тиждень.

риклади розв’язування задач.

Тема : "Графічний метод розв’язування ЗЛП"

адача 1.

Знайти мінімальне і максимальне значення функцій z при наявності таких обмежень

1. Будуємо граничні прямі:

I: а)

б)

II: а)

б)

III: а)

б)

IV: а)

б)

V:

VI:

2. Визначаємо багатокутник розв’язків:

3. Будуємо вектор мети

4. Проводимо лінії рівня перпендикулярно до

Визначаємо: , де точка А визначається перетином прямих I і II.

I II:

, де точка D визначається перетином прямих I і IV

I IV:

Відповідь: при плані при плані

адача 2.

Знайти мінімальне і максимальне значення функції мети z при наявності системи обмежень:

Z= -2x₁ + 4x₂ +8 extr;

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

1. Будуємо граничні прямі:

I: -5x₁ + 2x₂ = 7;

a) x₁ = 0; x₂ =3,5; (0; 3,5);

b) x₂ = 0; x₁ = -1,4; (-1,4; 0);

II: x₁ -2x₂ =5;

a) x₁ = 0; x₂ = -2,5; (0;-2,5);

b) x₂ = 0; x₁ = 5; (5; 0);

III: x₁ + x₂ = 2;

a) x₁ = 0; x₂ = 2; (0;2);

b) = 0; x₁ = 2; (2;0);

IV: x₁ + x₂ = 6;

a) x₁ = 0; x₂ = 6; (0; 6);

b) x₂ = 0; x₁ = 6; (6; 0);

V: x₁ = 0;

VI: x₂ = 0;

2. Будуємо багатокутник розв’язків – ABCDEF.

3. Будуємо вектор мети

4. Проводимо лінії рівняння перпендикулярно Мінімуму можуть відповідати точки E і F, а максимуму точка A.

5. Визначаємо координати точок:

E: II VI: ;

Z min =

F: II IV:

Z min =

A: I IV:

Z max =

Відповідь: на планах EF з координатами при плані

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

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

1. 2.

Відповідь: Відповідь:

3. 4.

Відповідь: Відповідь:

5. 6.

Відповідь: Відповідь:

7. 8.

Відповідь: Відповідь:

9. 10.

Відповідь: Відповідь:

Тема : "Розв’язування ЗЛП симплекс-методом"

адача 1.

На виготовлення двох видів продукції виділяється три види ресурсів. Запаси ресурсів: 99, 74 і 101 у.о. відповідно до норми їх витрат: 3 і 2 у.о. – 1 ресурсу; 2 і 2 у.о. – 2 ресурсу; 1 і 2 у.о. – 3 ресурсу відповідно на одиницю продукції кожного виду і прибуток 14 і 12 у.о. від реалізації одиниці продукції кожного виду відповідно. Знайти симплекс-методом такий план виробництва, який забезпечував би найбільший прибуток. Скласти подвійну задачу до вихідної і виписати її оптимальний план з останньої симплекс-таблиці розв‘язку вихідної задачі.

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

Відповідно до умови задачі отримаємо таку математичну модель:

(1)

Канонічний вид задачі (1):

Опорний розв’язок, наприклад, можна отримати при . Тоді , тобто

Основна матриця системи обмежень:

. Ранг матриці А дорівнює тому, що, наприклад, визначник

Так як кількість додатних координат опорного розв’язку дорівнює рангу матриці А, то даний опорний розв’язок є невиродженим. Базис складають вектори Базисна матриця має вигляд:

. Обернена матриця .

Розкладаємо небазисні вектори А₁, А₂ по векторам базису Для скорочення запису зробимо це у вигляді однієї матричної формули:

Запишемо симплекс-таблицю, яка відповідає даному опорному розв’язку:

№	Базис	Сі базис		14					Ci
1				3
				-14	-12

Обчислимо значення функції мети:

Оцінки:

Так як оцінки і від’ємні: 0 і 0, то даний опорний розв’язок не оптимальний. В базис вводимо вектор , бо його оцінка найменша із від’ємних. Із базиса виводимо вектор , бо відношення координат стовпчика до стовпчика : 99/3 = 33; 74/2 = 37; 101/2 = 50,5 – найменше із додатних для вектора . Розрахунковий елемент “3” отримаємо на перетині продовжень стрілок.

Обчислюємо нові елементи симплекс-таблиці, яка відповідає новому опорному розв’язку. Елементи рядка, який містить розрахунковий елемент ділимо на нього. Інші елементи таблиці отримаємо за правилом “хрест-на-хрест”. Наприклад, для нового значення в клітині з числом 74 маємо: і т. д. Нова симплекс-таблиця, яка відповідає новому опорному розв’язку має вид:

№	Базис	Сі базис							Сі
					2/3	1/3
2					2/3	-2/3
					5/3	-2/3
					-8/3	14/3

Так як оцінка від’ємна: 0, то даний опорний розв’язок не оптимальний. В базис вводимо вектор , бо його оцінка 0. Із базиса виводимо вектор , тому що відношення координат стовпчика до стовпчика : 33: 2/3 = 49,5; 8: 2/3 = 12; 35: 5/3 = 21 – найменше із додатних для вектора . Розрахунковий елемент “2/3” отримаємо на перетині продовжень стрілок. Аналогічно попередньому отримаємо нову симплекс-таблицю, яка відповідає новому опорному розв’язку.

№	Базис	Сі базис							Сі
						-1	-1
						-1	3/2
							-5/2

Обчислимо значення функції мети:

Оцінки:

Так як всі оцінки невід’ємні, то даний опорний розв’язок оптимальний:

Z max = 494 при плані .

Подвійна задача до (1):

min,

Із останньої симплекс-таблиці:

тоді

чого й треба було чекати.

Відповідь: при .

адача 2

На виготовлення двох видів продукції виділяється три види ресурсів. Запаси ресурсів: 273, 100 та 380 у.о., відповідно, норми їх витрат: 3 та 2 у.о. – 1 ресурсу; 1 та 1 у.о. – 2 ресурсу; 1 та 2 у.о. – 3 ресурсу відповідно на одиницю продукції кожного виду та прибутку 10 і 8 у.о. від реалізації одиниці продукції кожного виду приведені в таблиці. Знайти симплекс-методом такий план виробництва, який би забезпечував найбільший прибуток. Скласти подвійну задачу до вихідної і виписати її оптимальний план із симплекс-таблиці розв‘язку вихідної задачі.

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

Відповідно до умови задачі отримаємо наступну математичну модель:

z = 10x₁ + 8x₂ max,

(1)

Опорний розв‘язок (2) отримаємо, наприклад, при х_{3 =} х₄ = 0;

Канонічний вид задачі (1):

z = 10x₁ +8x₂ max,

(2)

тоді х₁ = 73; х₂ = 27; х₅ = 253, тобто х* (73; 27; 0; 0; 273).

Основна матриця системи обмежень (2):

має ранг r (A) = 3, бо, наприклад, .

Так як опорний розв‘язок має три додатні координати, то він є невиродженим. Базис опорного розв‘язку складають вектори .

Базисна матриця .

Будуємо обернену матрицю . Визначник

Алгебраїчні доповнення:

Обернена матриця

Перевірка:

Розкладаємо небазисні вектори по векторам базиса Для скорочення запису зробимо це у вигляді однієї матричної формули:

Запишемо симплекс-таблицю, яка відповідає даному опорному розв’язку:

№	Ба - зис	Сі базис							Сі
							-2
						-1
							-4

Знаходимо:

Оцінки:

Усі оцінки невід’ємні ( ). Даний опорний розв’язок оптимальний.

при оптимальному плані Подвійна задача до (1):

Із останньої симплекс-таблиці , то базисні змінні

,тоді:

Відповідь: при

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

Розв’язати ЗЛП симплекс – методом.

1. 2.

Відповідь: Відповідь:

3. 4.

Відповідь: Відповідь:

5. 6.

Відповідь: Відповідь:

Тема: "Транспортна задача. Метод потенціалів"

адача 1

Знайти оптимальний план транспортної задачі за даною таблицею, де - матриця вартості перевезення одиниці вантажу; - запаси, - потреби вантажу (у.о.), де .

.

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

Знаходимо:

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

b а
		ө 20	60
			ө 250

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

Базис складають вектори:

Він невироджений, бо що дорівнює кількості базисних векторів.

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

Система для визначення потенціалів має вигляд:

Задаючи отримаємо розв’язок системи:

Обчислимо оцінки небазисних векторів:

Так як оцінка >0, то даний опорний розв’язок є неоптимальним. Вводимо в базис вектор . Невідомий об’єм переведень за маршрутом позначимо . Складаємо компенсаторний ланцюг. Визначаємо Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

b a
	ө 150		80
	8	20	ө 230
		ө 170

Базисні вектори: Система для визначення потенціалів має вигляд:

Звідси отримаємо:

Оцінки небазисних векторів:

У базис вводимо вектор

Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

b a

Базис складають вектори:

Система для потенціалів має вигляд:

Звідси:

Оцінки небазисних векторів:

Всі оцінки недодатні. Даний опорний розв’язок оптимальний. Оптимальне значення функції мети:

.

Перевіряємо нульову оцінку на оптимальність. В базис вводимо вектор (4,4). Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

b a

тобто план перевезень також оптимальний.

Відповідь: при слідуючих оптимальних планах перевезень: І план - при цьому I споживач не отримає 70 одиниць продукції;

ІІ план – при цьому I споживач не отримає 50 одиниць продукції, а ІІ - 20.

адача 2

Знайти оптимальний план транспортної задачі за даними таблиці, - матриця вартості перевезення одиниці вантажу; - запаси, - потреби вантажу (у.о.), де ; .

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

Знаходимо .

Так як > , то маємо відкриту транспортну задачу (ТЗ). Для перетворення її в закриту ТЗ вводимо фіктивного виробника з об’ємом виробництва – = 890 – 820 = 70 і нульовими елементами матриці вартості. Запишемо цю ТЗ у вигляді таблиці 1:

в a
				ө 170
		ө 200

Опорний план перевезень визначаємо за методом мінімальності вартості. Запишемо його у правому нижньому кутку базисних клітин. Базис складають вектори: (1;3), (1;4), (2;2), (2;4), (3;1), (3;3), (4;3).

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

Система для визначення потенціалів має вигляд:

Задаючи , отримаємо розв’язок системи:

Оцінка векторів:

>0.

Так як >0, то даний опорний план є не оптимальним.

У базис вводимо вектор (1;2). Невідомий об’єм перевезень маршруту (1;2) позначимо Θ.

Складаємо компенсаторний ланцюг. Знаходимо Θ = min (170; 200) = 170. Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:

в a

Базис складають вектори:

(1; 2), (1; 3), (2; 2), (2; 4), (3; 1), (3; 3), (4; 3).

Система для визначення потенціалів має вигляд:

Розв’язок цієї системи має вигляд:

Оцінки небазисних векторів:

Усі оцінки недодатні. Даний опорний розв’язок є оптимальний.

Оптимальне значення функції мети:

Відповідь: оптимальне значення функції мети при оптимальному плані перевезень: При цьому III споживач не отримає 70 одиниць продукції.

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

Розв’язати ТЗ методом потенціалів:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.