Рефетека.ру / Эк.-мат. моделирование

Курсовая работа: Стандартна задача лінійного програмування

Вступ


Історія предмета включає в себе, з одного боку, історію математичних джерел та методів, а з другого — історію застосування цих методів у прикладних галузях, насамперед в економіці.

Як найпершу економічну модель, що містила деякі найпростіші ідеї лінійного програмування, слід назвати „Економічні таблиці" лейб-медика короля Людовика 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. Звести до першої стандартної форми таку задачу лінійного програмування:


Стандартна задача лінійного програмування


Розв'язання. Введенням однієї додаткової змінної Стандартна задача лінійного програмування та заміною Стандартна задача лінійного програмування зводимо задачу до вигляду


Стандартна задача лінійного програмування

Хоч тут кількість змінних без обмеження на знак і менша від кількості основних обмежень, їх не можна вивести з задачі, оскільки вектори-стовпці їхніх коефіцієнтів пропорційні і не можуть разом входити до базисного мінору. Тому виведемо одну з них, а другу замінимо різницею двох невід'ємних змінних.

Запишемо задачу в таблицю (в нульовий рядок записане рівняння, що відповідає цільової функції:Стандартна задача лінійного програмування


№ рядка

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

0 -6 3 4 -5 0 0
1 2 -6 -2

Стандартна задача лінійного програмування

0 12
2 3 1 -2 1 0 6
3 1 -1 -4 2 1 8

Вибравши Стандартна задача лінійного програмування= 1 ключовим елементом, переходимо до нової таблиці.


№ рядка

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

0 4 -27 -6 0 0 60
1 2 -6 _2 1 0 12
2 1 7 0 0 0 -6
3 -3 11 0 0 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<40.


Всі умови задачі виконуються, до того ж оптимальний план дає змогу повністю використати два види ресурсів з мінімальним надлишком третього.

Виручка становитиме: 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 дол.

Висновок


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

Лінійне математичне програмування являє собою розв’язок задач: загальної, канонічної і стандартної форми.

Загальна форма задачі лінійного програмування не є досить простим і ефективним способом розв’язання її. Тому, як правило, задачу зводять до стандартної форми. В залежності від методів, які застосовуються, розрізняють дві стандартні форми: першу і другу.

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


Література


Цегелик Г.Г. Лінійне програмування. – Львів, 1995.

Акулич. Математичне програмування в прикладах і задачах. – Москва, 1986.

Математичне програмування. Навч.-метод. Посібник для самостійного вивчення дисципліни / В.В. Вітлінський, С.І. Наконечний, Т.О. Терещенко. М-во освіти і науки України. КНЕУ. – К.: КНЕУ, 2001.

Математичне програмування [Текст] навч. посібник для студ. вищ. закладів, І.Ю. Іванченко. – К.: ЦУЛ, 2007.

Математическое программирование и моделирование экономических процессов: Учеб. для студ. лесотехн. вузов. – Санкт-Петербург, гос. лесотехн. акад. СПб: Изд-во ДНК, 2003.

Математичне програмування. Навч. посібник для студентів напрямів «Економіка і підприємство», «Менеджмент» / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка та ін.; М-во освіти і науки України. Нац. Ун-т «Львів. політехніка». – Л.: Інтелект-Захід, 2004.

Математичне програмування: Навч. посібник / С.І. Наконечний, С.С. Савіна; М-во освіти і науки України. КНЕУ. – К.: КНЕУ, 2003.

Гасс С. Линейное программирование (методы и приложения). Пер. с англ. Гольштейна Е.П. и Сушкевича М.И. Под ред. Юдина Д.Б. – М.: Физат гиз, 1961.

Математичне програмування: Навч. посібник / В.М.Дякон, Л.Є.Ковальов; за заг. ред. В.М. Міхайленка. – К.: Вид-во Європ. ун-ту, 2007.

Мазаракі А.А., Толбатов Ю.А. Математичне програмування. Excel: Навч. посіб. для студ. екон. спеціал. вузів. – К.: Четверта хвиля, 1998.

Похожие работы:

  1. • Математические модели и методы обоснования управленческих ...
  2. • Лінійна модель виробництва
  3. • Математичні методи та моделі в управлінні аграрним ...
  4. • Математична модель транспортної системи підприємства
  5. • Математичне програмування в економіці
  6. • Економічні задачі лінійного програмування і методи їх ...
  7. • Розв"язання задач лінійного програмування
  8. •  ... Якобі для рішення задач лінійного програмування
  9. • Побудова математичної моделі задачі лінійного ...
  10. • Побудова та реалізація економіко-математичної ...
  11. • Розв"язання лінійних задач методами лінійного ...
  12. • Рішення задач цілочисленного програмування
  13. • Розв'язок задач лінійного програмування. Задача ...
  14. • Будування математичної моделі економічної задачі ...
  15. •  ... інвестицій за допомогою динамічного програмування
  16. • Математичне моделювання економічних систем
  17. •  ... обладнання за допомогою динамічного програмування
  18. • Історія та створення СУБД
  19. • Функціональне відображення поведінки споживача
Рефетека ру refoteka@gmail.com