Вступ
Історія предмета включає в себе, з одного боку, історіюматематичних джерел та методів, а з другого — історіюзастосування цих методів у прикладних галузях, насамперед в економіці.
Як найпершу економічну модель, що містила деякі найпростішіідеї лінійного програмування, слід назвати „Економічні таблиці"лейб-медика короля Людовика XV Ф. Кене, складенуним близько 1758 р., в якій було запропоновано кількісну модельнаціональної економіки. У цій праці він поділив економіку Франції на тричастини:
1) виробничий сектор, включаючи великих власників землі;
2) сектор торгівлі, що складався із купців та ремісників;
3) сектор нерухомості, що включав майно дворянства, церквита королів.
Математичні моделі використовувались з ілюстративними ідослідницькими цілями також А. Смітом (класична макроекономічна модель), Д.Рікардо (модель міжнародної торгівлі).
З відомих нам математичних робіт основному методу лінійногопрограмування — симплексному — передували праці Ш. Фур'є (1823 p.), якийрозглядав задачу визначення найменшого максимального відхилення в розв'язкахсистем рівнянь. Ним ця задача була зведена до знаходження найнижчоїточки многогранникаn-вимірного простору, яку визначали послідовним переборомусіх вершин многогранника. Ідея Фур'є і лягла в основу симплексного методу.
У XIX сторіччівеликий внесок у моделювання ринкової економіки внесла математична школа (Л.Вальрас, О. Курно, В. Парето, Ф. Еджворт). В 1874 Р- Л. Вальрас запропонувавскладну математичну модель економіки, що містила технологічнікоефіцієнти.
У XX сторіччіматематичні методи моделювання застосовувались дуже широко, з їх використаннямзв'язані практично всі роботи, визначені Нобелевською премією в економіці (Д.Хіте, Р.Солоу, В. Леонтьев, П. Самуєльсон). Розвиток мікроекономіки, макроекономіки,прикладних дисциплін зв'язано з усе більш високим рівнем їх формалізації.Основу для цього заклав прогрес в області прикладної математики — теорії ігор,математичного програмування, математичної статистики.
У1926 р. в СРСР був опублікований баланс народногогосподарства, що містив усі основні ідеї і риси моделі міжгалузевого балансу,яка є методом математичного аналізу міжгалузевих економічних зв'язків.
Ґрунтуючись на цих ідеях, американський економіст В. Леонтьев створивкількісну модель американської економіки, яка давала можливість простежитивплив урядової політики і тенденції у сфері закупок на цілий ряд промисловихгалузей, тісно взаємозв'язаних між собою.
Вперше задачу оптимізації плану перевезень з метоюмінімізації їх сумарного кілометражу було поставлено в роботі радянськогоекономіста А. Н. Толстого в 1930 р.
Угорський математик Б. Егерварі в 1931р. сформулював задачуоптимального вибору і дав метод її розв'язування, що дістав назву угорськогометоду.
Проте, справжнім початком математичного (лінійногопрограмування) в його сучасному вигляді слід вважати праці радянськогоматематика академіка Л. В. Канторовича, який у 1939 р. зайнявшисьплануванням роботи агрегатів фанерної фабрики, розв'язав декілька задач: пронайкраще завантаження обладнання, про розкрій матеріалів з найменшими втратами,про вантажі по декільком видам транспорту та ін. Л.В. Канторович сформулювавновий клас умовно-екстремальних задач і запропонував універсальний метод їхрозв'язування, що поклало початок новому напряму прикладної математики — лінійномупрограмуванню.
Значний внесок у формування і розвиток математичногопрограмування внесли зарубіжні вчені Р. Акоф, Р. Белман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Сааті, Р. Черчмен, А.Кофман. Так, наприклад, американський математик P. Белманзаклав основи динамічного програмування (І954)-
У 1960-80-і роки економіко-математичний напрямок на Українібув пов'язаний в основному зі спробами формально описати „систему оптимальногофункціонування соціалістичної економіки". Будувалися багаторівневі системимоделей народногосподарського планування, оп-тямізаційні моделі галузей іпідприємств. Зараз важливою задачею є моделювання процесів перехідного періоду.
1. Приклади задач математичногопрограмування
Багато різних за реальним змістом задач лінійногопрограмування мають подібну математичну структуру, певні особливості якої можнауспішно використати при побудові алгоритмів розв'язування цих задач. Виходячи зцієї подібності, всі задачі лінійного програмування часто поділяють на двівеликі групи. Типовими задачами першої групи є задачі на добір оптимальноїсуміші сплавів та на складання оптимального раціону. За ними закріпилась назвазадачі про раціон.
Типовими задачами другої групи є транспортна задача і задачапро оптимальний добір. Ці задачі називаються задачамирозподільчого типу.
Задача на складання суміші сплаву. Нехай потрібновиплавити новий сплав, що містить а% свинцю, b% цинку і d% олова.Припустимо, що в розпорядженні підприємства є и різних сплаві, кожний з якихмістить />свинцю,/>цинку і />олова і може бутивикористаний для виробництва нового сплаву. Ціна одного кілограма />-го сплаву дорівнює />. Завдання полягаєв тому, щоб визначити, яку кількість кожного сплаву потрібно затратити накожний кілограм нового сплаву, щоб він був найдешевшим. Позначивши шуканівеличини xj, одержимо цільову функцію
/> (1)
яку слід мінімізувати при такій системі обмежень
/> (2)
/> (3)
/>
Задача про оптимальний добір в племінній справі. Великезначення в підвищенні ефективності тваринництва має племінна робота. Одним знайважливіших завдань при цьому є правильний добір сам-ця-плідника до самокматочного поголів'я. В умовах штучного запліднення, яке тепер є основним, заодним самцем закріплюється ціла група маток, кількістю від кількох сотень докількох тисяч. Нехай, у певному господарстві, чи зоні, що включає групугосподарств, усе маточне поголів'я розподілене на N груп згідно з деякоюсукупністю ознак, які визначають продуктивність нащадків, наприклад, належністьдо однієї породи та лінії, умови утримання, годівлі тощо. Позначимо кількістькожної групи />, так що /> — загальне число маток.Припустимо, що кожний з наявних у господарстві т самців-плідниківвипробуваний на певній кількості маток кожної />-їгрупи, в результаті чого добуто відповідні статистичні (вибіркові) середніпродуктивної якості нащадків кожного і-го самця по кожній />-й групі маток. Позначимоці величини />, а максимальну здатність />-го самця-плідника />в рік — через />, що означає максимальноможливе число маток, запліднюваних />-м самцем. Тепер задачу лінійногопрограмування можемо сформулювати так. Знайти цілочислову матрицю
/>
таку, щоб лінійна форма
/> (4)
набувала максимального значення при системі умов:
/> (5)
/> (6)
/>' (7)
де />— означаєкількість маток />-ї групи, щозапліднюються і-м самцем.
Наведемо приклади задач нелінійного програмування.
Задача оптимального вибору факторів виробничої функції. Нехай, z— кількість деякого продукту, навиробництво якого витрачаються певні ресурси в кількостях />. При цьому, якщовартість одиниці />-го ресурсу cj, тозагальні витрати виробництва
/> (8)
Нехай, відома також залежність величини z, вираженої внатуральних чи вартісних одиницях, від кількостей використаних в процесівиробництва ресурсів xj, які виступають якфактори виробництва,
/> (9)
Вид та параметри функції (9) залежать відтехнології виробництва і, як правило, встановлюються статистичними методами.Найбільше застосування дістала виробнича функція Коббо-Дугласа
/> (9a)
Зрозуміло, що
/> (10)
В даному випадку можна сформулювати дві взаємозв'язанихзадачі математичного програмування протилежного змісту.
Перша задача: при заданому об'ємі загальних витрат навиробництво продукції w=const, тобто призаданих асигнуваннях максимізувати випуск продукції z→max.
Друга задача: при заданому об'ємі виробництва даноїпродукції z=const мінімізувати величину загальнихвитрат на її виробництво w→min.
Цільовою функцією першої задачі є функція (9), аобмеженнями — співвідношення (8), (10); для другої задачі цільовоюфункцією являється функція (їло), а обмеженнями — співвідношення (9), (10).
Задача оптимізації розмірів закуповуваних партій товарів. Припустимо,що деякій організації на плановий період необхідні певні матеріали в об'ємах />. Ці матеріали витрачаютьсярівномірно в часі і зберігаються на одному складі, місткістю /> об'ємних одиниць, причому />, так що одночаснорозмістити на складі всі матеріали неможливо і необхідно провести кільказакупок цих матеріалів партіями по /> об'ємниходиниць кожного />-го товару />.
Вартість зберігання на складі об'ємної одиниці />-го матеріалу дорівнює />, так що зберігання/> одиниць товару протягомчасу його використання коштуватиме />.Припустимо, що вартість кожної закупки />-гоматеріалу не залежить від розміру партії xj і дорівнює sj. Необхідновизначити оптимальні розміри закуповуваних партій так, щоб мінімізуватизагальні витрати на зберігання і закупку матеріалів. Отже, цільова функція задачі
/> (11)
при умові, що сумарний об'єм закуповуваних партій неперевищить місткості складу
/> (12)
Очевидно,
/> (13)
Задача про режим роботи енергосистеми. В якості прикладазадачі опуклого програмування розглянемо простішу задачу про оптимальне веденнярежиму роботи енергосистеми.
Розглядається ізольована енергосистема, яка складається зтеплоелектростанцій, зв'язаних лініями передач з вузлом, в якому зосереджененавантаження. Ставиться задача розподілу активних потужностей міжелектростанціями у заданий момент часу. Розподіл здійснюється за критерієммінімізації сумарних паливних витрат на генерацію активної потужності.
Позначимо через, xj активнупотужність, яка генерується на j-й електростанції.Потужності xj лежать умежах, які визначаються технічними умовами:/>.Крім того, повинно виконуватись умова балансу потужностей, тобто загальнапотужність, що генерується, повинна відповідати потужності Р, якаспоживається, з урахуванням загальних втрат/>у лініях передач:
/>
Втрати палива на генерацію потужності xj являютьсобою функцію /> , якаопукла на відрізку/> Таким чином,задача приймає вигляд:
/> (14)
при умовах
/> (15)
/> (16)
Побудована модель є типовою задачею опуклого програмування злінійними обмеженнями. Розв'язок цієї задачі дає вельми грубе наближення додійсно оптимального режиму роботи енергосистеми. У реальній ситуації не можнавважати все навантаження зосередженим в одному вузлі, а слід розглядати п вузлів.Крім того, втрати в системі, природно не є сталими, а залежать від параметрівліній передач та величин потужностей, що передаються.
В якості наступного наближення можна розглядати задачу, вякійπ є білінійною функцією />,де параметри управління xy означають кількість активної потужності,яка передається з j-йелектростанції у i-й вузол.
Очевидно, що в цієї нової моделі умови будуть міститинелінійності (π (xy.) в рівняннібалансу).
Задача про розміщення. Ця простіша задачапро розміщення є прикладом багатоекстремальної задачі.
Є т можливих пунктів виробництва, причому відома длякожного i-го пункту залежність вартості виробництва fi від об'ємувиробництва xi (передбачається, що у вартістьвиробництва/>включені капітальні витрати).Дані/>пунктівспоживання із заданим об'ємом споживання bj у кожномупункті. Нарешті, задана матриця транспортних витрат (/>) (/> — вартість перевезенняодиниці продукції з i-го пункту виробництва в j-й пункт споживання). Необхідно знайти такіоб'єми виробництва /> , які мінімізуютьсумарні витрати; інакше кажучи, шукається
/> (17)
при умовах
/> (18)
/> (19)
Оскільки собівартість одиниці продукції звичайно спадає призбільшені об'єму виробництва, то функції fi (yi), якправило, монотонно зростають і опуклі вгору. Множина значень xij, щозадовольняє обмеження задачі, утворює опуклий многокутник, вершини якого єточками локальних мінімумів функції l(xij) (рис. 1).
/>
Рис. 1. Звідси й назва подібних задач — багатоекстремальні.
Доцільно зазначити, що за своїм реальним змістом більшістьзадач математичного програмування є задачами або мінімізації витрат ресурсів навиробництво заданих кількостей продукції, або ж максимізації випуску продукції(прибутку) при заданих обмежених кількостях ресурсів. 2. Дві стандартні форми задач лінійного програмування
Загальна форма задачі лінійного програмування (3.1) — (3.6) непридатна для побудови досить простих і ефективних методів розв'язування її,причиною чого е неоднорідність системи умов (3.2) -(3.6). Тому,як правило, задачу зводять до стандартної форми.
В залежності від методів, які застосовуються, розрізняютьдві стандартні форми:
основна задача лінійного програмування зобмеженнями-рівностями або перша стандартна форма;
основна задача лінійного програмування зобмеженнями-нерівностями або друга стандартна форма.
Формулювання основної задачі лінійного програмування у першійстандартній формі полягає в наступному: серед усіх невід'ємних розв'язківсистеми основних обмежень-рівнянь знайти такий, при якому цільова функціянабуває найбільшого або найменшого значення:
/> (21)
/> (22)
/> (23)
Або у короткому запису
/> (21а)
/> (22а)
Основна задача лінійного програмування може бути такожзаписана у скалярно-векторній, матричній і векторній формах, якщо скористатисьпозначеннями:
/>
Тут /> — вектор-стовпецьзмінних, />— вектор-стовпець вільнихчленів, А — матриця системи основних обмежень, /> - вектор-стовпець матриці А; /> — вектор-рядоккоефіцієнтів цільової функції, /> -вектор-рядок матриці А.
Скалярно-векторна форма:
/> (216)
/> (22б)
/> (23б)
Матрична форма:
/> (21в)
/> (22в)
/> (23в)
Векторна форма:
/> (21г)
/> (22г)
/> (23г)
Лема 1. Будь-яку задачу лінійного програмування у загальнійформі можна звести до першої стандартної форми.
Доведення. Покажемо, що будь-яку нерівність, введеннямдодаткової невідомої можна звести до рівності. Дійсно, нехай деяке обмеженнямає вигляд
/>
Перепишемо його таким чином:
/>
Введемо позначення />
За побудовою /> єневід'ємною величиною. Крім того останнє
співвідношення є рівняння відносно невідомих/>:
/>
Отже ми прийшли до рівності еквівалентній вихідноїнерівності.
За таким самим алгоритмом можна звести до рівності йнерівність з протилежним знаком, але завжди треба нові невідомі додавати доменших частин нерівностей, бо у протилежному випадку вони не будутьневід'ємними величинами.
Наступний крок полягає в зведені до однорідної системиобмежень на знак. Умови недодатності (3.6) легко перетворюються в умовиневід'ємності за допомогою заміни відповідних змінних /> .
Складніше позбутися змінних, на знак яких обмежень ненакладено. Цього можна досягти двома способами.
1-й спосіб. Якщо число таких змінних (3.7) менше, ніжчисло обмежень основної групи і вектори-стовпці коефіцієнтів при них разом здеякими іншими утворюють базисний мінор, то, розв'язавши добуту нами системуобмежень-рівностей відносно згаданих змінних, виключаємо їх як з системи умов,так і з цільової функції, залишаючи без уваги формули, що виражають їх черезневід'ємні змінні, підставляючи які у залишені вирази, дістаємо й оптимальнізначення змінних (3.7).
Хоч цей спосіб придатний для більшості практичних випадків,однак буває, що умови необхідні для його використання, не виконуються.
Тоді цим способом можна виключити лише частину вільнихзмінних, а до тих, що залишилися у задачі, застосувати 2-й спосіб.
2-й спосіб. Кожну змінну, на знак якої не накладенообмежень, подають у вигляді різниці двох невід'ємних змінних
/> (24)
Визначивши оптимальні значення /> та />, можемознайти за (24) і оптимальне значення відповідних />
Приклад 1. Звести до першої стандартної форми такузадачу лінійного програмування:
/>
Розв'язання. Введенням однієї додаткової змінної /> та заміною /> зводимо задачу до вигляду
/>
Хоч тут кількість змінних без обмеження на знак і менша відкількості основних обмежень, їх не можна вивести з задачі, оскількивектори-стовпці їхніх коефіцієнтів пропорційні і не можуть разом входити добазисного мінору. Тому виведемо одну з них, а другу замінимо різницею двохневід'ємних змінних.
Запишемо задачу в таблицю (в нульовий рядок записанерівняння, що відповідає цільової функції:/>№ рядка
/>
/>
/>
/>
/>
/> -6 3 4 -5 1 2 -6 -2
/> 12 2 3 1 -2 1 6 3 1 -1 -4 2 1 8
Вибравши />= 1ключовим елементом, переходимо до нової таблиці.№ рядка
/>
/>
/>
/>
/>
/> 4 -27 -6 60 1 2 -6 _2 1 12 2 1 7 -6 3 -3 11 1 -16
Виписуючи окремо 1-й рядок (виразивши з нього, />) /> і замінивши />, дістаємо першустандартну форму задачі
/>
де/>
Основна задача лінійного програмування у другій стандартнійформі полягає в тому, що серед всіх невід'ємних розв'язків системи основнихобмежень-нерівностей треба знайти такий, при якому цільова функція буде матиоптимальне значення:
/> (25)
/> (26)
/>
/> (27)
Або у короткому запису
/> (25а)
/> (26а)
Скалярно-векторна форма:
/> (25б)
/> (26б)
/> (27б)
Матрична форма:
/> (25в)
/> (26в)
/> (27в)
Векторна форма:
/> (25г)
/> (26г)
/> (27г)
Лема 2. Перша стандартна форма основної задачі лінійногопрограмування завжди може бути зведена до другої стандартної форми.
Доведення. Припустимо, що невідомі /> є вільними;
/> - базисними; рангматриці системи обмежень (22) дорівнює/>
Розв'яжемо систему рівнянь (22) відносно базиснихневідомих і нехай розв'язок має вигляд
/> (28)
Всі невідомі невід'ємні, тому
/>
Враховуючи це, поставимо у відповідність отриманомурозв'язку (28) еквівалентну систему нерівностей:
/>
Введемо позначення/>іпомноживши всі нерівності на -1 отримуємо систему обмежень:
/>
Очевидно, що остання система обмежень збігається з (26) ірівносильна системі обмежень (3-9) У тому розумінні, що будь-якому розв'язку /> системи нерівностей відповідаєпевний розв'язок /> системи рівнянь (22) Длязавершення доведення леми підставимо у цільову функцію (21) замість базисних невідомих/> їхні вирази (28). Якщо згрупуватиподібні члени, то цільова функція набуде вигляду (25). Приклад 2. Звести додругої стандартної форми задачу
/>
/>
Розв'язання. Виписуємо матрицю системи обмежень
/>
і шукаємо ранг матриці. Базисним буде мінор
/>
Отже, ранг />. Базисніневідомі: />; вільні невідомі: />
Розв'язуємо систему відносно базисних невідомих:
/>
Так як/>, то
/>
Запишемо цільову функцію z черезвільні невідомі
/>
Отже, задача, рівносильна вихідній, має вигляд:
/>
Із лем 1, 2 випливає така теорема.
Теорема 1. Основна задача лінійного програмування упершій стандартній формі і основна задача лінійного програмування у другій стандартнійформі еквівалентні між собою 3. Економічна модель задачі
Фірма спеціалізується на виготовленні та реалізаціїелектроплит і морозильних камер. Припустимо, що збут продукції необмежений,проте обсяги ресурсів (праці та основних матеріалів) обмежені. Завдання полягаєу визначенні такого плану виробництва продукції на місяць, за якого виручкабула б найбільшою.
Норми використання ресурсів та їх загальний запас, а такожціни одиниці кожного виду продукції наведені в табл. 1.
Таблиця 1 Інформація, необхідна для складаннявиробничої програмиВид продукції Норми витрат на одиницю продукції Ціна одиниці продукції, ум. од.
робочого часу,
люд.-год.
листового заліза, м2
скла, м2 Морозильна камера 9,2 3 — 300 Електрична плита 4 6 2 200 Загальний запас ресурсу на місяць 520 240 40 —
Побудуємо економіко-математичну модель даної задачі.
Позначимо через/>кількістьвироблених морозильних камер, а через, />— електроплит. Виразимо математично умови, що обмежують використанняресурсів.
Виходячи з нормативів використання кожного з ресурсів наодиницю продукції, що наведені в табл. 1, запишемо сумарнівитрати робочого часу:
/>.
За умовою задачі ця величина
не може перевищувати загальний запас даного ресурсу, тобто520 люд.-год. Ця вимога описується такою нерівністю:
/>
Аналогічно запишемо умови щодо використання листового залізата скла:
/>
Необхідно серед множини всіх можливих значень/>та/> знайти такі, за яких сума виручкимаксимальна, тобто: max/>
Отже, умови задачі, описані в прикладі 1.1, можна податитакою економіко-математичною моделлю:
/> 5
за умов:
/>
Остання умова фіксує неможливість набуття змінними від'ємнихзначень, тому що кількість виробленої продукції не може бути від'ємною. Розв'язавшизадачу відповідним методом математичного програмування, дістаємо такийрозв'язок: для максимальної виручки від реалізації продукції необхідновиготовляти морозильних камер — 50 штук, електроплит — 15 (/>=50,/>=15).
Перевіримо виконання умов задачі:
9,2-50 + 4·15 = 520;
3-50 + 6·15 = 240;
2·15 = 30
Всі умови задачі виконуються, до того ж оптимальний план даєзмогу повністю використати два види ресурсів з мінімальним надлишком третього.
Виручка становитиме: F = 300-50 +200-15 = 18000 ум. од.
Отриманий оптимальний план у порівнянні з першим варіантомвиробничої програми уможливлює збільшення виручки на
18000-16 800 = 1200 ум. од., тобто на/>100% = 7,1% 4.Математична модель задачі
Математичнамодель стандартної задачі – це її спрощений образ, поданий у вигляді сукупностіматематичних співвідношень (нерівностей). Загальна задача лінійногопрограмування (ЛП) подається у вигляді:
знайти максимум (мінімум) функції
/> (29)
або/>
за умов
/> (30)
/> (31)
Отже, потрібно знайти значення змінних/>, які задовольняють умови (30)і (31), тоді як цільова функція набуває екстремального (максимального чимінімального) значення.
Задачу (29)—(2.3) легко звести до канонічної форми, тобто дотакого вигляду, коли в системі обмежень (30) всі />(і =1,2,… n) невід'ємні,а всі обмеження є рівностями.
Якщо якесь/>від'ємне,то, помноживши />-те обмеження на(—1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-теобмеження має вигляд нерівності ,/>/> , тоостанню завжди можна звести до рівності, увівши допоміжну змінну
/>
Аналогічно обмеження виду /> зводимодо рівності, віднімаючи від лівої частини допоміжну змінну /> , тобто І/>
Приклад 2.1. Записати в канонічній формі такузадачу ЛП:
/>
за умов
/>
Розв'язування. Помножимо другу нерівність на (-1) і введемовідповідно допоміжні змінні/>і/>для другого та третьогообмеження:
/>
Неважко переконатися, що допоміжні змінні, у цьому разі/> і />, є невід'ємними, причомуїх уведення не змінює цільової функції.
Отже, будь-яку задачу ЛП можна записати в такій канонічнійформі:
знайти максимум функції/> (32)
за умов
/> (33)
/> (34)
Задачу (32)—(34) можна розв'язувати на мінімум, якщо цільовуфункцію помножити на (-1), тобто
/> 5.Геометрична інтерпретація стандартної задачі
Геометрична інтерпретація аналітичних задач дає можливістьнаочно представити їх структуру, що сприяє засвоєнню їхніх основнихвластивостей та відкриває шляхи виявлення і дослідження інших, більш складнихвластивостей цих задач. У найпростіших випадках геометричне подання дає змогузнайти розв'язок задачі, однак навіть у тривимірному просторі геометричнерозв'язування ускладнюється і створює ряд труднощів у побудові відповіднихгеометричних фігур, а в просторах вимірності, більшої за три, такерозв'язування і зовсім неможливе.
Можливі різноманітні форми і способи геометричногопредставлення задач лінійного програмування. Доцільність вибору кожного способузумовлюється метою, якої хочуть досягти даною геометричною інтерпретацією таособливостями структури самої задачі, в тому числі й формою її представлення.
Для геометричної інтерпретації візьмемо основну задачулінійного програмування у другій стандартній формі. Для наочності розглянемонайпростіший випадок, коли в системі обмежень (26) і цільовій функції (25) єлише дві змінних/>,/>
Розглянемо розв'язування нерівностей.
Лема 3. Множина розв'язків нерівності з двома змінними
/>
є однією з двох півплощин, на які вся площина ділитьсяпрямою />, включаючи й цюпряму, а інша півплощина з тією ж прямою є множиною розв'язків нерівності
/>
Доведення. Гранична пряма /> перпендикулярнадо вектора нормалі ./> (рис 3.1). Векторнормалі (його ще називають напрямним вектором ) є градієнтом лінійноїфункції /> і показує напрям зростанняїї значень /> — одиничні векторивздовж осей/>і/>відповідно; таким чином, />. Справді, нехай /> ,/>. Візьмемо на прямій, якавизначається вектором /> точку />, причому нехай />, тобто точка /> лежить далі від початкукоординат, ніж точка/>. Очевидно також,що />. У точці />числове значення /> лінійної функції /> дорівнює /> . Аналогічно вточці /> значення />. Ураховуючи, що />, дістанемо />
/>
Рис. 1.
Аналогічно можна пересвідчитись, що напрям зменшення значеньлінійної функції /> збігається з напрямнимвектором />
Прямі лінії на площині/>,які паралельні прямій, що визначається рівнянням/>називаютьлініямирівнів лінійної функції />. Користуючисьпоняттям напрямного вектора /> , можемо визначитирозміщення півплощин/>і /> на координатній площині/>. Півплощина /> розміщена по тойбік прямої/>, куди показує напрямнийвектор -/>. Аналогічно вектор /> показує, де розміщенапівплощина />відносно прямої />побудуємо напрямний векторN=(3,-2). Напрямний вектор міститься у шуканій півплощині, яка виділенаштриховими лініями (рис 3.2).
/>
Рис. 3.2
Якщо врахувати, що множина точок, що задовольняє рівняння
/> 29.)
при п = 3, є півплощина, а при п > 3 — гіперплощинав n-вимірному просторі, то лему 3 можна поширити на випадоктрьох і більше змінних.
Теорема 2. Множиною всіх розв'язків лінійної нерівності з пзмінними
/>
є одним з півпросторів, на які весь простір розділяєтьсяплощиною або гіперплощиною (29), включаючи й саму площину (гіперплощину).
Розглянемо множину розв'язків систем нерівностей.
Теорема 3. Множиною розв'язків сумісної системи т лінійнихнерівностей з двома змінними
/>
є опуклим многокутником.
Доведення. Кожна з нерівностей у відповідності з лемою3 визначає одну з півплощин, які є опуклими множинами точок. Множиноюрозв'язків сумісної системи лінійних нерівностей є множина точок, які належатьпівплощинам-розв'язкам усіх нерівностей, тобто належать їх перетину. Згіднотеореми 2 про перетин опуклих множин ця множина є опуклою і містить скінченечисло кутових точок, тобто є опуклим многокутником.
Теорема 4. Множина розв'язків сумісної системи т лінійнихнерівностей з п змінними є опуклим многогранником в n-вимірномупросторі.
Теорема 5. Множиною всіх допустимих розв'язків сумісноїсистеми т лінійних рівнянь з п змінними (/>) є опуклиммногогранником в n-вимірному просторі.
Теорема 6. Оптимальне значення задачі лінійногопрограмування досягається у вершині многогранника розв'язків системиобмежень.
Результати цього підрозділу дають змогу так інтерпретуватизадачі лінійного програмування:
У многограннику (многокутнику у випадку двох змінних)розв'язків системи обмежень задачі лінійного програмування знайти таку вершину,де цільова функція набуває оптимального (найбільшого або найменшого) значення.
Нехай фермер прийняв рішення вирощувати озиму пшеницю іцукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га.Техніко-економічні показники вирощування цих культур маємо у табл. 2:
Таблиця 2 Показники вирощування сільськогосподарськихкультурПоказник (із розрахунку на 1 га) Озима пшениця Цукрові буряки Наявний ресурс Затрати праці, людино-днів 5 25 270 Затрати праці механізаторів, людино-днів 2 8 80 Урожайність, тонн 3,5 40 — Прибуток, тис. грн. 0,7 1 —
Критерієм оптимальності є максимізація прибутку.
Запишемо економіко-математичну модель структури виробництва озимоїпшениці та цукрових буряків, ввівши такі позначення:
x1 — шукана площа посіву озимої пшениці, га;
x2— шуканаплоща посіву цукрових буряків, га.
Задача лінійного програмування має такий вигляд:
/> (38)
за умов:
/> (39)
/> (40)
/> (41)
/> (42)
/> (43)
Геометричну інтерпретацію задачі зображено на рис. 2.2.
/>
Рис. 2.2. Область допустимих розв'язків задачі
Область допустимих розв'язків цієї задачі дістаємо так.Кожне обмеження, наприклад /> задає півплощину з граничною прямою />. Будуємо її івизначаємо півплощину, яка описується нерівністю />.Зцією метою в нерівність /> підставляємокоординати характерної точки, скажімо,/>і/>. Переконуємося, що цяточка належить півплощині />. Цей фактна рис. 2.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємопівплощини, які відповідають нерівностям (39)—(43). У результаті перетину цихпівплощин утворюється область допустимих розв'язків задачі (на рис. 2.2 —чотирикутник ABCD). Цільова функція Z = 0,7x1+х2являєсобою сім'ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема,якщо Z=0, то маємо Z = 0,7x1+х2=0. Ця прямапроходить через початок системи координат. Коли Z= 3,5, томаємо пряму 0,7x1+х2=3,5. 6. Розв’язання стандартної задачісимплекс-методу
Графічний метод для визначення оптимального плану задачілінійного програмування доцільно застосовувати лише для задач із двомазмінними. За більшої кількості змінних вдаються до загального методурозв'язування задач лінійного програмування — так званого симплекс-методу. Процесрозв'язування задачі симплекс-методом має ітераційний характер: обчислювальніпроцедури (ітерації) одного й того самого типу повторюються у певній послідовностідоти, доки не буде отримано оптимальний план задачі або з’ясовано, що його неіснує.
Отже, симплекс-метод — це поетапна обчислювальна процедура, воснову якої покладено принцип послідовного поліпшення значень цільової функціїпереходом від одного опорного плану задачі лінійного програмування до іншого.
Алгоритм розв'язування задачі лінійного програмування симплекс-методом складаєтьсяз п'яти етапів:
1. Визначення початкового опорного плану задачі лінійногопрограмування.
2. Побудова симплексної таблиці.
3. Перевірка опорного плану на оптимальність за допомогоюоцінок />. Якщо всі оцінкизадовольняють умову оптимальності, то визначений опорний план є оптимальнимпланом задачі. Якщо хоча б одна з оцінок />не задовольняє умову оптимальності, то переходять до нового опорногоплану або встановлюють, що оптимального плану задачі не існує.
4. Перехід до нового опорного плану задачі виконуєтьсявизначенням розв'язувального елемента та розрахунком нової симплексної таблиці.
5. Повторення дій починаючи з п. 3. Розглянемо докладнішекожний з етапів алгоритму.
1. Визначення першого опорного плану починають із записузадачі лінійного програмування в канонічній формі, тобто у виглядіобмежень-рівнянь з невід'ємними правими частинами. Якщо в умові задачі присутніобмеження-нерівності, то перетворення їх на рівняння виконується за допомогою додатковихзмінних, які вводяться до лівої частини обмежень типу «» — зі знаком «-». У цільовій функціїзадачі додаткові змінні мають коефіцієнт нуль.
Після зведення задачі до канонічного вигляду її записують увекторній формі. За означенням опорного плану задачі лінійного програмуванняйого утворюють т одиничних лінійно незалежних векторів, які становлятьбазис w-вимірного простору (де m — кількістьобмежень у задачі лінійного програмування).
На цьому етапі розв'язування задачі можливі такі випадки:
після запису задачі у векторній формі в системі обмежень єнеобхідна кількість одиничних векторів. Тоді початковий опорний планвизначається безпосередньо без додаткових дій;
у системі обмежень немає необхідної кількості одиничнихнезалежних векторів. Тоді для побудови першого опорного плану застосовують методштучного базису. Ідея його полягає в тому, що відсутні одиничні вектори можнадістати, увівши до відповідних обмежень деякі змінні з коефіцієнтом +1, якіназиваються штучними. У цільовій функції задачі лінійного програмуванняштучні змінні мають коефіцієнт +М (для задачі на min) або —М (для задачіна max), де М— досить велике додатне число.
Визначені одиничні лінійно незалежні вектори утворюютьбазис, і змінні задачі, що відповідають їм, називають базисними, а всі іншізмінні — вільними, їх прирівнюють до нуля та з кожногообмеження задачі визначають значення базисних змінних. У такий спосіб отримуютьпочатковий опорний план задачі лінійного програмування.
2. Подальший обчислювальний процес та перевірку опорногоплану на оптимальність подають у вигляді симплексної таблиці.
У першому стовпчику таблиці — «Базис» — записують базиснізмінні опорного плану, причому в тій послідовності, в якій вони розміщуються всистемі обмежень задачі.
Наступний стовпчик симплексної таблиці — «Сбаз» —коефіцієнти при базисних змінних у цільовій функції задачі.
У третьому стовпчику — «План» — записують значення базиснихзмінних і відшукувані у процесі розв'язування задачі компоненти оптимальногоплану.
У решті стовпчиків симплексної таблиці, кількість якихвідповідає кількості змінних задачі, записують відповідні коефіцієнти з кожногообмеження задачі лінійного програмування.
3. Перевіряють опорний план на оптимальність згідно знаведеною далі теоремою.
Теорема (ознака оптимальності опорного плану). Опорнийплан /> задачі лінійного програмуванняє оптимальним, якщо для всіх /> виконуєтьсяумова /> (для задачі на max) або: /> (для задачі на min)
Якщо для побудови опорного плану було використано методштучного базису, необхідною умовою оптимальності є також вимога, щоб у процесірозв'язування задачі всі штучні змінні були виведені з базису і дорівнювалинулю.
Значення оцінок />визначаютьза формулою
/>
або безпосередньо із симплексної таблиці як скалярнийдобуток векторів-стовпчиків «Сбаз» та «xj» мінусвідповідний коефіцієнт />.Розрахованіоцінки записують в окремий рядок симплексної таблиці, який називають оцінковим.
У процесі перевірки умови оптимальності можливі таківипадки:
а) усі/>задовольняютьумову оптимальності, і тоді визначений опорний план єоптимальним;
б) не всі /> задовольняють умову оптимальності, і тоді потрібно виконатиперехід до наступного, нового опорного плану задачі.
4. Перехід від одного Опорного плану до іншого виконуєтьсязміною базису, тобто виключенням з нього деякої змінної та введенням замістьнеї нової з числа вільних змінних задачі.
Змінна, яка включається до нового базису, відповідає тійоцінці/>, що не задовольняє умовуоптимальності. Якщо таких оцінок кілька, серед них вибираютьнайбільшу за абсолютною величиною і відповідну їй змінну вводять до базису.Припустимо, що індекс зазначеної змінної/>.Відповідний стовпчик симплексної таблиці називають напрямним.
Для визначення змінної, що має бути виключена з базису,знаходять для всіх додатних /> напрямногостовпчика величину /> .Вибираютьнайменше значення 6, яке вказує на змінну, що виводиться з базису. Припустимо,що це виконується для /> .Відповідний рядок симплексної таблиці називатиметься напрямним.
Перетином напрямного стовпчика та напрямного рядкавизначається число симплексної таблиці />,яке називають розв'язувальним елементом. За допомогоюелемента /> і методу Жордана—Гаусса розраховують новусимплексну таблицю.
Далі ітераційний процес повторюють доти, доки не будевизначено оптимальний план задачі.
У разі застосування симплекс-методу для розв'язування задачлінійного програмування можливі такі випадки.
1. Якщо в оцінковому рядку останньої симплексної таблиціоцінка /> відповідає вільній(небазисній) змінній, то це означає, що задача лінійного програмування маєальтернативний оптимальний план. Отримати його можна, вибравши розв'язувальнийелемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.
2. Якщо при переході у симплекс-методі від одного опорногоплану задачі до іншого в напрямному стовпчику немає додатних елементів/>, тобто неможливо вибратизмінну, яка має бути виведена з базису, то це означає, що цільова функціязадачі лінійного програмування є необмеженою й оптимальних планів не існує.
3. Якщо для опорного плану задачі лінійного програмування всі оцінки />задовольняють умовуоптимальності, але при цьому хоча б одна штучна змінна є базисною імає додатне значення, то це означає, що система обмежень задачі несумісна йоптимальних планів такої задачі не існує.
Навчальні завдання розв'язування задач симплекс-методом
Розглянемо застосування симплекс-методу для розв'язуваннядеяких задач лінійного програмування.
Задача 2.41.
Продукція чотирьох видів А, В, С і Дпроходить послідовну обробку на двох верстатах. Тривалість обробки одиниціпродукції кожного виду задано таблицею.Верстат Тривалість обробки, год, одиниці продукції А В С Д
1
2
2
3
3
2
4
1
2
2
Витрати на виробництво одиниці продукції кожного видувизначають як величини, прямо пропорційні до часу використання верстатів (умашино-годинах). Вартість однієї машино-год становить 10 дол. для верстата 1 і15 дол. — для верстата 2. Можливий час використання верстатів обмежений: дляверстата 1 він становить 450 машино-год, а для верстата 2 — 380машино-год.
Ціна одиниці продукції кожного виду дорівнює відповідно 73,70, 55 та 45 дол.
Визначити оптимальний план виробництва продукції всіхчотирьох видів, який максимізує загальний чистий прибуток.
Побудова математичної моделі. Нехай />— план виробництвапродукціїу-го виду, де у може набувати значень від 1 до 4.
Умовами задачі будуть обмеження на час використанняверстатів для виробництва продукції всіх видів:
для верстата 1 /> (машино-год);
для верстата 2 />(машино-год).
Цільова функція задачі визначається як загальний чистийприбуток від реалізації готової продукції і складається з різниці між ціною тасобівартістю виготовлення продукції кожного виду:
/>
Отже, математична модель поставленої задачі маєтакий вигляд:
/>
Розв'язування. Розв'яжемо задачу симплекс-методом згідно зрозглянутим алгоритмом.
1. Запишемо систему обмежень задачі в канонічному вигляді.Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши долівої частини обмежень додаткові змінні х5 та х6.
/>
Ці додаткові змінні за економічним змістом означаютьможливий, але не використаний для виробництва продукції час роботи верстатів 1та 2. У цільовій функції Z додаткові змінні мають коефіцієнти,які дорівнюють нулю:
/>
Канонічну систему обмежень задачі запишемо у векторнійформі: >і
/>
де
/>
Оскільки вектори />та />одиничні та лінійнонезалежні, саме з них складається початковий базис у зазначеній системівекторів. Змінні задачі />та />, що відповідають одиничнимбазисним векторам, називають базисними, а решту вільнимизмінними задачі лінійного програмування. Прирівнюючи вільні змінні донуля, з кожного обмеження задачі дістаємо значення базисних змінних:
/>
Згідно з визначеними /> векторнаформа запису системи обмежень задач матиме вигляд
/>
Оскільки додатні коефіцієнти х5 та х6відповідаютьлінійно незалежним векторам, то за означенням
/>
є опорним планом задачі і для цього початкового плану
/>
2. Складемо симплексну таблицю для першого опорного планузадачі.
/>
Елементи останнього рядка симплекс-таблиці є оцінками Δj, задопомогою яких опорний план перевіряють на оптимальність. їх визначають так:
/>
У стовпчику «План» оцінкового рядка записують значенняцільової функції Z, якого вона набуває для визначеного опорного плану:/>=0-450 + 0-380 = 0.
3. Після обчислення всіх оцінок опорний план перевіряють наоптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі />(для задачі на max) або />(для задачі на min), визначенийопорний план є оптимальним. Якщо ж в оцінковому рядку присутня хоча б однаоцінка, що не задовольняє умову оптималь-ності (від'ємна в задачі на max або додатнав задачі на min), то опорний план є неоптимальним і його можна поліпшити.
У цій задачі в оцінковому рядку дві оцінки />та />суперечать умовіоптимальності, і тому перший визначений опорний план є неоптимальним. Заалгоритмом симплекс-методу необхідно від нього перейти до іншогоопорного плану задачі.
4. Перехід від одного опорного плану до іншого виконуютьзміною базису, тобто за рахунок виключення з поточного базису якоїсь змінної тавключення замість неї нової з числа вільних змінних.
Для введення до нового базису беремо змінну/>, оскільки їй відповідаєнайбільша за абсолютною величиною оцінка серед тих, які не задовольняють умовуоптимальності (/>).
Щоб визначити змінну, яка підлягає виключенню з поточногобазису, для всіх додатних елементів стовпчика «х2» знаходимовідношення /> і вибираємо найменшезначення. Згідно з даними симплексної таблиці бачимо, що min/>, і тому з базисувиключаємо змінну/>, а число/>= 3 називатимемо розв'язувальнимелементом. Подальший перехід до нового опорного плану задачі полягає впобудові наступної симплексної таблиці, елементи якої розраховують за методомЖордана—Гаусса.
Друга симплексна таблиця має такий вигляд:
/>
У цій таблиці спочатку заповнюють два перших стовпчики«Базис» і «/>», а решту елементів новоїтаблиці розраховують за розглянутими далі правилами:
1. Розв'язувальний (напрямний) рядок необхідно поділити нарозв'язувальний елемент і здобуті числа записати у відповідний рядок новоїсимплексної таблиці.
2. Розв'язувальний стовпчик у новій таблиці записують якодиничний з одиницею замість розв'язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, товідповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, товідповідний рядок переписують у нову таблицю без змін.
Усі інші елементи наступної симплексної таблиці розраховуютьза правилом прямокутника.
Щоб визначити будь-який елемент нової таблиці за цимправилом, необхідно в попередній симплексній таблиці скласти умовнийпрямокутник, вершини якого утворюються такими числами:;
1 — розв'язувальний елемент;
2 — число, що стоїть на місці елемента нової симплексноїтаблиці, який ми маємо розрахувати;
3 та 4 — елементи, що розміщуються в двох інших протилежнихвершинах умовного прямокутника.
Необхідний елемент нової симплекс-таблиці визначають так:
/>
Наприклад, визначимо елемент />,який розміщується в новій таблиці в другому рядку стовпчика «Х4». Складемоумовний прямокутник:
/>
Тоді />=(3-2-2-2):3 = 2/3. Це значення записуємо в стовпчик «/>» другого рядка другоїсимплексної таблиці.
Аналогічно розраховують усі елементи нової симплексноїтаблиці, у тому числі елементи стовпчика «План» та оцінкового рядка. Наявністьдвох способів визначення оцінок опорного плану (за правилом прямокутника та завідповідною формулою) дає змогу контролювати правильність арифметичнихобчислень на кожному кроці симплекс-методу.
Після заповнення нового оцінкового рядка перевіряємовиконання умови оптимальності />длядругого опорного плану. Цей план також неоптимальний, оскільки />. Використовуючи процедуру симплекс-методу, визначаємотретій опорний план задачі, який наведено у вигляді таблиці:
/>
В оцінковому рядку третьої симплексної таблиці немаєвід'ємних чисел, тобто всі />ізадовольняють умову оптимальності. Це означає, Що знайдено оптимальний планзадачі:
/>
Або
/>
Отже, план виробництва продукції, що передбачає випуск 48одиниць продукції А та 118 од. продукції В, оптимальний і дає найбільшийприбуток 1564 дол. При цьому час роботи верстатів використовується повністю (х5= х6 = 0).
Задачу можна розв'язати симплекс-методом, узявши не трисимплексні таблиці, а одну, в якій послідовно записувати всі ітерації.
Задача 2.42.
Розв'язати задачу 2.41 із додатковою умовою: продукція С маєвиготовлятися в кількості не менш як 9 одиниць.
Розв'язування. Математичну модель сформульованої задачізапишемо так:
/>
Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочаткузаписуємо систему обмежень у канонічній формі, а далі — у векторній:
/>
Зауважимо, що нерівність типу «>» у рівняння перетворюємовведенням у ліву частину обмеження додаткової змінної зі знаком «-».
Векторна форма запису:
/>
Серед записаних векторів є лише Два одиничні — />та />, а базис у тривимірномупросторі має складатися з трьох одиничних векторів. Ще один одиничний векторможна дістати, увівши в третє обмеження з коефіцієнтом +1 штучну змінну х8якійвідповідатиме одиничний вектор
/>
Тепер можемо розглянути розширену задачу лінійногопрограмування:
/>
На відміну від додаткових змінних штучна змінна />має в цільовій функції Z коефіцієнт +М (для задачіна min) або -М (для задачі на max), де М— доситьвелике додатне число.
У розширеній задачі базисними змінними є x5, х6,х8, а рештазмінних вільні. Початковий опорний план задачі:
/>
Складемо першу симплексну таблицю задачі:
/>
Розраховуючи оцінки першого опорного плану, дістаємо z0= 0 — 9М, Z1 – С1= -8, Z2 – С2 = -10, Z3 — С3= 0 — М і т. д. Як бачимо, значення оцінок складаються з двохчастин, одна з яких містить М, а інша — просто число. Тому длязручності розбиваємо оцінковий рядок на два. У перший оцінковий рядок записуємопросто число, а в другий — число з коефіцієнтом М.
Оцінки першого плану не задовольняють умову оптимальності, ітому він є неоптимальним. Згідно з алгоритмом, розглянутим у задачі 2.41,виконуємо перехід до наступного опорного плану задачі.
Подальше розв'язування задачі наведене у вигляді таблиці:
/>
Оптимальним планом задачі є вектор
/>
Отже, оптимальним є виробництво 57 одиниць продукції А, 100одиниць продукції В і 9 одиниць продукції С. Тоді прибуток буде найбільшим істановитиме 1456 дол.
Висновок
Змістматематичного програмування складає теорія і методи розв’язання задач прознаходження екстремумів функції на множинах, які визначаються лінійними інелінійними обмеженнями (рівностями і нерівностями).
Лінійнематематичне програмування являє собою розв’язок задач: загальної, канонічної істандартної форми.
Загальнаформа задачі лінійного програмування не є досить простим і ефективним способомрозв’язання її. Тому, як правило, задачу зводять до стандартної форми. Взалежності від методів, які застосовуються, розрізняють дві стандартні форми:першу і другу.
При розв’язанні задач лінійного програмування майже завждискладають математичну модель. Математична модель стандартної задачі – це їїспрощений образ, поданий у вигляді сукупності математичних нерівностей.
Література
1. ЦегеликГ.Г. Лінійне програмування. – Львів, 1995.
2. Акулич.Математичне програмування в прикладах і задачах. – Москва, 1986.
3. Математичнепрограмування. Навч.-метод. Посібник для самостійного вивчення дисципліни /В.В. Вітлінський, С.І. Наконечний, Т.О. Терещенко. М-во освіти і науки України.КНЕУ. – К.: КНЕУ, 2001.
4. Математичнепрограмування [Текст] навч. посібник для студ. вищ. закладів, І.Ю. Іванченко. –К.: ЦУЛ, 2007.
5. Математическоепрограммирование и моделирование экономических процессов: Учеб. для студ.лесотехн. вузов. – Санкт-Петербург, гос. лесотехн. акад. СПб: Изд-во ДНК, 2003.
6. Математичнепрограмування. Навч. посібник для студентів напрямів «Економіка іпідприємство», «Менеджмент» / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка таін.; М-во освіти і науки України. Нац. Ун-т «Львів. політехніка». – Л.:Інтелект-Захід, 2004.
7. Математичнепрограмування: Навч. посібник / С.І. Наконечний, С.С. Савіна; М-во освіти інауки України. КНЕУ. – К.: КНЕУ, 2003.
8. Гасс С. Линейноепрограммирование (методы и приложения). Пер. с англ. Гольштейна Е.П. иСушкевича М.И. Под ред. Юдина Д.Б. – М.: Физат гиз, 1961.
9. Математичнепрограмування: Навч. посібник / В.М.Дякон, Л.Є.Ковальов; за заг. ред. В.М. Міхайленка.– К.: Вид-во Європ. ун-ту, 2007.
10. Мазаракі А.А., ТолбатовЮ.А. Математичне програмування. Excel: Навч. посіб. для студ. екон.спеціал. вузів. – К.: Четверта хвиля, 1998.