Дата конвертації24.03.2017
Розмір58.55 Kb.
Типкурсова робота

Скачати 58.55 Kb.

Математичні методи в рішенні економічних задач

Вступ

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

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

Завдання роботи:

вивчити літературу з даної теми

для заданого варіанту отримати рішення задачі лінійного програмування:

- Графічним методом;

- Симплекс - методом для прямої задачі;

- Симплекс - методом для двоїстої задачі.

- Сформулювати двоїсту задачу і знайти її рішення.

- Сформулювати і вирішити транспортну задачу.

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


Завдання математичного та лінійного програмування

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

При цьому складаються рівняння або нерівності, які пов'язують різні показники (змінні) досліджуваного процесу, утворюючи систему обмежень. У цих співвідношеннях виділяються такі змінні, змінюючи які можна отримати оптимальне значення основного показника даної системи (прибуток, дохід, витрати і т.п.). Відповідні методи, що дозволяють вирішувати зазначені завдання, об'єднуються під загальною назвою «математичне програмування», або «математичні методи дослідження операцій».

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

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

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

Методами математичного програмування вирішуються завдання про розподіл ресурсів, плануванні випуску продукції, ціноутворення, транспортні завдання і т.п.

Побудова математичної моделі економічної задачі включає наступні етапи:

1) вибір змінних завдання;

2) складання системи обмежень;

3) вибір цільової функції.

Змінними задачі називаються величини x1, x2, ..., хп, які повністю характеризують економічний процес. Їх зазвичай записують у вигляді вектора Х = (х1, х2, ..., хп).

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

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

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

Допустимим рішенням (планом) задачі лінійного програмування (ЗЛП) називається будь-n-мірний вектор Х = (х1, х2, ..., хn), що задовольняє системі обмежень і умов невід'ємності.

Безліч допустимих рішень (планів) завдання утворює область допустимих рішень (ОДР).

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

Загальний вигляд задачі лінійного програмування:

,

обмеження:

1. Праві частини всіх обмежень повинні бути невід'ємними . Якщо який-небудь з коефіцієнтів <0, то необхідно коефіцієнти обмеження зліва і справа помножити на "-1" і змінити знак даного обмеження на протилежний;

2. Всі обмеження повинні бути представлені у вигляді рівності, тому при переході від нерівності до рівності використовують апарат додаткових змінних.

Якщо вихідні обмеження визначають витрата деякого ресурсу (знак " "), То змінні

слід інтерпретувати як залишок, або невикористану частину ресурсу. В цьому випадку - Залишкова змінна і вводиться в рівняння зі знаком "+". Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак " "), То вводиться надлишкова змінна

знаком "-".

змінні:

Всі змінні повинні бути невід'ємними, тобто

.

Якщо змінна не має обмеження в знаку, то її потрібно представити як різниця двох невід'ємних змінних:

,

де . Таку підстановку варто використовувати у всіх обмеженнях, що містять цю змінну, а також у натуральному вираженні для цільової функції.

Якщо така змінна потрапляє в оптимальне рішення, то .

Цільова функція:

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

Приступаємо до вирішення завдання.

Потрібно скласти план виробництва виробів А₁ і А₂ що забезпечує максимальний прибуток підприємства від реалізації готової продукції. необхідно:

Вирішити задачу геометрично;

Вирішити задачу симплекс-методом (аналітичним та табличним)

Сформулювати двоїсту задачу і знайти її рішення.


завдання №1

Підприємство передбачає випускати два види продукції А₁ і А₂, для виробництва яких використовується сировина трьох видів. Виробництво забезпечене сировиною кожного виду в кількостях: b₁, b₂, b₃ кг. На виготовлення одиниці виробу А₁ потрібно затратити сировини кожного виду а₁₁, а₂₁, а₃₁ кг, відповідно, а для одиниці виробу А₂ - а₁₂, а₂₂, а₃₂ кг. Прибуток від реалізації одиниці виробу А₁ становить с₁ грош, для одиниці виробу А₂ - с₂ грош

Допоміжна таблиця

вид сировини

Продукція

Обмеження по сировині

А₁

А₂

1-й

а₁₁

а₁₂

b₁

2-й

а₂₁

а₂₂

b₂

3-й

а₃₁

а₃₂

b₃

прибуток

с₁

с₂

Рішення завдання геометричним методом

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

Перший крок при використанні графічного методу полягає в геометричному поданні допустимих рішень, тобто побудові області допустимих рішень (ОДР.), в якій одночасно задовольняються всі обмеження моделі. При отриманні графічного рішення змінна X1 відкладається по горизонтальній осі, а X2 - по вертикальній. При формуванні ОДР необхідно запобігти отриманню неприпустимих рішень, які пов'язані з необхідністю виконання умови невід'ємності змінних. Перед побудовою необхідно визначити квадранти, в яких буде розташовуватися ОДР. Квадранти визначаються знаками змінних X1 і X2. Умови невід'ємності змінних X1 і X2 обмежують область їх допустимих значень першим квадрантом. Якщо змінна X1 не обмеженої в знаку, то область обмежується першим і другим квадрантом, якщо X2, то - першим і четвертим квадрантом.

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

В результаті побудов виходить багатокутник, який визначає простір рішень. Якщо одне з обмежень має знак "=", то ОДР вироджується у відрізок.

У кожній точці, що належить області або межам багатокутника рішень, все обмеження виконуються, тому всі рішення, які відповідають цим точкам, є допустимими. Простір рішень містить нескінченне число таких точок, незважаючи на це, можна знайти оптимальне рішення. Для цього необхідно побудувати в площині змінних X1, X2 градієнт цільової функції. Визначення оптимальної точки залежить від того завдання, яке необхідно вирішити.

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

Після знаходження оптимальної точки простору рішень визначають її координати X1 *, X2 * і значення цільової функції F * в ній.Правильність вибору оптимальної точки можна перевірити розрахунком цільової функції в вершинах багатогранника рішень. У ЗЛП область допустимих рішень завжди є опуклим безліччю, тобто таким безліччю, що поряд з будь-якими двома точками, які належать цій множині, цього ж безлічі належить і відрізок, що з'єднує ці дві точки. Будь-яка функція найшвидшим образом збільшується в напрямку свого градієнта.

Далі приступаємо до вирішення завдання:

Занесемо необхідні нам дані в допоміжну таблицю:

вид сировини

Продукція

Обмеження по сировині

А₁

А₂

1-й

5

2

750

2-й

4

5

807

3-й

1

7

840

прибуток

30

49

Рішення:

Припустимо, що буде виготовлено Х₁ одиниць виробів виду А₁ і Х₂ одиниць - виду А₂. Оскільки виробництво продукції обмежена наявними в розпорядженні підприємства сировиною кожного виду і кількість виготовлених виробів не може бути негативним, повинні виконуватися нерівності:


Загальний прибуток від реалізації Х₁ виробів А₁ і Х₂ виробів виду А₂ складе

F = 30Х₁ + 49Х₂ .

Таким чином, ми приходимо до наступної математичної задачі: серед всіх невід'ємних розв'язків даної системи лінійних нерівностей потрібно знайти таке, при якому функція F приймає максимальне значення.

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

Ці прямі зображені на рис №1. Кожна з побудованих прямих ділить площину на дві півплощини. Координати точок одній півплощині задовольняють вихідному нерівності, а інший - ні. Щоб визначити шукану полуплоскость, потрібно взяти якусь точку, що належить одній з півплощини, і перевірити, чи задовольняють її координати даного нерівності. Якщо координати взятої точки задовольняють даному нерівності, то шуканої є та полуплоскость, якій належить ця точка, в іншому випадку - інша напівплощина.

Знайдемо, наприклад, напівплощина, яка визначається нерівностями.


Побудуємо область допустимих рішень:

для прямої

С (0; 0) => 5 · 0 + 2 · 0 = 0, а 0≤750, значить пряма прагне до нуля (рис.1)

для прямої


В (0; 0) => 4 · 0 + 5 · 0 = 0, а 0≤807, значить пряма прагне до нуля (рис.1)

для прямої

А (0; 0) => 1 · 0 + 7 · 0 = 0, а 0≤840, значить пряма прагне до нуля (рис.1). Це і показано стрілками.

Перетин отриманих напівплощин і визначає багатокутник рішень даної задачі.

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

Щоб знайти зазначену точку, побудуємо вектор ñ = (30; 49) і пряму 30Х1 + 49Х2 = h, де h - деяка постійна така, що пряма 30Х1 + 49Х2 = h має загальні точки з багатокутником рішень. Покладемо, наприклад, h = 510 і побудуємо пряму 30Х1 + 49Х2 = 510 (рис. №1).

Якщо тепер взяти якусь точку, що належить побудованої прямий і многоугольнику рішень, то її координати визначають такий план виробництва виробів А1 і А2, при якому прибуток від їх реалізації дорівнює 510 руб. Далі, вважаючи h рівним деякому числу, більшому ніж 510, ми будемо отримувати різні паралельні прямі. Якщо вони мають загальні точки з багатокутником рішень, то ці точки визначають плани виробництва виробів А1 і А2, при яких прибуток від їх реалізації перевершить 510 руб.

Переміщаючи побудовану пряму 30Х1 + 49Х2 = 510 в напрямку вектора ñ, бачимо, що останньою спільною точкою її з багатокутником рішень задачі служить точка В. Координати цієї точки і визначають план випуску виробів А1 і А2, при якому прибуток від їх реалізації є максимальною.

Знайдемо координати точки В як точки перетину прямих і . Отже, її координати задовольняють рівнянням цих прямих

Вирішимо цю систему рівнянь:

Х1 = 840 - 7х2, підставимо отримане в перше рівняння => 3360 - 28Х2 + 5х2 = 807 => 23Х2 = 2553 =>

Х2 = 111, з цього рішення випливає, що Х1 = 840 - 7 · 111 = 63 => Х1 = 63

Отже, якщо підприємство виготовить 63 виробів виду А1 і 111 виробів виду А2, то воно отримає максимальний прибуток, рівну Fmax = 30 · 63 + 49 · 111 = 7329 руб.

Рішення завдання аналітичним симплекс-методом

Симплексний метод - це метод цілеспрямованого перебору опорних рішень задачі лінійного програмування. Він дозволяє за кінцеве число кроків розрахунку або знайти оптимальне рішення, або встановити, що оптимального рішення не існує.

Ідея симплексного методу полягає в наступному. Використовуючи систему обмежень, наведену до загального вигляду, т. Е. До системи т лінійних рівнянь з п змінними (т <п), знаходять її будь-базисне рішення, по можливості найбільш просте. Якщо перше ж знайдене базисне рішення виявилося допустимим, то перевіряють його на оптимальність. Якщо воно не оптимально, то переходять до іншого допустимому базисного вирішення.

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

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

Дамо математичне формулювання завдання. Нехай Х1 і Х2 - кількість виробів А1 і А2, запланованих до виробництва. Так як кількість сировини по кожному виду обмежена, то їх необхідно виконувати такі нерівності:

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

F = 30Х₁ + 49Х₂ .

Отже, завдання зводиться до знаходження максимуму функції F = 30Х₁ + 49Х₂ при обмеженнях:


Для відомості системи обмежень-нерівностей до системи рівнянь додамо до лівої частини кожного нерівності додаткові невід'ємні змінні Х3, Х4, Х5. В умовах даної задачі вони мають конкретне економічний зміст, а саме висловлюють обсяг залишків сировини кожного виду після виконання плану по випуску продукції. Після введення додаткових змінних отримаємо систему рівнянь:


5х1 + 2Х2 + Х3 = 750

4х1 + 5 Х2 + Х4 = 807

Х1 + 7х2 + Х5 = 840

Хi≥0, i = 1 ... .5

Потрібно знайти таке припустиме базисне рішення цієї системи обмежень, яке б максимізувати лінійну форму F = 30Х₁ + 49Х₂.

Так як система обмежень є система трьох незалежних рівнянь з двома змінними, то число базисних змінних має дорівнювати трьом, а число вільних - двом.

Для вирішення завдання симплексним методом перш за все потрібно знайти будь-базисне рішення. В даному випадку це легко зробити. Для цього достатньо взяти в якості базисних додаткові змінні Х3, Х4, Х5. Так як коефіцієнти при цих змінних утворюють одиничну матрицю, то відпадає необхідність обчислювати визначник. Вважаючи вільними змінні Х1 і Х2 рівними нулю, отримаємо базисне рішення (0; 0; 750; 807; 840), яке до того ж виявилося допустимим. Переходимо до пошуків оптимального рішення.

I ш а р Базисні змінні: Х3, Х4, Х5; вільні змінні: Х1 і Х2. В системі (1.1) базисні змінні висловимо через вільні. Для того щоб судити, чи залишити вільні змінні в числі вільних або їх вигідніше з точки зору наближення до оптимального рішення перевести в базисні, слід висловити через них і лінійну форму (в даному випадку вона вже виражена через змінні Х1 і Х2). Тоді отримаємо:

Х3 = 750 - 5 Х1 - 2 Х2

Х4 = 807 - 4 Х1 - 5х2

[Х5 = 840 - Х1 - 7х2]

F = 30Х₁ + 49Х₂

При Х1 = Х2 = 0 маємо Х3 = 750, Х4 = 807, Х5 = 840, що дає базисне рішення (0; 0; 750; 807; 840), яке ми прийняли за вихідне. При цьому базисному рішенні значення лінійної форми


F = 30Х₁ + 49Х₂ = 0.

Коли ми припустили, що Х1 = Х2 = 0 (підприємство нічого не випускає), була поставлена ​​мета - знайти перше, байдуже яке, базисне рішення. Ця мета досягнута. Тепер від цього початкового рішення потрібно перейти до іншого, при якому значення лінійної форми збільшиться. З розгляду лінійної форми видно, що її значення зростає при збільшенні значень змінних Х1 і Х2. Іншими словами, ці змінні невигідно вважати вільними, т. Е. Рівними нулю, їх потрібно перевести в число базисних. Це і означає перехід до нового базисного рішення. При симплексному методі на кожному кроці рішення передбачається переклад в число базисних тільки однією з вільних змінних. Переведемо в число базисних змінну Х2 так як вона входить в вираз лінійної форми F = 30Х₁ + 49Х₂ з великим коефіцієнтом.

Як тільки одна з вільних змінних переходить в число базисних, одна з базисних повинна бути переведена на її місце в число вільних.Яку ж з чотирьох базисних змінних потрібно вивести? Відповісти на це питання допоможуть наступні міркування: значення Х2 необхідно зробити якомога більшою, так як це відповідає кінцевої мети - максимізації F. Однак виявляється, що збільшення Х2 може тривати тільки до відомих меж, а саме до тих пір, поки не порушиться вимога невід'ємності змінних.

Х2 = min ; = Min {375; 161,4; 120} = 120,

далі Х2 переведемо в базисні замість Х5.

II ш а р Базисні змінні: Х3, Х4, Х2; вільні змінні: Х1, Х5. Висловимо базисні змінні і лінійну форму через вільні. В системі (1.2) беремо то рівняння, з якого отримано мінімальне значення відношення вільного члена до коефіцієнта при Х2. В даному випадку це третє рівняння, яке виділено рамкою. Висловивши з цього рівняння Х2, отримаємо:

Х2 = 120 - Х1 - Х5

Підставивши цей вираз Х2 в усі інші рівняння системи (1.2) і в лінійну форму F, отримаємо:

Х2 = 120 - Х1 - Х5

Х3 = 750 - 5 Х1 - 2 (120 - Х1 - Х5) = 510 - Х1 + Х5

Х4 = 807 - 4 Х1 - 5 (120 - Х1 - Х5) = 207 - Х1 + Х5


Х2 = 120 - Х1 - Х5

(1.3)

Х3 = 510 - Х1 + Х5

[Х4 = 207 - Х1 + Х5]

F = 30Х₁ +49 (120 - Х1 - Х5) = 5880 + 23 Х1 - 7 Х5

При Х1 = Х5 = 0 маємо F = 5880. Це вже краще, ніж на I етапі, але не шуканий максимум. Подальше збільшення функції F можливо за рахунок введення змінної Х1 в число базисних; так як ця змінна входить в вираз F з позитивним коефіцієнтом, тому її збільшення призводить до збільшення лінійної форми і її невигідно вважати вільної, т. е. дорівнює нулю.

Для відповіді на питання, яку змінну вивести з базисних в вільні, приймемо:

Х1 = min ; = Min {840; 108,2; 63} = 63,

далі Х1 переведемо в базисні замість Х4.

III крок. Базисні змінні: Х1, Х2, Х3; вільні змінні: Х4, Х5. Висловимо основні змінні і лінійну форму через вільні. З останнього рівняння системи (1.3) маємо:

Х1 = 207 + Х5 - Х4 => Х1 = 63 + Х5 - Х4

Підставляючи цей вираз в інші рівняння і в лінійну форму, отримаємо:

Х1 = 63 + Х5 - Х4

Х2 = 120 - (63 + Х5 - Х4) - Х5 = 111 - Х5 - Х4

Х3 = 510 - (63 + Х5 - Х4) + Х5 = 213 - Х5 + Х4

Х1 = 63 + Х5 - Х4

(1.4)

Х2 = 111 - Х5 - Х4

Х3 = 213 - Х5 + Х4

F = 5880 + 23 (63 + Х5 - Х4) - 7 Х5 = 7329 - 2 Х5 - 7 Х4

Так як в вираз лінійної форми змінні Х4 і Х5 входять з негативним коефіцієнтами, то ніяке збільшення F за рахунок цих змінних неможливо.

Отже, на III етапі критерій оптимальності досягнутий і задача вирішена. Оптимальним є рішення (63; 111; 213; 207; 0), при якому Fmаx = 7329.

Таким чином, для отримання максимального прибутку, що дорівнює 7329 ден. од., з цих запасів сировини підприємство має виготовити 63 види виробів А1 і 111ізделій виду А2.

Відповідь: Х1 * = 63; Х2 * = 111. Fmаx = 7329.

Вирішити завдання табличним симплексним методом

Розглянутий симплексний метод розв'язання ЗЛП в попередньому пункті можна звести до запису однотипно заповнюваних таблиць. Здійснити це можливо, дотримуючись наступного алгоритму:

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

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

Обчислити оцінки розкладів векторів умов по базису опорного рішення і заповнити симплексну таблицю.

Якщо виконується ознака єдиності оптимального рішення (для будь-якого вектора умов, що не входить в базис, оцінка відмінна від нуля), то рішення задачі закінчується.

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

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

Якщо пункти 4-6 алгоритму не виконуються, знаходять нове опорне рішення з використанням умов перебування оптимального рішення.

Складемо математичну модель задачі. Шуканий випуск продукції А1 позначимо через Х1, продукції А2 - Х2. Оскільки існує ембарго на виділений підприємству фонд сировини кожного виду, змінні Х1, Х2 повинні задовольняти наступній системі нерівностей:

5х1 + 2Х2 ≤ 750

(1.1)

4х1 + 5 Х2 ≤ 807

Х1 + 7х2 ≤ 840

Х1≥0, Х2≥0

Загальна вартість виробленої підприємством продукції за умови випуску Х1ізделій А1 і Х2 виробів А2 становить F = 30Х₁ + 49Х₂

За своїм економічним змістом змінні Х1 і Х2 можуть приймати тільки невід'ємні значення: Х1, Х2 ≥0.

Таким чином, приходимо до наступної математичної задачі: серед всіх невід'ємних розв'язків системи нерівностей (1.1) потрібно знайти таке, при якому функція F = 30Х₁ + 49Х₂ приймає максимальне значення.

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


5х1 + 2Х2 + Х3 = 750

(1.1)

4х1 + 5 Х2 + Х4 = 807

Х1 + 7х2 + Х5 = 840

Хi≥0, i = 1 ....5

Ці додаткові змінні за економічним змістом означають яке не використовується при даному плані виробництва кількість сировини того чи іншого виду. Наприклад, Х3 - це неиспользуемое кількість сировини 1-ого виду і т.д.

Для вирішення завдання табличним симплексним методом перш за все потрібно знайти будь-базисне рішення. В даному випадку це легко зробити. Для цього достатньо взяти в якості базисних додаткові змінні Х3, Х4, Х5., А в якості вільних змінні Х1 і Х2 рівними нулю, отримаємо базисне рішення (0; 0; 750; 807; 840), яке до того ж виявилося допустимим. F = 30Х₁ + 49Х₂ => F - 30Х₁ - 49Х₂ = 0

Переходимо до пошуків оптимального рішення.

Складемо симплексну таблицю:

Як видно з таблиці (2.1), значення всіх змінних відповідають такому «плану», при якому нічого не виробляється, сировина не використовується і значення цільової функції дорівнює нулю (т. Е. Вартість виробленої продукції відсутня). Цей план, звичайно, не є оптимальним.

Це видно і з 4-го рядка таблиці (2.1), так як в ній є два від'ємних числа: (- 30; - 49; 0; 0; 0). Негативні числа не тільки свідчать про можливість збільшення загальної вартості виробленої продукції, але і показують, на скільки збільшиться ця сума при введенні в план одиниці того чи іншого виду продукції.

Навіть з економічної точки зору найбільш доцільним є включення в план виробництва виробів А2. Це ж необхідно зробити і на підставі формальної ознаки симплексного методу, оскільки максимальне за абсолютною величиною негативне число -49, варто в 4-му рядку 2-го стовпця => цей стовпець є разрешающім.Определяем вектор, що підлягає виключенню з базису і вибираємо роздільну рядок . Для цього знаходимо:

Х2 = min ; ; = 120.

знайшовши число = 120, => 3-тя рядок (Х5) є роздільною. Отже, в базис введемо Х2 замість Х5. Тим самим ми, з економічної точки зору визначили, скільки виробів А2 підприємство може виготовляти з урахуванням норм витрати і наявних обсягів сировини кожного виду.

Таблиця (2.1)

базисні змінні

вільні змінні

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

750

5

2

1

0

0

2

Х4

807

4

5

0

1

0

3

Х5

840

1

7

0

0

1

4

F

0

-30

-49

0

0

0

На перетині дозволяє стовпця і рядка знаходиться дозволяє елемент - це число 7. Виробляємо перерахунок всіх коефіцієнтів таблиці, таким чином, щоб на місці дозволяє елемента отримати 1, а в дозвільному стовпці всі елементи = 0.

Для цього: 1) Третій рядок розділимо на 7, в результаті отримаємо на місці дозволяє елемента 1.

2) Третій рядок помножимо на 2 і з першого рядка віднімемо те, що вийшло при множенні. Результат записуємо в перший рядок.

3) Третій рядок домножимо на 5 і з другого рядка віднімемо те, що вийшло при множенні. Результат записуємо у другому рядку.

4) Третій рядок помножимо на 49 і додамо до рядка F.

При перерахунку у нас в стовпчику F, таблиці (2.2), знову виявилося негативне число, а це говорить про те що рішення потрібно продовжувати.

Далі, що дозволяє стовпцем у нас буде Х1, т.к негативне число -23 знаходиться в ньому.

Визначаємо вектор, що підлягає виключенню з базису і вибираємо роздільну рядок. Для цього знаходимо:

Х1 = min ; ; = 63.

знайшовши число = 63, => 2-й рядок (Х4) є роздільною. Отже, в базис введемо Х1 замість Х4.

Запишемо всі розрахунки в таблицю

Таблиця (2.2)

базисні змінні

вільні змінні

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

510

33/7

0

1

0

-2/7

2

Х4

207

23/7

0

0

1

-5/7

3

Х2

120

1/7

1

0

0

1/7

4

F

5880

-23

0

0

0

7

На перетині дозволяє стовпця і рядка знаходиться дозволяє елемент - це число 23/7. Виробляємо перерахунок всіх коефіцієнтів таблиці, таким чином, щоб на місці дозволяє елемента отримати 1, а в дозвільному стовпці всі елементи = 0.

Для цього: 1) Третій рядок розділимо на і запишемо вийшло в цю ж рядок.

2) З першого рядка віднімемо другу, помножену на і записуємо в перший рядок.

3) З третього рядка віднімемо другу помножену на , Результат запишемо в третій рядок.

4) До рядку F додамо другий рядок помножену на 23 і запишемо в рядок F.

Таблиця (2.3)

базисні змінні

вільні змінні

1

2

3

4

5

Х1

Х2

Х3

Х4

Х5

1

Х3

213

0

0

1

-33/23

119/161

2

Х1

63

1

0

0

7/23

-5/23

3

Х2

111

0

1

0

-1/23

28/161

4

F

7329

0

0

0

7

2

Відповідь: з викладеного вище економічного змісту даних таблиці (2.3) випливає, що на другому кроці план завдання є оптимальним. Х1 * = 63; Х2 * = 111. Fmаx = 7329, це означає, що загальна вартість всієї виробленої продукції, а вона дорівнює 7329 рублів, є максимальною

Рішення завдання двоїстим методом

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

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

5х1 + 2Х2 ≤ 750 Y1

(1.1)

4х1 + 5 Х2 ≤ 807 Y2

Х1 + 7х2 ≤ 840 Y3

F = 30Х₁ + 49Х₂ => max

Цільова функція вихідної задачі задається на максимум, а цільова функція двоїстої - на мінімум.

Складемо матрицю для вихідної завдання:

А =

Щоб скласти матрицю для двоїстої задачі потрібно застосувати транспонування (тобто заміна рядків - стовпцями, а стовпців - стоками)

АТ =

Число змінних в двоїстої задачі дорівнює числу співвідношень в системі (1.1) вихідної задачі, тобто дорівнює трьом.

Коефіцієнтами в цільової функції двоїстої задачі є вільні члени системи рівнянь, т .е 750,807,840.

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


Z (Y) = 750Y1 + 807Y2 + 840Y3 => min.

5Y1 + 4Y2 + Y3 ≥ 30

2Y1 + 5Y2 + 7Y3 ≥ 49

Y1 = 0

Y2 = 7

Y3 = 2

Z (Y) = 750 · 0 + 807 · 7 + 840 · 2 = 7329

Відповідь: Z (Y) = F (Х) = 7329, Y1 * = 0, Y2 * = 7, Y3 * = 2.

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

Під назвою «транспортна задача» об'єднується широке коло завдань з єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення.

завдання №2

Формулювання транспортної задачі

На три бази: А₁, А₂, А₃ надійшов однорідний вантаж в кількостях: а₁, а₂, а₃, відповідно. Вантаж потрібно перевезти в п'ять пунктів: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.

Спланувати перевезення так, щоб загальна їх вартість була мінімальною. Матриця тарифів сij перевезень між пунктами відправлення та пунктами призначення, а також запаси і потреби представлені нижче:


Пункт відправки

В₁

В₂

В₃

В₄

В₅

Запаси, а i

А₁

2

4

5

11

3

400

А₂

12

8

6

14

11

370

А₃

10

15

7

9

18

380

Потреби, bj

250

200

290

260

150

1150

Вихідні дані транспортної задачі зазвичай записуються в таблиці:

Для розв'язання транспортної задачі необхідно і достатньо, щоб запаси вантажу в пунктах відправлення були рівні потребам у вантажі в пунктах призначення. Перевіряємо виконання необхідного і достатнього умови розв'язання задачі. Знаходимо сумарні запаси постачальників і запити споживачів: 400 + 370 + 380 = 1150, 250 + 200 + 290 + 260 + 150 = 1150. => завдання з правильним балансом. Складаємо початкове опорне рішення:

Таблиця (1; 1)

250

200

290

260

150

V1

V2

V3

V4

V5

400

U1

2502

04

5

11

150 3

370

U2

12

+

808

-

2906

14

11

380

U3

10

__

120 15

+

* 7

2609

18

Оскільки n + m - 1 = 3 + 5 - 1 = 7, а в нашому завданні заповнених клітин всього 6, введемо додаткове число - нуль, на перетині U1 і V2.

Отримуємо рішення:

X1 = - Опорне рішення №1.

Обчислюємо значення цільової функції на цьому опорному вирішенні F = 250 · 2 + 150 · 3 + 80 · 8 + 290 · 6 + 120 · 15 + 260 · 9 = 500 + 450 + 640 + 1740 + 1800 + 2340 = 7470.

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

Ui + Vj = Сij

Записуємо систему рівнянь для знаходження потенціалів:

U1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V2 = 15,

U3 + V4 = 9

Далі одному з потенціалів задаємо значення довільно: нехай U1 = 0. Решта потенціали знаходяться однозначно:

U1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

U3 = 15 - V2 = 11

V4 = 9 - U3 = -2

V3 = 6 - U2 = 2

Перевіряємо опорне рішення Х1 на оптимальність. З цією метою обчислюємо оцінки для всіх незаповнених клітин таблиці.

Δ13 = U1 + V3 - С13 = 0 + 2 - 5 = - 3,

Δ14 = U1 + V4 - С14 = 0 - 2 -11 = - 13,

Δ21 = U2 + V1 - С21 = 4 + 2 - 12 = - 6,

Δ24 = U2 + V4 - С24 = 4 - 2 - 14 = - 12,

Δ25 = U2 + V5 - С25 = 4 + 3 - 11 = - 4,

Δ31 = U3 + V1 - С31 = 11 + 2 - 10 = 3,

Δ33 = U3 + V3 - С33 = 11 + 2 - 7 = 6,

Δ35 = U3 + V5 - С35 = 11 + 3 - 18 = - 4.

Початкове опорне рішення не є оптимальним, тому що є позитивні оцінки.

Переходимо до нового опорного рішення. Знаходимо клітинку таблиці, якій відповідає найбільша позитивна оцінка:

max {3, 6} = 6 - для клітини (U3; V3).

Для цієї клітини будуємо цикл.

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

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

Це переміщення виробляють за такими правилами:

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

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

Описаний вище перехід від одного опорного плану транспортної задачі до іншого називається зрушенням по циклу перерахунку.

250

200

290

260

150

V1

V2

V3

V4

V5

400

U1

2502

04

5

11

150 3

370

U2

12

2008

1706

14

11

380

U3

10

15

1207

2609

18

Слід зазначити, що при зсуві по циклу перерахунку число зайнятих клітин залишається незмінним, а саме залишається рівним n + m - 1 = 3 + 5 - 1 = 7

X2 = - Опорне рішення №2. Отриманий новий опорний план перевіряємо на оптимальність.

Обчислюємо значення цільової функції на другому опорному вирішенні:

F = 250 · 2 + 0 · 4 + 150 · 3 + 200 · 8 + 170 · 6 + 120 · 7 + 260 · 9 = 500 + 0 + 450 + 1600 + 1020 + 840 + 2340 = 6750.

Далі виробляємо перевірку оптимальності опорного рішення:


U1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V4 = 9.


U1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

V3 = 6 - U2 = 2

U3 = 7 - V3 = 5

V4 = 9 - U3 = 4

Перевіряємо опорне рішення Х2 на оптимальність. З цією метою обчислюємо оцінки для всіх незаповнених клітин таблиці.

Δ13 = U1 + V3 - С13 = 0 + 2 - 5 = - 3,

Δ14 = U1 + V4 - С14 = 0 + 4 -11 = - 7,

Δ21 = U2 + V1 - С21 = 4 + 2 - 12 = - 6,

Δ24 = U2 + V4 - С24 = 4 + 4 - 14 = - 6,

Δ25 = U2 + V5 - С25 = 4 + 3 - 11 = - 4,

Δ31 = U3 + V1 - С31 = 5 + 2 - 10 = - 3,

Δ35 = U3 + V5 - С35 = 5 + 4 - 18 = - 9.

Відповідь: загальна мінімальна вартість перевезень дорівнює F min = 6750ден.ед при вирішенні


Х2 = .


висновок

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

Для досягнення поставленої мети були використані різні джерела літератури. На практиці розглянуто рішення задачі заданими методами і вирішена транспортна задача.

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


бібліографічний список

1. Абрамов Л.M., Капустін В.Ф. Математичне програмування. -Л., 1981.

2. Акуліч І.Л. Математичне програмування в прикладах і завданнях. - М .: Вища школа, 1986.

3. Баумоль У. Економічна теорія і дослідження операцій. - М .: Прогрес, 1965.

4. Каліхман І.Л. Лінійна алгебра та програмування. - М .: Вища. шк., 1967.

5. Карасьов А.І., Аксютина З.М., Савельєва Т.І. Курс вищої математики для економічних вузів. Ч.II. Теорія ймовірностей і математична програмування. Лінійне програмування: Учеб. посібник для студентів вузів. - М .: Вища. школа, 1982.

6. Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. - М .: Вища. шк., 1980.

7. Лінійне програмування: Навчально-методичний посібник. - М .: Изд-во МГУ, 1992.

8. Матвєєв В.І., Сагитов Р.В., Шершнев В.Г. Курс лінійного програмування для економістів: Учеб. допомога. - М .: Менеджер, 1998..

9. Муртаф Б. Сучасне лінійне програмування. - М .: Світ, 1984.

10. Загальний курс вищої математики для економістів: Підручник / За ред. В.І. Єрмакова. - М .: інфа-М, 2002.