Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Зауваження

План

Графічний метод вирішення ЗЛП

1. Геометрична інтерпретація задачі лінійного програмування.

2. Алгоритм розв’язання задачі лінійного програмування графічним методом.

3. Розв’язання задачі лінійного програмування графічним методом.

 

 

1. Геометрична інтерпретація задачі лінійного програмування

При n=2 можна привести геометричну інтерпретацію на двовимірній площині. Можливі наступні варіанти множини допустимих рішень.

Вектор-градієнт вказує напрямок найшвидшого зростання функції і складається з приватних похідних:

Для F(x)=c1x1+c2x2+…+cjxj+…+cnxn gradF(x)=(c1,c2,…,cj,…,cn). За умови двовимірного простору його легко виразити у вигляді:

 

2. Алгоритм використання графічного методу:

1. Будуємо множину допустимих рішень;

2. Будуємо вектор-градієнт;

3. Проводимо довільну лінію рівняння цілі F=const (простіше F=0) перпендикулярно до вектора-градієнта;

4. При розв’язання задачі на максимум переміщуємо лінію рівняння F=const у напрямку вектора-градієнта, до тих пір, доки вона займе крайнє положення по відношенню до множини допустимих рішень. У випадку задачі на мінімум – перемуруємо лінію у оберненому напрямку.

3. Розв’язання задачі лінійного програмування графічним методом.

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

Задача використання сировини.

Для виготовлення двох видів продукції Р1 і Р2 використовують три види сировини: S1, S2, S3. Запаси сировини, кількість одиниць сировини, що використовується для виготовлення одиниці продукції, а також розмір прибутку, що буде отриманий у результаті реалізації одиниці продукції, наведені у таблиці 2.1.

Таблиця 2.1.

Види сировини Запаси сировини Кількість одиниць сировини, необхідних для виготовлення одиниці продукції
Р1 Р2
S1      
S2      
S3      
Прибуток від одиниці продукції, грн.    

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

Рішення.

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

1 + 5х2 20

1 + 5х2 40

1 + 6х2 30

Яка показує, що кількість сировини, яка використовується на виготовлення продукції, не може перевищувати наявні запаси. Якщо продукція Р1 не виготовляється, то х1=0; у протилежному випадку x2=0. Те ж саме і для продукції Р2. Таким чином, на невідомі х1 і х2 повинна бути накладена вимога невід’ємності: х1>0, х2>0.

Кінцеву ціль задачі, що вирішується – отримання максимального прибутку від реалізації продукції – виразимо як функцію двох змінних х1 и х2. Реалізація х1 одиниць продукції Р1 и х2 одиниць продукції Р2 дає Відповідно 50х1 і 40х2 грн. прибутку, загальний прибуток Z = 50х1 + 40х2 (грн.)

Умовами не зазначена неділимість одиниці продукції, тому х1 і х2 (план випуску продукції) можуть бути й дробовими числами.

Потрібно знайти такі х1 і х2, за яких функція Z досягає максимум, тобто знайти максимальне значення лінійної функції Z = 50х1 + 40х2 за обмежень:

1 + 5х2 ≤20

1 + 5х2 ≤40

1 + 6х2 ≤30

х1≥0, х2≥0.

Побудуємо багатокутник рішень (мал. 2.1).

Для цього у системі координат х1Ох2 на площині зобразимо граничні прямі:

1 + 5х2 = 20 (L1)

1 + 5х2 = 40 (L2)

1 + 6х2 = 30 (L3)

х1 = 0, х2 = 0.

Узявши яку-небудь точку, наприклад, початок координат, установимо, яку півплощину визначає відповідна нерівність (ці півплощини на мал. 2.1 показані штрихами). Багатокутником рішень даної задачі є обмежений п’ятикутник ОАВСD.

Для побудови прямої 50х1 + 40х2 = 0 будуємо радіус-вектор N = (50;40) = 10(5;4) и через точку O проводимо пряму, перпендикулярну йому. Побудовану пряму Z=0 переміщуємо паралельно самій собі у напрямку вектора N. З мал. 2.1 виходить, що опорною по відношенню до багатокутника рішень ця пряма стає у точці B, де функція Z приймає максимальне значення. Точка B лежить на перетині прямих L3 і L2. Для визначення її координат розв’яжемо систему рівнянь

8x1 + 5х2 = 40

1 + 6х2 = 30

Оптимальний план задачі: х1=90/23=3,9; х2=40/23= 1,7. Підставляючи значення х1 і х2 до лінійної функції, отримуємо Zmax = 50*3,9 + 40*1,7 = 263

Таким чином, для того щоб отримати максимальний прибуток у розмірі 263 грн., необхідно запланувати виробництво 3,9 од. продукції Р1 і 1,7 од. продукції Р2.

 

Оцінки цільової функції бажано розраховувати (перевіряти) двома способома (одним розраховувати, другим перевіряти).

Таким чином отримуємо нову симплексну таблицю, що відповідає новому плану (перехід до етапу ІІ).

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

 

<== предыдущая лекция | следующая лекция ==>
Чужеродностью | Тема: Основы международного права. Международное гуманитарное
Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 317; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.