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

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

31

МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

«УКРАЇНСЬКИЙ ДЕРЖАВНИЙ ХІМІКО-ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ»

Економічний факультет

Кафедра маркетингу

КУРСОВА РОБОТА

на тему «Економічні задачі лінійного програмування і методи їх вирішення»

з дисципліни «Економічна кібернетика»

Виконала

Братута А.В.

Дніпропетровськ 2010

ЗМІСТ

ВСТУП

1. Теоретичний розділ

1.1 Теоретичні основи лінійного програмування

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

1.2.1 Задача оптимального виробничого планування

1.2.2 Задача про суміші

1.2.3 Задача про розкрій

1.2.4 Транспортна задача

2. Моделювання і методика рішення задач лінійного програмування

2.1 Різновиди форм моделі задач лінійного програмування

2.1.1 Загальна форма моделі

2.1.2 Стандартна форма моделі

2.1.3 Канонічна форма моделі

2.2 Симплекс-метод

3. Прикладний розділ

3.1 Вирішення задачі лінійного програмування симплекс-методом

3.2 Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі Microsoft Office Excel 2003

ВИСНОВКИ

СПИСОК ЛІТЕРАТУРИ

Вступ

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

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

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

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

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

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

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

4. Постановка завдання і формування оптимізаційної моделі.

5. Розрахунок і аналіз результатів оптимізації прибутку.

6. Розробка комп'ютерної програми для вирішення поставленої задачі.

1. ТЕОРЕТИЧНИЙ РОЗДІЛ

1.1 ТЕОРЕТИЧНІ ОСНОВИ лінійного програмування

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

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

Вперше постановка задачі лінійного програмування у вигляді пропозиції щодо складання оптимального плану перевезень, що дозволяє мінімізувати сумарний пробіг, дана в роботі радянського математика А.Н. Толстого (1930). У 1931 р. угорський математик Б. Егерварі розглянув математичну постановку і вирішив завдання, що має назву «проблема вибору», метод вирішення якої отримав назву угорський метод. У 1939 р. радянський учений Л.В. Канторович вказав загальний метод (метод розв'язувальних множників) вирішення завдань, пов'язаних зі складанням оптимального плану при організації виробничих процесів (у зв'язку з вирішенням задачі оптимального розподілу роботи між верстатами фанерного тресту в Ленінграді). Він же спільно з М.К. Гавуріним в 1949 р. розробив метод потенціалів, який використовується при вирішенні транспортних задач. У наступних роботах Л.В. Канторовича, М.М. Моісеєва, В.С. Немчинова, В.В. Новожилова, А.Л. Лур'є, О.Г. Аганбегяна, Є. Г. Гольдштейна, Д.Б. Юдіна та інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем.

У 1949 р. американським математиком Дж. Данцигом (GB Dantzig) був опублікований симплекс-метод основний метод рішення задач лінійного програмування. Термін «лінійне програмування» вперше з'явився в 1951 р. в роботах Дж. Данцига і Т. Купманса.

При всьому різноманітті змісту конкретних завдань рішення кожної задачі проходить послідовно наступні основні етапи:

1. Постановка завдання.

2. Побудова (складання) математичної моделі.

3. Вибір методу рішення і рішення задачі.

4. Перевірка отриманого рішення на його адекватність досліджуваного явища і коректування моделі у разі потреби.

5. Реалізація знайденого рішення на практиці.

Зупинимося докладніше на другому етапі.

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

У побудові математичної моделі можна виділити наступні моменти:

1. Вибір невідомих величин Х = (х1, ..., хn), впливаючи на які можна змінювати поведінку досліджуваного процесу. Їх називають змінними, керованими параметрами, планом, стратегією.

2. Необхідно виділити мету (максимізація прибутку, мінімізація витрат та інше) функціонування досліджуваного процесу і записати її у вигляді математичної функції від обраних змінних. Така функція називається цільовою (функція мети, критерій оптимальності, критерій якості, показник ефективності) і дозволяє, змінюючи значення керованих параметрів x1, ..., xn, вибрати найкращий варіант з безлічі можливих. Будемо позначати функцію мети Z = f (X).

3. Запис у вигляді математичних співвідношень (рівнянь, нерівностей) умов, що накладаються на змінні. Ці співвідношення називають обмеженнями, вони можуть витікати, наприклад, через обмеженість ресурсів. Сукупність усіх обмежень складає область допустимих рішень (ОДР). Будемо позначати її буквою D (XD) [14].

За таких позначень модель задачі математичного програмування буде мати вид:

Або в розгорнутому виді

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

при обмеженнях:

З економічних або фізичних міркувань на деякі компоненти плану завдання, як правило, накладаються умови невід'ємності:

1.2 ПРИКЛАДИ ЕКОНОМІЧНИХ ЗАДАЧ лінійного програмування

1.2.1 Задача оптимального виробничого планування

Для виготовлення n видів продукції P1, ..., Pn використовується m видів сировини S1, ..., Sm, запаси якого обмежені і становлять відповідно b1, ..., bm одиниць. Відомо, що на виробництво одиниці продукції Pj (j =) витрачається аij одиниць ресурсу Si (i =, а прибуток від реалізації одиниці продукції Pj (j=) становить сj (j =.)

Потрібно визначити план виробництва, який дозволяє при готівкових ресурсах отримати максимальний прибуток підприємства від реалізації продукції [15].

Перш за все, запишемо умови задачі компактно у вигляді таблиці:

Таблиця 1.

Складемо математичну модель задачі.

Позначимо через xj (j =) плановане до випуску кількість продукції Рj (j=), а через Z (х1, ..., xn) - прибуток підприємства від реалізації всієї продукції. Тоді планом виробництва буде вектор Х = (х1, ..., хn), що показує, яку кількість продукції кожного виду буде вироблено. Змінні х1, ..., хn - керовані змінні. Мета рішення задачі (критерій оптимальності) - максимізувати прибуток:

Z = c1x1 + c2x2 +. . . + cnxn .

Сумарні витрати ресурсу Si (i = складають:

.

У силу обмеженості ресурсу Si величиною bi отримаємо систему обмежень:

.

На змінні хj повинна бути накладена умова невід'ємності

тобто продукція Рj або може випускатися (xj > 0), або не випускатися (xj = 0).

Отже, математична модель буде мати вид:

,

.

1.2.2 Задача про суміші

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

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

Потрібно забрати суміш із заданими властивостями при найменших витратах на вихідні сировинні матеріали.

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

Таблиця 2.

Позначимо через хi кількість сировини і-го виду, що входить у склад суміші.

Мета завдання (цільова функція) - мінімізувати сумарні витрати на сировину:

Система обмежень включає в себе обмеження за технічними характеристиками:

а також обмеження за обсягом сировини, які з урахуванням невід'ємності будуть мати вид:

Запишемо модель у компактній формі:

при обмеженнях:

1.2.3 Задача про розкрій

Задача оптимального розкрою матеріалів полягає у визначенні найбільш раціонального способу розкрою наявного матеріалу (колоди, сталеві смуги, шкіра і т.д.), при якому буде виготовлено найбільшу кількість готових виробів у заданому асортименті чи буде досягнуто найменшу кількість відходів. Нехай на обробку поступає a одиниць сировинного матеріалу одного виду (наприклад, a колод однієї довжини). З нього потрібно виготовити комплекти, в кожен з яких входить n видів виробів у кількості, пропорційній числах. Є m способів розкрою (обробки) даного матеріалу, тобто відомі величини визначають кількість одиниць j-х виробів при i-му способі розкрою одиниці сировинного матеріалу [10].

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

Таблиця 3.

Нехай - кількість одиниць сировинного матеріалу, розкроюється i-м варіантом ( .

Тоді кількість виробів 1-го виду одно:

.

Беручи до уваги умову комплектності, маємо:

де y - кількість комплектів.

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

Очевидно, що

(на розкрій надходить a одиниць сировинного матеріалу), а також

Мета задачі - максимізувати кількість комплектів:

.

Отже, приходимо до математичної моделі задачі про розкроєння:

,

.

Щоб виразити цільову функцію через змінні x1,…,xm, достатньо скористуватися будь-яким із співвідношень:

1.2.4 Транспортна задача

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

Нехай є m пунктів виробництва однорідного продукту (видобуток руди в кар'єрах, виробництво автобусів, кондитерських виробів, комп'ютерів і т.д.) і n пунктів споживання цього продукту. Потужності пунктів виробництва складають аi одиниць однорідного продукту, а потреби кожного j-го пункту споживання рівні одиниці. Відомі витрати на перевезення одиниці продукту від i-го постачальника j-му споживачеві. Скласти такий план перевезень, при якому сумарні витрати на всі перевезення були б найменшими. Нехай попит і пропозиція збігаються, тобто Таку транспортну задачу називають збалансованою (закритою). При цьому передбачається, що вся продукція від постачальників буде вивезена і попит кожного із споживачів буде задоволений [7]. Складемо математичну модель задачі. кількістьПозначимо через продукту, що перевозиться з i-го пункту виробництва в j-й пункт споживання. Тоді матриця:

план перевезень.

Матрицю називають матрицею витрат (тарифів).

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

Таблиця 4.

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

Яку необхідно мінімізувати при обмеженнях:

(весь продукт із кожного i-го пункту повинен бути вивезений повністю),

(попит кожного j-госпоживача повинен бути повністю задоволений).

Із умови задачі виходить, что всі

Отже, математична модель сбалансованої транспортної задачі має вид:

при обмеженнях:

.

2. Моделювання і методика рішення задач лінійного програмування

2.1 Різновиди форм моделі задач лінійного програмування

Якщо ввести у розгляд матрицю:

і вектори:

, , ,

то стандартна форма моделі матиме вид:

Задачу ЛП в стандартній формі зручно вирішувати графічним методом, якщо число змінних дорівнює двом () [1].

де X = (x1, …, xn) -- вектор змінних,

C = (c1, …., cn), B = (b1, …, bm)T,

Aj = (a1j, …, amj)T, j = 1, …, n -- задані вектори,

T -- знак транспонування, та

відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану -- . Тоді

, (1)

, (2)

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

, (3)

, (4)

де xij коефіцієнт розкладання. Система умов

, (5)

zk ? 0, xj = 0, j = m + 1, …, n, j ? k (6)

при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому променю дорівнює и, тоді значення базисних змінних дорівнюють xi(и). В цих позначеннях рівняння (5) можна представити в виді

. (7)

помноживши рівняння (3) на и при j = k та віднявши від рівняння (1), отримаємо

. (8)

Із рівнянь (7-8) отримаємо

. (9)

Оскільки xi(и) при и = 0 визначають план задачі, то найбільше и, яке не порушує обмеження xi (и) ? 0, визначається із умови

. (10)

де I = xik > 0.

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та и > 0. Значення лінійної форми при и = и0 визначається із рівнянь (9), (4), (2)

,

де Дk = zk -- ck. Очевидно, Дj = 0 для j = 1, …, m.

Нехай -- початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

1. знайти Дk = minjДj. Якщо Дk = 0, тоді план, який розглядається оптимізовано; якщо Дk < 0, вектор Ak вводиться в базис;

2. знайти и0 та l, для якого , із формули (10). Якщо I = Л -- порожня множина, лінійна форма необмежена зверху; якщо I ? Л вектор Al виводиться із базису;

3. за знайденими l, k обчислити нові значення елементів таблиці за формулами

4.

(12)

,

де та перейти до виконання операції (1) з новими значеннями всіх xij = x'ij.

Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу

,

при обмеженнях

;

,

яка містить одиничний базис, який складається із векторів An+1, …, An+m. Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі , вихідна задача не має розв'язку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0 може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi на bi + еi, де еi достатньо малі, при вдалому виборі еi не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.

3. Прикладний розділ

3.1 Вирішення задачі лінійного програмування симплекс-методом

Для розробки математичної моделі задачі позначимо:

x1 - кількість продукту А;

x2 - кількість продукту В;

Цільова функція буде мати вид:

Z=x1+2x2mах

Система обмежень:

3 x1+3 x2 <= 15 2 x1+6 x2 <= 18 4 x1<= 16 x1+2x2 <= 8 Xj>=0, j=1..2

Зведення задачі до канонічного виду: Zmax = x1+2x2 при умовах:

3x1+3x2+x3 = 15 2x1+6x2+x4 = 18 4x1+x5 = 16 x1+2x2+x6 = 8 Xj>=0, j=1..6

Таблиця 5.

Таблиця 6.

Таблиця 7.

Відповідь: Zmax =7, Xопт =(3 ; 2 ; 0 ; 0 ; 4 ; 1).

Це свідчить про те, що максимальний прибуток підприємства буде дорівнювати 7 грн., а виробництво продукції А і В складає відповідно 3 і 2 одиниці.

3.2 Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі Microsoft Office Excel 2003

«Пошук рішень» - одна із сервісних можливостей пакету Microsoft Office Excel 2003. Він представляє собою спрощений варіант симплекс-методу.

«Пошук рішень» викликається за допомогою меню «Сервіс», далі вибираємо підменю «Надстройки» і натискаємо «Пошук рішень» [12].

Методика знаходження рішення задачі за допомогою «Пошуку рішень» в Excel полягає в тому, що користувач задає основні параметри завдання (цільову функцію, систему обмежень) і змінні клітинки, яким дають деякі довільні початкові значення (одиниці). Після цього «Пошук рішень» автоматично перебирає всі можливі значення змінюваних клітинок так, щоб вони задовольняли обмеженням, а цільова функція приймала задані значення. Таким чином, порядок виконання «Пошуку рішень» такий [3]:

1. На аркуші Excel формується масив, відповідний розширеній матриці системи обмежень задачі (блок клітинок В2:С5 та Е2:Е5).

2. Виділяються клітинки, відповідні змінним завдання, яким присвоюються початкові значення, які дорівнюють одиницям (В8:С8).

3. Виділяється клітинка, в якій обчислюється значення цільової функції, яка містить посилання на клітинки змінних (у клітинку В10 вводимо формулу =1*B8+2*C8).

4. Створюється масив, відповідний лівим і правим частинам системи обмежень. Для цього з посиланням на клітинки коефіцієнтів і змінних обчислюються складові лівих частин системи обмежень, і обчислюється сума (у клітинку В12 вводимо формулу =B2*B8, у клітинку В13 вводимо =B3*$B$8 і далі тягнемо мишкою вниз ще на дві клітинки; у клітинку С12 вводимо =C2*$C$8 і тягнемо вниз; відповідно у клітинках Е12-Е15 обчислимо суму построково). Це все проілюстровано на рисунку 1.

Рис. 1.

5. Після запуску «Пошуку рішень» задається адреса цільової клітинки, спрямованість цільової функції, адреса змінюваних клітинок, система обмежень, умова невід'ємності значень змінних. Вікно «Пошуку рішень» зображено на рисунку 2.

Рис. 2.

6. У параметрах виділяється лінійна і невід'ємна моделі. Дивись рисунок 3.

Рис. 3.

7. Проводиться запуск. У випадку, якщо необхідне рішення знайдено, воно зберігається. Це вікно зображене на рисунку 4.

Рис. 4.

Остаточні результати бачимо на рисунку 5. З нього видно, що x1=3, тобто продукції виду А необхідно виготовляти у кількості 3-х одиниць, x2=2, тобто продукції виду В необхідно виготовляти у кількості 2-х одиниць, при цьому максимальне значення цільової функції буде досягати 7, тобто прибуток підприємства буде складати 7 грн.

Рис. 5.

Висновки

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

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

3. Було розроблено математичну модель поставленої задачі, тобто записана цільова функція і система обмежень, і програмне забезпечення.

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

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

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

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

СПИСОК ЛІТЕРАТУРИ

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высшая шк., 1986. -319с.

2. Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и свіязь, 1989. - 176с.

3. Белобродский А.В., Гриценко М.А. Поиск решений с Excel 2000. -Воронеж, 2001.

4. Вагнер Г. Основы исследования операций. Т.1. - М.: Издательство «Мир», 1972.

5. Вентцель Е. С. Исследование операций. Задачи, принципы, методология. - М.: Дрофа, 2004.

6. Енциклопедія кібернетики /За ред. В. Глушкова. - К.: «Українська радянська енциклопедія», 1973.

7. Зайченко Ю.П. Исследование операций. - К.: Вища шк., 1979.

8. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. - М.: «Дело и Сервис» , 1999. - 368 с.

9. Конюховский П.В. Математические методы исследования операций в экономике. - СПб.: Питер, 2000. - 208с.

10. Косоруков О.А., Мищенко А.В. Исследование операций /Под общ. ред.. Н. П. Тихомирова. - М.: «Экзамен», 2003.

11. Лотов А.В. Введение в экономико-математическое моделирование. - М.: Наука, 1984. - 391с.

12. Мур Дж., Уэдерфорд Л.Р. и др. Экономическое моделирование в Microsoft Excel. - М.: Издательский дом «Вильямс», 2004. - 1024 с.

13. Таха, Хемди А. Введение в исследование операцій: Пер. с англ. - М.: Издательский дом «Вильямс», 2005. - 912с.

14. Химмельблау. Прикладное нелинейное программирование. - М.: «Мир», 1975.

15. Шелобаев С. И. Математические методы и модели в экономике, финансах, бизнесе. - Учеб. пособие для вузов. - М.: ЮНИТИ-ДАНА, 2001. - 367с.

16. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. - М.: Наука, 1969. - 424с.