Xreferat.com » Рефераты по информатике и программированию » Економічні задачі лінійного програмування і методи їх вирішення

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

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

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

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

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

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


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

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

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


Виконала

Братута А.В.


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

ЗМІСТ


ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі 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 (XЕкономічні задачі лінійного програмування і методи їх вирішенняD) [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.

Вид продукції

Вид сировини

Р1 ... Pj ... Pn

Запас

ресурсу

S1 a11 ... a1j ... a1n b1
... ... ... ... ... ... ...
Si ai1 ... aij ... ain bi
... ... ... ... ... ... ...
Sm am1 ... amj ... amn bm
Прибуток c1 cj cn

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

Позначимо через 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.

Вид речовини


Вид сировини

1 ... j ... n

Обсяг сировини


Ціна

сировини

1 a11 ... a1j ... a1n d1 c1
... ... ... ... ...
i ai1 ... aij ... ain di ci
... ... ... ... ...
m am1 ... amj ... amn dm cm

Мінімальна кількість речовини в суміші


b1


...


bj


...


bn




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

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


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


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

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


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


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


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


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


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


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


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

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

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


Таблиця 3.

Вид виробу

Спосіб

розкрою


1


...


j


...


n

1 a11 ... a1j ... a1n
... ... ... ... ...
i ai1 ... aij ... ain
... ... ... ... ...
m am1 ... amj ... amn

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

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


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


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


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


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

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


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


Очевидно, що

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


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


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


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


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


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


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

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

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


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


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


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

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

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


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


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

Матрицю Економічні задачі лінійного програмування і методи їх вирішенняназивають матрицею витрат (тарифів).

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


Таблиця 4.

bj

ai

b1 b2 ... bn
a1

c11

x11

c12

x12

...

c1n

x1n

a2

c21

x21

c22

x22

...

c2n

x2n

... ... ... ... ...
am

cm1

xm1

cm2

xm2

...

cmn

xmn


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


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


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


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


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


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


(попит кожного j-гоЕкономічні задачі лінійного програмування і методи їх вирішенняспоживача повинен бути повністю задоволений).

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


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


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


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


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


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

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


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


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


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

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

Знайти сукупність значень n змінних Економічні задачі лінійного програмування і методи їх вирішення що задовольняють системі обмежень:


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


і умові невід’ємності:


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


для яких лінійна функція (цільова функція) Економічні задачі лінійного програмування і методи їх вирішення досягає екстремуму (максимуму або мінімуму) [9].


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

Знайти сукупність значень n змінних Економічні задачі лінійного програмування і методи їх вирішення що задовольняють системі обмежень:


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


і умові невід’ємності:


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


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

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


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


і вектори:


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


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


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


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


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

Знайти сукупність значень n змінних Економічні задачі лінійного програмування і методи їх вирішення що задовольняють системі рівнянь:


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


і умові невід’ємності:


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


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

Компактна форма моделі має вид:


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

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

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


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


Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану [6].

Опишемо метод.

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:


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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

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