ЛАБОРАТОРНА РОБОТА №2 ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО РІШЕННЯ ЗАДАЧІ ГРАФІЧНИМ МЕТОДОМ І. Загальні положення Для розв’язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв’язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе. ІІ. Теоретичні відомості Розглянемо задачу. Знайти
(2.1) за умов:
(2.2)
. (2.3) Припустимо, що система (2.2) за умов (2.3) сумісна і багатокутник її розв’язків обмежений. Згідно з геометричною інтерпретацією задачі лінійного програмування кожне і-те обмеження-нерівність у (2.2) визначає півплощину з граничною прямою
(і = 1, 2, …, т). Системою обмежень (2.2) графічно можна зобразити спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовольняють всі обмеження задачі — багатокутник розв’язків. Умова (2.3) невід’ємності змінних означає, що область допустимих розв’язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с1х1 + с2х2 = const. Скористаємося для графічного розв’язання задачі лінійного програмування такими властивостями: якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатокутника розв’язків; якщо ж цільова функція досягає екстремального значення більш як в одній вершині багатокутника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією цих вершин. Отже, розв’язати задачу лінійного програмування графічно означає знайти таку вершину багатокутника розв’язків, у результаті підстановки координат якої в (2.1) лінійна цільова функція набуває найбільшого (найменшого) значення. Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків: 1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.5) знаків нерівностей на знаки рівностей. 2. Визначаємо півплощини, що відповідають кожному обмеженню задачі. 3. Знаходимо багатокутник розв’язків задачі лінійного програмування. 4. Будуємо вектор
, що задає напрям зростання значення цільової функції задачі. 5. Будуємо пряму с1х1 + с2х2 = const, перпендикулярну до вектора
. 6. Рухаючи пряму с1х1 + с2х2 = const в напрямку вектора
(для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального значення. 7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці. ІІІ. Завдання За варіантами побудувати та розв’язати графічно задачу лінійного програмування. Дати економічну інтерпретацію результатам розв’язку. Варіанти 1-5 Для виробництва двох видів продукції А і В підприємство використовує 4 групи обладнання. Використання обладнання для виробництва продукції, а також прибуток від реалізації одиниці продукції А і В наведено у табл. 2.1. На підприємстві обладнання 1 виду є у кількості 18 од., 2 виду – 12+р од., 3 виду – 24 од., 4 виду – 18+р од. Скільки продукції має виробляти підприємство для отримання максимального прибутку? Таблиця 2.1 Використання обладнання за групами для виробництва одиниці продукції (шт.) Прибуток, грн.   1 2 3 4   А 1 0 5 3 4+0,1×р  В 1+р 1 0 2 6+0,1×р   Варіанти 6-10 На фермі кожна корова щоденно має отримувати не менше 9 одиниць зерна С1, не менше 8 сіна, не менше 12 одиниць висівок. Для годування тварин використовуються два види кормів. Кількість одиниць зерна, сіна та висівок у кожному виді кормів та вартість 1 кг кормів наведено у табл. 2.2. Складіть денний раціон необхідно поживності мінімізуючи при цьому витрати на придбання кормів. Таблиця 2 Поживні речовини Кількість поживних речовин у 1 кг   Корм 1 Корм 2  Зерно 3+0,01×р 1  Сіно 1 2+0,01×р  Висівки 1 6  Вартість 1 кг кормів, грн. 0,34+0,01×р 0,26+0,01×р   Варіанти 11-15 Для виготовлення двох виді виробів А і В завод використовує як сировину сталь і кольорові метали, запаси яких обмежені. На виготовлення вказаних двох виробів зайняті токарні і фрезерні верстати. У табл. 2.3 приведені вихідні дані. Визначити план випуску продукції, при якому буде досягнутий максимальний прибуток. Таблиця 2.3 Вид ресурсів Об’єм ресурсів Норми витрат на один виріб    Виріб А Виріб Б  Сталь (кг) 570+р 10 70  Кольорові метали (кг) 420+р 20 50  Токарні верстати (станко-г) 5600-р 300 400  Фрезерні верстати (станко-г) 3400-р 200 100  Прибуток (тис.грн.)  3 8   Варіанти 16-20 Підприємство електронної промисловості виготовляє дві моделі радіоприймачів Soundmax та GRUNDIG. Кожна з моделей виробляється на окремій технологічній лінії. Потужність лінії 1 складає 90 виробів, лінії 2 – 80+р-10 виробів. На радіоприймач Soundmax витрачається 15 однотипних елементів електронних схем, на радіоприймач GRUNDIG – 10 таких самих схем. Максимальний добовий запас електронних схем складає 950+10-р одиниць. Прибуток від реалізації одного радіоприймача Soundmax складає 320+10-р грн., а радіоприймача RUNDIG – 210+10-р грн. Визначити оптимальній добові обсяги виробництва радіоприймачів двох моделей. Варіанти 21-25 Компанія виготовляє набори шахів та шашок. Кожний набір шашок приносить прибуток 16+р-5 грн, а набір шахів – 32+р-10 грн. На виготовлення одного набору шашок витрачається 4 год. роботи на дільниці А і 2 години роботи на дільниці Б. Шаховий набрі виготовляється з витратами часу: на дільниці А – 6+0,1×р год., на дільниці Б – 6 год., і на дільниці В – 1+0,1×р год. Виробнича потужність дільниці А складає 120+р нормо-годин, дільниці Б – 72+р нормо-години, дільниці В – 10+0,1×р нормо-годин. Скільки наборів шашок та шахів треба компанії виготовити для отримання максимального прибутку? Варіанти 26-30 У четвер їдальня готує два види страв – смаженину та котлети. Для приготування використовується м’ясо, крупа, картопля. Норми витрат продуктів для приготування та прибуток від реалізації однієї порції страви наведено у табл. 3. Розрахувати максимальний прибуток їдальні у четвер. Таблиця 3 Вид продукту Запаси продуктів Норми витрат на 1 страву    Смаженина Котлети  М’ясо 5×р 0,4 0,15  Крупа 6×р 0,2 0,3  Картопля 4×р 0,25 0,2  Прибуток від реалізації 1 порції страви, грн./шт. 2×р/5 1,4+р/5