Основні поняття математичного програмування
1. Огляд теми
1.1 Класифікація задач математичного програмування
1. За характером взаємозв’язку між змінними: Лінійні та Нелінійні.
2. За типом змінних: Неперервні (значення кожної змінної можуть приймати всі значення деякого інтервалу) та Дискретні (цілочислові) (усі або хоча б одна змінна приймають окремі – цілочислові – значення).
3. За врахуванням фактора часу: Статичні (незалежність елементів моделі від часу) та Динамічні
4. За наявністю інформації про змінні: Задачі в умовах повної визначеності (детерміновані); Задачі в умовах неповної визначеності Та Задачі в умовах невизначеності.
5. За числом критеріїв оцінки альтернатив: Прості (однокритеріальні задачі) та Складні (багатокритеріальні задачі).
1.2 Форми запису задач лінійного програмування
Розрізняють три форми запису задач лінійного програмування: загальну, основну (канонічну) і стандартну (симетричну).
Загальна форма запису задачі лінійного програмування наведена в
п. 1.1 (формули (1.4) – (1.7)). (див. Лекція 1). Іншими словами, загальна форма запису задачі лінійного програмування передбачає виконання таких умов:
1) цільова функція спрямована на максимум або на мінімум;
2) система обмежень складається з нерівностей або рівнянь або їх сукупності;
3) на невідомі накладена умова невід’ємності.
Стандартна (симетрична) задача лінійного програмування складається із знаходження максимального значення функції (1.5) при виконанні умов (1.9) і (1.11) (див. Лекція 1). Іншими словами, передбачається виконання таких умов:
1) цільова функція спрямована на максимум;
2) система обмежень складається з нерівностей виду “≤”;
3) на невідомі накладена умова невід’ємності.
Канонічна (основна) задача лінійного програмування складається з визначення максимального значення функції (1.5) при виконанні умов (1.10) і (1.11) (див. Лекція 1).. Або, іншими словами, необхідно виконання умов:
1) цільова функція спрямована на максимум;
2) система обмежень складається з рівнянь;
3) на невідомі накладена умова невід’ємності.
Щоб перейти від однієї форми запису задачі лінійного програмування до іншої, потрібно в загальному випадку уміти:
1) зводити задачу мінімізації до задачі максимізації;
2) переходити від обмежень-нерівностей до обмежень рівнянь і навпаки;
3) заміняти змінні, для яких не виконується умова невід’ємності.
В Першому випадку при переході від знаходження мінімуму функції до знаходження максимуму цієї ж функції (і навпаки) слід цю функцію помножити на 
,оскільки 
.
В Другому випадку при переході від нерівності до рівняння в ліву частину обмеження вводиться додатна величина, яка називається Додаткова змінна. Додаткова змінна має знак “+”, якщо нерівність виду “£”. Додаткова змінна має знак “-”, якщо нерівність виду “³”.
В Третьому випадку змінну 
замінюють різницею двох невід’ємних змінних 
і 
: 
.
1.3 Економічний зміст основних і додаткових замінних задачі планування виробництва
Основні змінні задачі планування виробництва, як показано у прикладах 1.1 і 1.2 (див. Лекція 1)., кількісно описують План випуску продукції по видах.
В першому обмеженні прикладу 1.2 
ліва частина показує витрати корму першого виду на вирощування всіх норок і всіх нутрій, а права частина даної нерівності – запаси корму першого виду. Введемо додаткову змінну 
. Так як ліва частина менша за праву, додаткова змінна вводиться із знаком “+”. Отримуємо 
. Виразимо :
,
Тобто запаси корму першого виду мінус витрати корму першого виду. Очевидно, що – залишки корму першого виду.
Узагальнюючи висновки наведеного прикладу, можна сказати, що в задачі планування виробництва економічний зміст Додаткової змінної, яка введена в нерівність Із знаком “+”, – Залишки сировини відповідного виду.
Припустимо, що фермер уклав угоду на продаж 20 норок. Тоді до системи обмежень додасться нерівність 
. При переході до основної форми запису нерівність перетвориться у рівняння 
. Виразимо змінну 
:
.
– кількість норок, яку планується виростити, 20 – мінімальна кількість норок, яку необхідно виростити. Отже, показує, на скільки більше за оптимальним планом слід виростити норок, ніж мінімально встановлена їх кількість.
Узагальнюючи зроблений висновок, можна сказати, що в задачі про планування виробництва Додаткова змінна, яка введена Із знаком “-“, показує, На скільки більше оптимальна кількість виробництва продукції певного виду, ніж мінімально встановлена її кількість.
1.4 Приклад.Скласти економіко-математичну модель задачі розкрою матеріалу (задача про відходи).
Для виготовлення брусу довжиною 
І 
М у співвідношенні 
на розкрій поступають 
колод довжиною 
м. Визначити план розпилу, який забезпечить максимальне число комплектів, якщо 
.
Вказівка. Перш за все необхідно визначити всі можливі способи розпилу колод, вказавши відповідне число брусу, яке можна одержати з однієї колоди (див. табл. 1). Наприклад,. Згідно з цими даними отримуємо такі способи розпилу:
Таблиця 1
|
Спосіб розпилу |
Можливе чИсло брусків довжиною |
||
|
0,8 м |
2 м |
1,5 м |
|
|
1 |
5 |
– |
– |
|
2 |
3 |
– |
1 |
|
3 |
2 |
1 |
– |
|
4 |
1 |
– |
2 |
|
5 |
– |
2 |
– |
|
6 |
– |
1 |
1 |
За змінні 
обирають кількість колод, розпилених І-м способом. В даному випадку 
. Змінна 
– число комплектів брусків.
Враховуючи, що всі колоди повинні бути розпилені, а кількість брусків кожного розміру повинна задовольняти умову комплектності, економіко-математична модель задачі набуває вигляду:
Рекомендована література
Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. – М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. – М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высш. Шк.», 1986, – 319 с . Ляшенко И. Н. Линейное и нелинейное программирование. – і К.: Вищашк., 1975,-371 с.
7. Математическое моделирование экономических процессов в сельском хозяйстве/ Гатаулин А. М. и др.; Под ред. А. М.Гатаулина. – М.: Агропромиздат, 1990. – 432с.:ил.
8. Эддоус М., Стэнфилд Р. Методы принятия решений/ Пер. с англ. под ред. член-корр. РАН И. И.Елисеевой. – М.: Аудит, ЮНИТИ, 1997. – 590с.
Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. – Киев: Высшая школа. Головное изд-во, 1979. – 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV – Санкт-Петербург, 1997. – 384с., ил. Ляшенко И. Н. Лінійне та нелінійне програмування. – К.: Вища шк., 1975. Степанюк В. В. Методи математичного програмування. – К.: Вища шк., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. – М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.:Колос, 1978. Кузнецов Ю. Н. Математические модели в с/х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.
Ви прочитали: "Основні поняття математичного програмування"Читати далі