Практична робота № 3.

ТЕМА: Прийняття оптимальних рішень. Симплексний метод розв'язання задач лінійного програмування.

МЕТА: Набути навички розв’язування задач лінійного програмування з використанням симплексного методу.

ТРИВАЛІСТЬ: 6 години.

ЗАБЕЗПЕЧЕННЯ ЗАНЯТТЯ: ПК, пакет Microsoft Office.

Теоретичні відомості

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

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

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

Послідовність дій під час реалізації цього алгоритму:

1. Модель практичної задачі лінійного програмування звести до канонічного вигляду за умови пошуку найбільшого значення цільової функції.

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

3. За наявного опорного плану зобразити базисні змінні та цільову функцію через вільні змінні. Записати симплекс-таблицю.

4. Склавши симплекс-таблицю, дослідити наявний опорний план:

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

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

в) якщо в оціночному рядку є хоча б один від’ємний елемент, а у відповідному стовпці – хоча б один додатний, то можна наявний опорний план поліпшити.

5. Одержаний на наступному кроці новий опорний план треба знову дослідити на оптимальність.

ЗАВДАННЯ ДЛЯ РОБОТИ

Завдання 1. Згідно варіанту побудувати математичну модель економічної задачі. Привести задачу до канонічної форми. Розв'язати задачу симплекс-методом.

Завдання 2. Оформити звіт з практичної роботи.

Варіанти для завдання 1.

№ студента в журналі

Задача

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

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

Виробничі ресурси	Пшениця	Овес	Ячмінь	Загальний об’єм ресурсів
Витрати праці на 1 га, люд-год	5	4	3	25
Добрива на 1 га, кг	2	3	5	35
Вихід продукції з 1га, грн	20000	1400	15000

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

Знайти склад суміші з максимальною її вартістю, якщо 1 кг першого порошку коштує 2 грн, а другого – 1 грн.

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

На виробництво 1 т кожного препарату витрачається відповідно 4 та 6 кг нафтопродукту, запас якого на добу не перевищує 30 кг.

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

Цех випускає вироби двох видів: вали і втулки. Виготовляючи один вал, робітник витрачає 3 годину, а одну втулку – 2 години. Від реалізації вала підприємство одержує прибуток 80 коп., а від реалізації втулки – 60 коп. цех повинен випустити не менше 100 штук валів і не менше 200 штук втулок.

Скільки треба виготовити валів і втулок, щоб цех одержав найбільший прибуток, якщо фонд робочого часу становить 900 людино-годин.

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

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

На виготовлення 1 т декораційних плит першого типу витрачається 6 куб. м деревини, а другого – 7 куб. м. Витрати деревини за добу не повинні перевищувати 42 куб. м. При цьому слід мати на увазі, що різниця між кількостями виробництва першого та другого типів не повинна перевищувати 2 т, а найбільш доцільний режим технології виробництва плит – не більше як 4 т плит за добу.

Знайти оптимальний план виробництва декоративних плит, якщо вартість 1 т плит першого типу – 3 тис. грн, а другого – 1 тис. грн.

Три цехи разом виготовляють не більше 500 т будівельного матеріалу за добу. Фонд часу не перевищує 3200 годин, а витрати праці не повинні перевищувати 8000 чол.-днів. Питомі витрати по кожному цеху на виробництво 1 т матеріалу наведені у таблиці:

Ресурси	Цех
Ресурси	1	2	3
Час, год	3	2	4
Витрати праці, чол.-днів	11	15	20

Вихід валової продукції по цехах дорівнює відповідно 400, 300 та 200 грн за 1 т. За добу другий цех повинен виробляти не більше як 200 т матеріалу.

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

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

Вид продукту	Норми витрат продуктів (кг) на одну партію бутербродів виду			Наявність продуктів (кг)
Вид продукту	Б1	Б2	Б3	Наявність продуктів (кг)
С1	4	3	1	42
С2	2	5	4	56
С3	3	6	2	38
С4	5	7	3	40
Прибуток, (грн)	5	7	8

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

Скласти оптимальний план (мінімум капітальних затрат) забудови мікрорайону міста житловими будинками трьох різних типів. Наявність квартир у кожному з типових будинків відображає таблиця.

Планова кількість мешканців у квартирі	Кількість квартир за типом будинку
Планова кількість мешканців у квартирі	Першим	Другим	Третім
2	50	50	60
3	30	100	50
4	120	60	40
Вартість	804 тис. грн	822 тис. грн	602 тис. грн

Демографічний склад майбутнього населення мікрорайону зумовлює необхідність того, щоб було не менше ніж 750 квартир на 2-х мешканців; 1700 квартир на 3-х; 450 квартир на 4-х.

Цех за добу може випускати не більше 10 шт. виробів першого типу, 7 шт. – другого та 9 шт. – третього типу. Згідно з умовами ритмічності роботи цех повинен за добу випускати не більше 20 виробів. Тривалість виробництва одного виробу першого типу дорівнює 1 год, другого – 0,5 год, третього – 1,5 год. А вартість одного виробу становить відповідно 3, 2 та 4 грн.

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

Вміст кількості поживних речовин типу А та С (у міліграмах) у 1 кг двох типів продуктів наведено в таблиці.

Вітамін	Продукти
Вітамін	1	2
А	350	400
С	150	750

Яку кількість першого та другого типів продуктів необхідно включити до раціону харчування, щоб у ньому було не менш як 600 мг речовини А та 750 мг речовини С за умов мінімальних витрат. Якщо виробництво 10 кг продукту першого типу коштує 0,025 грн, а 10 кг другого – 0,03 грн.

При цьому необхідно врахувати, що загальна кількість продукту в раціоні харчування повинна бути не більше 1 кг.

У процесі виробництва двох рецептів використовується три типи лікарських речовин, витрати яких на 1 г кінцевої продукції наведені у таблиці.

Речовина, г	Рецепт
Речовина, г	1	2
1-го типу	5	1
2-го типу	2	5
3-го типу	1,5	4

У виробництві рецептів повинно використовуватись не менше як 20 г першої, як 10 г другої та не більше як 32 г третьої речовин відповідно. Вартість виробництва 10 г продукції за першим рецептом – 1,8 грн, за другим – 1грн.

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

Фабрика виробляє два види продуктів за умов дотримання таких вимог: загальне виробництво за добу обох продуктів повинно становити планове завдання до 3,5 т; технологією виробництва передбачається обов`язкова різниця між обсягами двох продуктів не більше як 2,5 т; запаси сировини на добу не перевищують 20 т, а нормативи витрат його на виробництво 1 т першого продукту дорівнюють 2 т, другого – 10 т. Знайти оптимальне виробництво двох видів продукції з максимальною вартістю їх реалізації, якщо вартість реалізації 1 т першого продукту – 10 грн, другого – 20 грн.

Майстерня виробляє до 40 шт. скляних виробів за добу. Норми витрат кольорової речовини та час виготовлення першого та другого видів скляних виробів наведені у таблиці.

Ресурси	1	2
Кольорова речовина, г	3	4
Час, хв	50	60
Прибуток, грн	25	20

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

Кондитерська фабрика для виробництва 3-х видів карамелі А1, А2, А3 використовує 3 види сировини С1, С2, С3. Норми витрат сировини кожного виду на виробництво 1 т карамелі даного виду наведені в таблиці.

Вид продукту	Норми витрат сировини на одну тонну карамелі			Загальна кількість сировини (кг)
С1	0,8	0,5	0,6	800
С2	0,4	0,4	0,3	600
С3	–	0,1	0,1	120
Прибуток, (грн)	108	112	126

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

З нафтопродукту виробляють два типи кінцевого продукту широкого вжитку. Необхідно знайти обсяги виробництва кінцевих продуктів з максимальною вартістю їх реалізації та виконанням умов (зведено до однієї доби):

загальні витрати нафтопродукту не повинні перевищувати 3 т;

сумарне виробництво обох видів продуктів не може бути менше як 1 т;

виробництво кожних 2-х т другого виду кінцевого продукту потребує не менше як 1 т першого кінцевого продукту;

щоб виготовити 1 т першого виду кінцевого продукту, необхідно не більше 1 т нафтопродукту, для другого – не більше 3 т нафтопродукту;

вартість реалізації 1 т першого та другого типів кінцевих продуктів дорівнює відповідно 1 та 2 грн.

Для виготовлення хімічних речовин А, В, С використовують два лікарські препарати. Кількість речовин кожного препарату, яка міститься в одній таблетці, така:

у першому препараті міститься 0,2; 1,1 та 0,7 г відповідних речовин;

у другому препараті – відповідно 0,4 та 0,1 г речовин А та С.

Вартість однієї упаковки з 10 таблеток лікарського препарату першого типу – 10 коп., другого – 18 коп. Для виробництва лікарських препаратів є 40 г речовини В, 10 г речовини С та 35 г. речовини А.

Знайти план випуску лікарських препаратів з максимальною вартістю.

Для збереження здоров`я та працездатності бригада 10 чоловік повинна споживати за добу не менше як 40 г речовини В1, не менше як 100 г – В2, не більше як 90 г – В3 та не менше як 50 г – В4. Харчі можна готувати за двома рецептами: 1 кг харчів за першим рецептом містить 5 г речовини В1, 6 г – В2, 3 г – В3 та 1 г – В4; а 1 кг харчів за другим рецептом містить 1 г речовини В1, 3 г – В2, 1 г – В3 та 2 г – В4.

За першим рецептом 1 кг харчів коштує 30 коп., за другим – 10 коп. Потрібно організувати харчування бригади таким чином, щоб вартість його була мінімальною, а вся бригада одержувала б необхідну норму речовини за добу.

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

Вид сировини	Норми витрат сировини на 1 виріб			Кількість сировини
Вид сировини	Виріб А	Виріб В	Виріб С	Кількість сировини
Сировина І	18	15	12	360
Сировина ІІ	6	4	8	192
Сировина ІІІ	5	3	3	180
Ціна 1 виробу	9	10	16	-

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

Підприємство може виготовляти чотири види продукції П-1, П-2, П-3, П-4. Збут будь-якого її обсягу забезпечений. Норми витрати ресурсів і прибуток від одиниці кожного виду продукції подані в таблиці

Обсяг ресурсів:	Норми витрат ресурсів на од. продукції
Обсяг ресурсів:	П-1	П-2	П-3	П-4
3000	3	4	4	5
5000	2	0	3	4
8000	10	12	10	8
Ціна од. продукції	46	12	10	8

Скласти план виробництва, при якому прибуток від реалізації продукції буде максимальним.

Підприємство виготовляє продукцію видів А, В і С, для чого використовує три види ресурсів І, II, III. Норми витрат усіх ресурсів на одиницю кожної продукції та обсяги ресурсів на підприємстві наведено в табл.1.

Вид ресурсу

Норма витрат на одиницю продукції за видами

Запас ресурсу

І

III

180

210

244

Відома ціна одиниці продукції кожного виду: А - 10 ум.од., В -14 ум.од. і С - 12 ум. од. Визначити план виробництва продукції, що забезпечує підприємству найбільший дохід.

Деяка установа надає послуги виду 1 та виду 2. Кожна послуга виду 1 дає прибуток 60 грн., а на її надання витрачається 1 одиниця ресурсу 1, 0.5 одиниць ресурсу 2 і 1 одна одиниця ресурсу 3. Кожна послуга виду 2 дає прибуток 160 грн., а на її надання витрачається 2 одиниці ресурсу 1, 0.4 одиниці ресурсу 2 і 4 одиниці ресурсу 3. Ресурси установи обмежені: щотижня вона може отримувати від своїх постачальників 130 одиниць ресурсу 1, 50 одиниць ресурсу 2 і 220 одиниць ресурсу 3.

Треба визначити, в якій кількості спланувати надання послуг виду 1 і виду 2, щоб прибуток був максимальним.

Для виготовлення виробів A, B, C підприємство використовує три види сировини. Норми використання сировини на виробництво одного виробу кожного виду, ціна одного виробу A, B, C, а також загальні запаси сировини кожного виду, приведені в таблиці. Потрібно знайти оптимальний план виробництва при якому загальна вартість всієї виробленої продукції буде максимальною.

Види сировини	Норми витрат сировини			Запаси сировини
Види сировини	А	В	С	Запаси сировини
І	18	15	12	360
ІІ	8	4	6	192
ІІІ	5	3	3	180
Ціна 1 виробу	9	10	16

Потрібно засіяти не більше 5 га двома сільськогосподарськими культурами, причому першою культурою повинна бути засіяна площа не більше як 3 га, до того ж площа її мусить бути удвічі більшою ніж площа засіву другої культури. Прибуток від продажу культур становить 4 тис. грн за 1 га першої культури і 5 тис. грн – другої культури.

Знайти оптимальний варіант засіву площі двома культурами.

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

Верстати	Сумарний час роботи верстатів	Час обробки деталі			Прибуток
Верстати	Сумарний час роботи верстатів	А1	А2	А3	Прибуток
1	16	1	2	2	4
2	28	2	3	2	3
3	30	3	3	2	2

Приклад розв'язання задачі ЛП симплекс-методом.

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

f(x)=12х₁+15х₂ → max

6х₁+6х₂<36,

4х₁+2х₂<20,

4х₁+8х₂<40,

х₁>0; х₂>0.

Рішення

Приведемо задачу до канонічної форми:

f = 12х₁+15х₂+0·x₃+0·x₄+0·x₅ → mах;

6х₁+6х₂+x₃=36,

4х₁+2х₂+x₄=20,

4х₁+8х₂+x₅=40,

x_j ≥0 (j=1,5)

Виділяємо базисні змінні. Кількість базисних змінних повинна дорівнювати кількості обмежень, тобто трьом. У кожному обмеженні даної задачі можна виділити одну змінну, котра присутня тільки в одному обмеженні з коефіцієнтом +1. Отже, змінні х₃, х₄, х₅ є базисними, а змінні х₁, х₂ – небазисними.

Визначимо вихідний базисний план і значення цільової функції: х₁ = 0, х₂ = 0, х₃ = 36, х₄ = 20, х₅ = 40, f = 0.

Вхідні дані задачі, а також обчислені значення цільової функції (f = 0·36 + 0·20 + 0·40 = 0) і значення відносних оцінок (Δ1 = 0·6 + 0·4 + 0·4 – 12 = –12; Δ2 = 0·6 + 0·2 + 0·8 – 15= –15) перенесемо у вихідну симплексну таблицю (табл. 1.).

Таблиця 1. – Вхідна симплекс-таблиця

Базис	С	В	12	15
Базис	С	В	х₁	х₂
х₃	0	36	6	6
х₄	0	20	4	2
х₅	0	40	4	8
Δ		0	-12	-15

Перевіряємо отриманий план на оптимальність за умовою оптимальності (Δj ≥ 0). Оскільки для даного плану існують оцінки Δ1<0 і Δ2<0, план не оптимальний. Необхідний перехід до іншого базисного плану.

У першу чергу серед небазисних змінних виберемо змінну, котра буде вводитися в базис:

У базис буде вводитися змінна х₂, тому що цій змінній відповідає максимальна за модулем відносна оцінка |Δ₂| = 15. Стовпець, що відповідає змінній х₂, є головним (розв’язувальним).

Далі виберемо змінну, котра буде виводитися з базису:

З базису буде виводитися змінна х₅, тому що цій змінній відповідає мінімальне відношення, рівне 5. Рядок, що відповідає змінній х₅, є головним. На перетинанні головного рядка й головного стовпця знаходиться головний елемент а₅₂=8.

Будуємо нову симплексну таблицю (табл. 2.), у якій змінні х₅ і х₂ міняються місцями, разом зі своїми коефіцієнтами в цільовій функції. Інші змінні переписуються без змін зі своїми коефіцієнтами у цільовій функції.

Таблиця 2. – Симплекс-таблиця 1 ітерації

Базис	С	В	12	0
Базис	С	В	х₁	х₅
х₃	0	6	3	-3/4
х₄	0	10	3	-1/4
х₂	15	5	1/2	1/8
Δ		75	-9/2	15/8

Перераховуємо елементи табл. 1. і результати заносимо у відповідні клітини табл. 2. Елементи головного рядка табл. 1. перераховуються шляхом діленням кожного елемента цього рядка на головний , головний елемент – шляхом ділення одиниці на головний елемент , елементи головного стовпця – шляхом діленням кожного елемента цього стовпця на головний зі знаком мінус .

Всі інші елементи табл. 2. визначаються за правилом прямокутника.

Наприклад, для клітки x₃х₁ новий елемент дорівнює .

Перевіряємо правильність розрахунку значень цільової функції f і оцінок Δ1, Δ5 за формулами:

f = 0·6 + 0·10 + 15·5 = 75,

Δ1 = 0·3 + 0·3 + 15·1/2 – 12 = –9/2,

Δ5 = 0·(–3/4) + 0·(–1/4) + 15·1/8 – 0 = 15/8.

Отриманий у табл. 2. план не оптимальний, тому що існує Δ1 = –9/2. У число базисних уводиться змінна х₁, а з базису виключається змінна х₃.

Перераховуємо елементи табл. 2. і результати заносимо в табл. 3. Після перевірки правильності розрахунку f і оцінок Δ3, Δ5 робимо висновок про те, що отриманий у табл. 3. план оптимальний, тому що оцінки Δ3, Δ5 > 0.

Таблиця 3. – Симплекс-таблиця 2 ітерації

Базис	С	В	12	0
Базис	С	В	х₃	х₅
х₁	12	2	1/3	-1/4
х₄	0	4	-1	1/2
х₂	15	4	-1/6	1/4
Δ		84	3/2	3/4

Для одержання максимального доходу в розмірі 84 гр.од. підприємству необхідно випускати з наявних ресурсів 2 од. продукції виду П1 і 4 од. продукції П2.

Відповідь: x₁*=2, х₂*=4, f_max=84.

Контрольні питання

1. Суть задачі лінійного програмування.

2. Поняття цільової функції та її обмежень.

3. Що означає поняття «оптимальний план»?

4. Які Ви можете назвати форми задачі лінійного програмування?

5. У чому різниця між канонічною й довільною формою задачі лінійного програмування?

6. Що є областю допустимих значень у задачі ЛП?

7. Перерахуйте етапи побудови обмежень задачі ЛП.