Навігація
Головна
Форми запису задами лінійного програмування та її економічна...Постановка задачі лінійного програмуванняОснови лінійного програмуванняОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯГрафічний метод рішення задач лінійного програмуванняПрикріплення споживачів до постачальників методами лінійного...Модель транспортної задачі лінійного програмуванняФорми економічного програмуванняМетод динамічного програмування та оцінки для задач оптимального...Загальний метод проекції градієнта для загальної задачі квадратичного...
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Форми запису задачі лінійного програмування та її економічна інтерпретація

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

У задачі лінійного програмування (ЗЛП) потрібно знайти екстремум (максимум чи мінімум) лінійної цільової функції:

(2.9)

при обмеженнях (умовах):

(2.10)

(2.11)

де - задані постійні величини. Так записується загальна задача лінійного програмування в розгорнутій формі. Знак {≤, =, ≥} означає, що в конкретній ЗЛП можливе обмеження типу рівності або нерівності (в ту чи іншу сторону).

Систему обмежень (2.10) називають функціональними обмеженнями ЗЛП, а обмеження (2.11) - прямими.

Вектор, компоненти якого задовольняють системі обмежень (2.10) і (2.11), називається допустимим рішенням або планом ЗЛП, тобто обмеження (2.10), (2.11) визначають область допустимих рішень або планів задачі лінійного програмування (область визначення ЗЛП).

План (допустиме рішення), який доставляє максимум або мінімум цільової функції (2.9), називається оптимальним планом (оптимальним рішенням) ЗЛП.

Канонічної формою запису задачі лінійного програмування (КЗЛП) називають завдання виду (запис з використанням знаків підсумовування):

(2.12)

(2.13)

(2.14)

Векторна форма запису КЗЛП має вигляд

де СХ - скалярний добуток векторів,; і В - вектор-стовпці:

Матрична форма запису КЗЛП:

data-override-format="true" data-page-url = "http://stud.com.ua">

Тут - вектор-рядок; - матриця розмірності т × п, стовпцями якої є вектор-стовпці; X і В - вектор-стовпці:

Іноді використовується стандартна форма запису ЗЛП:

Має місце твердження, що будь-яку ЗЛП можна привести до канонічного виду.

Приведення ЗЛП до канонічного виду здійснюється введенням в ліву частину відповідного обмеження виду (2.10) k-й додаткової (допоміжної) змінної зі знаком "-" у разі обмеження типу "≥" і знаком "+" у разі обмеження типу "≤".

Якщо на деяку змінну х r не накладає умову невід'ємності, то роблять заміну змінних. У реформованій завданню всі змінні невід'ємні.

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

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

Приклад 2.1 (задача а сумішах). Стандартом передбачено, що октанове число автомобільного бензину А-76 має бути не нижче 76, а вміст сірки в ньому - не більше 0,3%. Для виготовлення такого бензину на заводі використовується суміш з чотирьох компонентів. Дані про ресурси змішуються компонентів, їх собівартості і їх октанове число, а також про зміст сірки наведені в таблиці [1]:[1]

data-override-format="true" data-page-url = "http://stud.com.ua">

Характеристика

Компонент автомобільного

бензину

№ 1

№2

№3

№4

Октанове число

68

72

80

90

Вміст сірки%

0,35

0,35

0,3

0,2

Ресурси, т

700

600

500

300

Собівартість, ден. од. / т

40

45

60

90

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

Рішення. Для вирішення цього завдання сформулюємо її економіко-математичну модель, тобто сформулюємо задачу математично. Введемо необхідні позначення: нехай (j = 1, 2, 3, 4) - кількість в суміші компонента з номером у. Таким чином, формально план виробництва суміші являє собою вектор

З урахуванням введених позначень математична модель розглянутої задачі за критерієм "мінімум сумарних витрат на виготовлення суміші" має вигляд

(1)

(2)

(3)

Функціональне обмеження (3) відображає необхідність отримання заданої кількості суміші (1000 т), (1) і (2) - обмеження за октановим числом і змістом сірки в суміші, решта - обмеження по запасах відповідних ресурсів (компонентів). Прямі обмеження очевидні, але принципово важливі для вибору методу рішення. Отримана математична задача (модель) - задача лінійного програмування. Вона може бути вирішена симплекс-методом, який розглянутий в даній главі нижче (для автоматизації розрахунків можна використовувати надбудову Пошук рішення MS Excel [2]). В результаті рішення ЗЛП отримаємо оптимальне рішення:[2]

де;;;.

Підставляючи знайдене рішення в цільову функцію (ЦФ), маємо

Таким чином, пропонуються наступні рекомендації з виробництва суміші:

- Для виробництва суміші компонент № 1 береться в кількості 571,429 т;

- Компонент № 3 береться в кількості 142,857 т;

- Компонент № 4 береться в кількості 285,714 т.

При такому змішанні очікуються мінімальні витрати на виробництво суміші, рівні 57143 (ден. Од.).

Приклад 2.2 (задача про оптимальне використання обмежених ресурсів).

На ділянку споруджуваної дороги [3] необхідно вивезти 20000 м3 кам'яних матеріалів. У районі будівництва є три кар'єра із запасами 8000 м3, 9000 м3 і 10 000 м3. Для навантаження матеріалів використовуються екскаватори, що мають продуктивність 250 м3 у зміну в кар'єрах 1, 2 і 500 м3 у зміну в кар'єрі 3.

Ці кар'єри забезпечують кам'яними матеріалами також ряд інших об'єктів, що будуються. На навантаження матеріалів для розглянутого ділянки виділений для екскаваторів загальний ліміт 60 машино-змін з правом використання його на розсуд будівельників.

Транспортні витрати на перевезення матеріалів характеризуються такими показниками: на перевезення 1000 м3 матеріалів з кар'єру 1 потрібно 100 автомобілі-змін, з кар'єру 2 - 1350 автомобілі-змін, з кар'єру 3 - 1700 автомобілі-змін.

Потрібно знайти оптимальний план перевезень, що забезпечує мінімальні транспортні витрати.

Рішення. Сформулюємо економіко-математичну модель задачі. Приймемо за одиницю виміру кількості матеріалів 10000 м3. Позначимо через - обсяг видобутку матеріалів в кар'єрі 1, - в кар'єрі 2, - в кар'єрі 3. Таким чином, формально план перевезень являє собою вектор.

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

(1)

(2)

(3)

(4)

(5)

Умова (1) відображає потребу в матеріалах, (2) - обмеження але наявності ресурсу "фонд робочого часу екскаваторів" (ми не можемо використовувати більше того, що у нас в наявності). Умови (3) - (5) відображають той факт, що видобуток матеріалів йде в умовах обмеженості запасів матеріалів у відповідних кар'єрах. Отримана завдання - завдання лінійного програмування; вирішивши її симплекс-методом (див. нижче), знайдемо оптимальний план (рішення):

Таким чином, з кар'єру 1 слід вивезти 8000 м3 кам'яних матеріалів, з кар'єру 2 - 2000 м3, з кар'єру 3- 10000 м3. Це управлінське рішення буде пов'язано з мінімальними транспортними витратами:

  • [1] Мельник Μ. М. Економіко-математичні методи і моделі в плануванні та управлінні МТС: підручник. М .: Вища школа, 1990.
  • [2] Гармаш А. Н., Орлова І. В. Математичні методи в управлінні: навчань, посібник. М .: Вузівський підручник, 2012.
  • [3] Золотар І. А. Економіко-математичні методи в дорожньому будівництві. М .: Транспорт, 1974.
 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >

Cхожі теми

Форми запису задами лінійного програмування та її економічна інтерпретація
Постановка задачі лінійного програмування
Основи лінійного програмування
ОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Графічний метод рішення задач лінійного програмування
Прикріплення споживачів до постачальників методами лінійного програмування
Модель транспортної задачі лінійного програмування
Форми економічного програмування
Метод динамічного програмування та оцінки для задач оптимального керування
Загальний метод проекції градієнта для загальної задачі квадратичного програмування на основі теореми Куна - Таккера
 
Дисципліни
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук