Постановка задач лінійного програмування, їх моделі та основні форми

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

Загальну лінійну математичну модель формалізації економічних процесів і явищ (загальну задачу лінійного програмування), можна подати у вигляді:

знайти максимум (мінімум) функції

(3.1)

за умов

(3.2)

(3.3)

Функцію Z називають цільовою функцією або функцією мети. Для економічної системи це є функція ефективності її функціонування та розвитку.

Сформулюємо загальне визначення задачі лінійного програмування таким чином:

Необхідно знайти такі значення керованих змінних хі, щоб цільова функція при цих значеннях набувала екстремального (мінімального чи максимального) значення за виконання певної множини умов. Отже, потрібно знайти значення змінних , які задовольняють умови (3.2) і (3.3), при яких цільова функція (3.1) набуває екстремального (максимального чи мінімального) значення.

Система (3.2)-(3.3) називається системою обмежень або системою умов задачі. Вона описує внутрішні технологічні та економічні процеси функціонування і розвитку виробничо-економічної системи, а також процеси зовнішнього середовища, які впливають на результат діяльності системи. Для економічних систем змінні хімають бути невід’ємними. Формалізований запис задачі (3.1)-(3.3) є загальною економіко-математичною моделлю функціонування умовної економічної системи. Розробляючи окреслену модель, потрібно керуватися такими правилами:

1) модель має адекватно описувати реальні економічні та технологічні процеси;

2) у моделі потрібно враховувати все істотне, суттєве в досліджуваному явищі чи процесі, відкидаючи все другорядне, неістотне;

3) модель має бути зрозумілою для користувача;

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

Будь-який набір змінних що задовольняє умови (3.2) та (3.3), називають допустимим планом або планом. Очевидно, що кожний допустимий план є відповідною стратегією економічної системи, програмою дій. Кожному допустимому плану відповідає значення цільової функції, яке обчислюється за формулою (3.1). Сукупність усіх розв’язків систем обмежень (3.2) та (33), тобто множина всіх допустимих планів, становить область існування планів. План, за якого цільова функція набуває екстремального значення, називається оптимальним. Оптимальний план є розв’язком задачі математичного програмування (3.1)-(3.3).

Відзначимо, що в задачі математичного програмування передбачається одна цільова функція, яка кількісно виражена. В реальних економічних системах на роль критерію оптимальності (ефективності) претендують багато показників. Наприклад, максимум чистого доходу від виготовленої продукції чи максимум рентабельності, мінімум собівартості виготовленої продукції або мінімум витрат дефіцитних ресурсів тощо. Хоча загальна задача математичного програмування передбачає одну цільову функцію, але існують математичні методи побудови компромісних планів, тобто методи багатокритеріальної оптимізації. Розглянемо найпростіші математичні моделі задач лінійного програмування (ЛП):

1) Задача про використання ресурсів (сировини). Для виготовлення двох видів продукції П1 та П2 використовуються три види сировини S1, S2, S3. Запаси сировини, норми витрат сировини на виготовлення одиниці продукції кожного виду та дохід від одиниці продукції кожного виду наведені в таблиці:

 

 

 

Вид сировини Запаси сировини Витрати сировини на виготовлення одиниці продукції
П1 П2
S1
S2
S2
Дохід від одиниці продукції

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

Побудуємо математичну модель задачі. Позначимо:

х1, х2 – загальна кількість продукції П1 та П2;

Z – сумарний дохід, який отримаємо від реалізації всієї продукції П1 та П2.

Запишемо цільову функцію задачі. Дохід від реалізації одиниці продукції П1 становить с1, а всього цієї продукції плануємо випустити х1 одиниць, тому перемноживши с1 на х1, отримаємо весь дохід, який матимемо від реалізації всієї продукції. Аналогічно дохід від реалізації продукції П2 становитиме с2х2. Додамо ці два доданки (с1х12х2) і отримаємо весь дохід від реалізації всієї продукції П1 та П2. Оскільки ми хочемо отримати найбільший дохід, то будемо знаходити максимальне значення цільової функції:

Тепер потрібно записати обмеження задачі. Нам відомо, скільки ресурсів кожного виду затрачається на виготовлення одиниці продукції кожного виду. Так, на виготовлення одиниці продукції П1 ресурсу (сировини) S1 витрачаємо а11, всього продукції П1 плануємо виготовити одиниць. Перемножимо а11 на і отримаємо ту кількість ресурсу S1, яка піде на виготовлення всієї продукції П1. Цього ж ресурсу S1 на виготовлення одиниці продукції П2 затрачаємо а12, а плануємо виготовити х2 одиниць продукції П2, тому, коли перемножимо а12 на х2, будемо мати кількість ресурсу S1, затрачену на виготовлення всієї продукції П2. Якщо додамо а11 х1 та а12х2, то отримаємо сумарні витрати ресурсу S1 на виготовлення всієї продукції П1 та П2. Але запас кожного виду ресурсу обмежений iвикористати більше, ніж ми маємо, не можемо. Запас ресурсу S1 становить . Тому обмеження з використання ресурсів матимуть вигляд:

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

Ми отримали таку задачу лінійного програмування:

(3.4)

(3.5)

Функція (3.4) - це цільова функція або функція мети, (3.5) - система обмежень задачі, причому перші три обмеження (3.5) називають основними обмеженнями, а останні два - природними чи економічними.

2) Узагальнена модель оптимального планування.Розглянемо загальну модель оптимального планування. Припустимо, що планується організувати випуск продукції r видів за допомогою т можливих технологій. Для цього використовується п видів виробничих ресурсів (матеріалів, обладнання, праці, сировини тощо). Введемо позначення: i - індекс ресурсу, ; jіндекс технології, ; l - індекс виду продукції, ; - витрати ресурсу і-го виду на одиницю часу роботи технологічної лінії виду j; - вихід продукції виду l за одиницю часу роботи технологічної лінії виду j; - обсяг запасів ресурсів i-го виду; - коефіцієнт, який відображає частку продукції виду l в загальному обсязі кінцевої продукції; - час роботи технологічної лінії виду j; Z - загальний обсяг кінцевої продукції.

Тоді узагальнена модель оптимального планування матиме вигляд: знайти такий план { }, який забезпечить

при виконанні обмежень:

а) за обсягом ресурсів:

(3.6)

б) за структурою кінцевої продукції

(3.7)

 

3) Задача про складання кормового раціону.

В кормовий раціон для відгодівлі великої рогатої худоби (ВРХ) входять п’ять видів кормів Кh К2, К3, К4 та К5. Для забезпечення заданого приросту ваги тварини повинні споживати поживні речовини Р12 та Р3. Мінімальна кількість поживних речовин, потрібних тваринам, а також вміст кількості одиниць поживних речовин в 1 кг корму та вартість 1 кг корму наведені в таблиці.

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

 

 

 

Поживні речовини Мінімальна кількість поживних речовин Кількість одиниць поживних речовин в 1 кг корму
Р1 К2 К3 К4 К5
Р1
Р2
Р3
Вартість 1 кг корму с1 с2 С3 С4 С5

 

Побудуємо математичну модель задачі. Введемо позначення: хі - кількість корму (кг) Кі в раціоні (і=1, 2, 3, 4, 5); Z - вартість добового раціону.

Оскільки вартість одного кілограма корму становить сі aзагальна кількість корму і-гoвиду, що потрібна для відгодівлі ВРХ становить хі кг (і=1, 2, 3, 4, 5), то перемноживши сі на хі i додавши ці добутки, отримаємо вартість добового раціону відгодівлі ВРХ: Z = c1x1+c2x2+c3x3+c4x4+c5x5. Для побудови обмежень задачі перемножимо - кількість поживних речовин Р1, що містяться в 1кг корму К1на загальну кількість цього корму х1і так по всіх видах кормів, щоб в результаті отримати загальну кількість поживних речовин, отриманих від усіх п’яти кормів, а мінімальна кількість поживних речовин повинна становити відповідно , , ,тому обмеження з першого, другого та третього видів поживних речовин матимуть вигляд 3.9:

Ми отримали математичну модель задачі про кормовий раціон:

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

(3.8)

Обмеження

(3.9)

4) Задача про раціональний розкрій матеріалів.

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

Для побудови математичної моделі задачі введемо позначення. Нехай:

m – кількість різних заготовок;

Bi – план випуску заготовок і-го виду;

n - кількість різних способів (варіантів) розкрою стандартного матеріалу;

– число заготовок і-го виду, одержаних за допомогою j-го способу розкрою;

сj – величина відходів при j-му варіанті розкрою.

Схематично задачу можна представити у вигляді таблиці:

 

 

Варіант (спосіб) розкрою Вихід заготовок з одиниці матеріалу Відходи
1-го виду 2-го виду m-го виду
N cn
План випуску заготовок B1 B2 Bm  

Через невідому xj позначимо кількість одиниць вихідного матеріалу, які потрібно розрізати j-тим способом, а через Z – загальну кількість відходів.

Кількість заготовок i-го виду, одержана за всіма варіантами розкрою становитиме , а нам потрібно цих заготовок в кількості Bi одиниць. Тому в якості обмеження з i-того виду заготовок буде рівність:

=Bi .

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

(3.10)

(3.11)

Існуючі методи розв’язування задач лінійного програмування передбачають певні вимоги до системи основних обмежень (3.2), тому розрізняють дві стандартні форми запису задач лінійного програмування:

І-ша - з обмеженнями-рівняннями;

ІІ-га - з обмеженнями-нерівностями.

Запишемо задачу лінійного програмування в першій стандартній формі:

(3.12)

(3.13)

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

Задача ЛП записана в другій стандартній формі має вигляд:

(3.14)

(3.15)

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

 






Дата добавления: 2016-07-22; просмотров: 2993; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.05 сек.