Тема 2. Симплексний метод розв'язку задачі лінійного програмування.

Ідея методу, область визначення. Алгоритм методу. Побудова опорного плану. Ознаки оптимальності опорного плану. Особливі випадки застосування симплекс-методу. Інтерпретація симплекс-таблиці – аналізу моделі на стійкість.

Тема 3. М-метод (метод великих штрафів)

Ідея методу, область визначення. Алгоритм методу. Ознаки оптимальності. Практичне застосування.

Приклад

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

 

РЕСУРСИ	ТЕХНОЛОГІЧНІ ЗАСОБИ	ОБСЯГ РЕСУРСІВ
№		Т1	Т2	Т3
1	Робоча сила, людино-год.
	Попит, т
	Електроенергія, квт/год
	Продуктивність технологічних засобів, грн.

Необхідно визначити інтенсивність використання технологічних засобів.

 

Рішення:

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

Цільова функція:

Z = 500 x₁ + 400 x₂ + 300 x₃ ® max,

 

Обмеження:

(х_j ³ 0; j = 1,3)

 

Зведемо систему обмежень до канонічного вигляду:

 

15х₁ + 20х₂ + 100х₃ + х₄ = 1500

х₁ + 2х₂ + 3х₃ + х₅ = 200

10х₁ + 20х₂ + 10х₃ + х₆ = 200

 

Z = 500х₁ + 400х₂ +300х₃ + 0х₄ + 0х₅ + 0х₆ ® max

 

Опорний план:

х₄ = 1500

х₅ = 200

х₆ = 200

Z = 0

 

Ресурси є, але виробництво не ведеться. Тому прибуток дорівнює нулю.

Виходячи з опорною плану побудуємо першу симплексну таблицю:

 

№	Базисні змінні	Сі	Вільні члкни	Х1	Х2	Х3	Х4	Х5	Х6	Симплексні відношення
	х4		1500							100
	х5
3	х6
	Z			-500	-400	-300

 

Друга симплексна таблиця:

 

№ п/п	Базисні змінні	Сі	Вільні члени	Х1	Х2	Х3	Х4	Х5	Х6
	Х1				1,33	6,67	0,067
	Х5				0,67	-3,67	-0,067
	Х6				6,67	-56,67	-0,67
	Z				266,67	3033,33	33,33

 

 

Так як в Z – рядку усі елементи невід’ємні, то в другій таблиці отримано оптимальний розв’язок.

Технологічні засоби Т₂ і Т₃ використовувати недоцільно. Найбільший прибуток 50000 грн. дасть використання 100 одиниць технологічних засобів Т₁

Попит залишиться недовикористаним у кількості 100 т.

Електроенергія залишиться недовикористаною у кількості 1000 квт / год.

 

Аналіз останньої симплексної таблиці.

 

Якщо до оптимального п лану ввести одну одиницю технологічного засобу Т₂ , то доцільно зменшити використання технологічного засобу Т₁ на 1,33 одиниці. Попит зменшиться на 0,67 т, а використання електроенергії зменшиться на 6,67 квт / год. Прибуток збільшиться на 266,67 грн.

Якщо до оптимального плану ввести одиницю технологічного засобу Т₃, то доцільно зменшити використання технологічного засобу Т₁ на 6,67 одиниць.

При цьому попит збільшиться на 3,67 т, а використання електроенергії збільшиться на 56,67 квт / год. Прибуток при цьому зросте на 3033,33 грн.

Якщо ресурси робочої сили збільшити на 1 людино-год., то доцільно збільшити використання технологічного засобу Т₁ на 0,067 одиниць. При цьому попит збільшиться на 0,067 т, а використання електроенергії збільшиться на 0,67 квт / год. Прибуток зросте на 33,33 грн.

 

 

Практичні завдання

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

 

1. Для пошиття спідниці і сукань швейний цех має 96м тканини. На пошиття однієї сукні витрачають 3м тканини і 1,8 год роботи устаткування, а на пошиття однієї спідниці – 2м тканини і 0,6 год роботи устаткування. Час роботи устаткування обмежений 45 год на тиждень. Прибуток від продажу однієї сукні становить 18 грн, а однієї спідниці – 10 грн. Визначити щотижневий план виробництва, який забезпечує найбільший прибуток від реалізації торгових виробів, якщо суконь потрібно виготовити щонайбільше 20, а спідниць – щонайбільше 30.

 

2. Відомо, що відгодівля худоби економічно вигідна, якщо кожна тварина отримує на день щонайменше 6 одиниць споживчої речовини А, 12 одиниць речовини В і 4 одиниці речовини С. Для відгодівлі худоби використовують два види кормів. Споживчу цінність 1 кг кожного виду корму наведено в таблиці.

 

Вид корму	Споживча цінність 1 кг споживчої речовини
А	В	С
І
ІІ

 

Вартість 1 кг корму І становить 50 коп., корму ІІ – 60 коп. Скільки необхідно використати кожного виду корму, щоб витрати були найменшими?

 

3. Підприємство виробляє два види продукції, для чого використовується три види ресурсів. Для виготовлення одиниці продукції першого виду необхідно витратити 3 одиниці ресурсу А, 2 одиниці ресурсу В і 1 одиницю ресурсу С, а для виготовлення одиниці продукції другого виду – 2 одиниці ресурсу А, 3 одиниці ресурсу В і 1 одиниця ресурсу С. Запаси ресурсів А, В і С становлять відповідно 101, 99 і 37 одиниць. визначити, скільки одиниць продукції кожного виду потрібно виробити, щоб отримати максимальний прибуток, якщо кожна одиниця продукції першого виду має прибуток 27 грн, другого виду – 24 грн.

 

4. Для відгодівлі худоби використовують два види кормів. у кожному кілограмі корму І міститься 5 одиниць споживчої речовини А і 2,5 одиниці споживчої речовини В, а у кожному кілограмі корму ІІ – по 3 одиниці споживчих речовин А і В. Встановлено, що відгодовувати тварин вигідно лише тоді, коли їх денний раціон становитиме щонайменше 30 одиниць споживчої речовини А і 22,5 одиниці споживчої речовини В. Відомо, що вартість (споживча цінність 1 кг) кожного виду корму – 1 грн. Визначити, скільки корму кожного виду треба використовувати щоденно, щоб витрати були щонайменшими за зазначених умов відгодовування?

 

5. Для збереження здоров’я і працездатності людини повинна споживати щодня таку норму поживних речовин: - А щонайменше 4 мг, В і D – по 6 мг, С – 9 мг. У щоденному раціоні є два види продуктів. Вміст у 1 кг кожного виду продукту поживних речовин такий: А – відповідно 2 і 1 мг, В – 0 і 3 мг, С – 1 і 3 мг, D – 3 і 2 мг. Необхідно організувати щоденне харчування так, щоб його вартість була найменшою, а людина одержувала за добу зазначену норму поживних речовин.

 

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

Група виробничого устаткування	Необхідна кількість устаткування для випуску одиниці продукції	Кількість устаткування у групі
І	ІІ
А В С Д
Прибуток від реалізації

 

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

 

Виріб	Час обробки виробу на верстаті, год
І	ІІ	ІІІ
А В	0,5 0,25	0,4 0,3	0,2 0,4

 

Час роботи верстатів І, ІІ і ІІІ - відповідно до 40, 36 і 36 год на тиждень. Прибуток від реалізації одного виробу А і В – відповідно 5 і 3 грн. Визначити тижневі норми виробництва виробів А і В, при яких прибуток буде максимальний.

 

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

 

Тип виробничого устаткування	Витрати часу на обробку одного виробу продукції, год	Фонд робочого часу устаткування, год
Фрезерне Токарне Шліфувальне
Прибуток від реалізації одиниці продукції, грн

 

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