Xreferat.com » Рефераты по экономико-математическому моделированию » Стандартна задача лінійного програмування

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

Вступ


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

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


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


Розв'язання. Введенням однієї додаткової змінної Стандартна задача лінійного
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

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