Конспект лекцій з курсу «економіко-математичне моделювання»




НазваКонспект лекцій з курсу «економіко-математичне моделювання»
Сторінка1/19
Дата конвертації03.04.2014
Розмір1.22 Mb.
ТипКонспект
skaz.com.ua > Математика > Конспект
  1   2   3   4   5   6   7   8   9   ...   19


МІНІСТЕРСТВО ОСВІТИ і НАУКИ УКРАЇНИ
ОДЕСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ ХАРЧОВИХ ТЕХНОЛОГІЙ

Кафедра КС і УБП

КОНСПЕКТ ЛЕКЦІЙ
З КУРСУ «ЕКОНОМІКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ»

Модуль1 «Лінійне програмування»

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

6.030504 «Економіка підприємства», 6.030509 «Облік і аудит»

денної й заочної форм навчання

Затверджено

Методичною радою ОНАХТ

протокол № 5 від 28.02. 2013 р.


Одеса ОНАХТ 2013

Конспект лекцій з курсу «Економіко-математичне моделювання», Модуль 1 «Лінійне програмування» для студентів напряму підготовки 6.030504 «Економіка підприємства», 6.030509 «Облік і аудит» денної та заочної форм навчання / Укладачі: Н.О. Макоєд, О.Ю. Орлова -Одеса: ОНАХТ, 2013.- 60 с.

Укладачі Н.О. Макоєд, канд. пед. наук, доцент,

О.Ю. Орлова, асистент

Відповідальний за випуск

завідувач кафедри КС і УБП Волков В.Е., канд. фіз-мат. наук, доцент .

ВСТУП

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

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

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

Поняття оптимальності й критерію зв'язані між собою. Застосування терміну "оптимальний" коректне лише при вказуванні критерію.

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

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

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

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

Основна робота з математичного програмування була написана в 1939 році радянським математиком Л.В. Канторовичем. Створення ЕОМ дало потужний поштовх розвитку математичного програмування. У теперішні часи ця область перебуває в стадії розвитку.

^ 1.РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА

1.1. Основні поняття

Система m лінійних рівнянь із n невідомими має такий вигляд:



Тут хj ( j=1, n ) – змінні ( або невідомі) системи, аij ( i =1,m; j = 1,n ) – коефіцієнти при змінних, вi ( i =1,m ) – вільні члени.

Рішенням системи ( І.І) називається всякий набір значень змінних х1, х2, …, хn, при якому всі рівняння перетворюються в тотожності. Система називається сумісною, якщо вона має хоча б одне рішення, і несумісною – у протилежному випадку.

Наприклад, система



сумісна, тому що вона має, зокрема, таке рішення:

х1 = 1; х2 = 2; х3 = 0 . Система ж

несумісна.

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

Нарешті якщо у системі є рівняння виду

0∙ х1 + 0∙ х2 + ... + 0∙ хn = 0, то таке рівняння можна вилучити, одержавши систему, рівносильну вихідній.
^ 1.2. Приведення системи лінійних рівнянь до жорданової форми
Процес відшукування рішення системи лінійних рівнянь починається з того, що система приводиться до жорданової форми.

Визначення. Жордановою формою системи (I.I) називається система лінійних рівнянь, що володіє наступними властивостями:

а) вона рівносильна системі (I.I)

б) у кожному рівнянні жорданової форми є така змінна, котра входить у це рівняння з коефіцієнтом 1, а в інші рівняння - з коефіцієнтом 0.

Так, якщо системі (I.I) рівносильна наступній системі лінійних рівнянь:
(1.2)

то (І.2) є жорданова форма для (I.I). При цьому змінні х1, х2,... ,хк називаються базисними, останні змінні хк+1,..., хn називаються вільними. Жорданова форма завжди є сумісною системою лінійних рівнянь. Дійсно, система (І.2) має наступне рішення:

(І.3)

Оскільки система (І.2) рівносильна системі ( І.І ) , то (І.3) є рішенням системи (І.І).

Таким чином, якщо для системи лінійних рівнянь ( І.І ) існує жорданова форма, то ( І.І ) - сумісна система. Несумісна система жорданової форми не має.

Покажемо, що будь-яку сумісну систему можна привести до жорданової форми. Це досягається методом Гауса-Жордана, який полягає в наступному.

Розглянемо перше рівняння системи (І.І). Виберемо в ньому змінну, коефіцієнт при якій відмінний від нуля. Припустимо, що а11 0. Поділимо рівняння на а11.

Одержимо рівняння

х1+ а12х2 + … + а1nхn = в1 (І.4)
Будемо змінну х1 робити базисною в жордановій формі. Для цього її потрібно вилучити з інших рівнянь системи. Щоб вилучити х1 із другого рівняння, помножимо рівняння (І.4) на -а21 і складемо із другим рівнянням. Потім вилучимо х1 із третього рівняння, для чого рівняння (І.4) помножимо на -а31 і складемо із третім рівнянням. Аналогічно змінна х1 вилучається з інших рівнянь. Таким чином, взявши за "ведуче" перше рівняння й провівши серію "жорданових вилучень", ми одержимо рівносильну (I.I) систему рівнянь, у якій x1 входить у перше рівняння з коефіцієнтом 1 , а в інші рівняння - з коефіцієнтом 0.

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

Якщо на деякому кроці виникне рівняння виду

0∙ х1 + 0∙ х2 + ... + 0∙ хn = 0 (І.5)

то вилучаємо його із системи. Якщо ж виникне рівняння виду

0∙ х1 + 0∙ х2 + ... + 0∙ хn = b ≠ 0, то це свідчить про несумісність вихідної системи ( І.І), а несумісна система до жорданової форми не приводиться.

Отже , метод Гауса-Жордана сумісну систему лінійних рівнянь приводить до жорданової форми, а у випадку несумісної системи виявляє несумісність.

Ясно, що в жордановій формі число рівнянь не може бути більше числа рівнянь у вихідній системі. Так, якщо система (1.2) є жордановою формою для системи (I.I), то , причому сувора нерівність має місце тоді, коли на деяких кроках жорданової процедури вилучалися рівняння виду (1.5).

Очевидно, та сама система може мати багато різних жорданових форм.
Приклад. Привести до жорданової форми



Виберемо як ведуче перше рівняння, а як базисну змінну - змінну х1. Поділимо перше рівняння на (-1) (коефіцієнт при х1), одержимо:



Помножимо це рівняння на (+5) і додамо до другого рівняння, потім помножимо його на (-3) і додамо до третього рівняння.

Одержимо систему:


Тепер зробимо ведучим друге рівняння, а базисною змінною - змінну . Поділивши друге рівняння на (-8) і виключивши з першого й третього рівнянь, одержимо систему:



Нарешті, у третьому рівнянні вибираємо за базисну змінну . Поділимо це рівняння на (-1) і виключимо з інших рівнянь. Одержимо жорданову форму:



Змінні є базисними, змінна - вільною.
^ 1.3. Поняття загального, часного й базисного рішень

.

Нехай система (І.І) представлена в жордановій формі (1.2). Виразимо базисні змінні через вільні.
(1.6)

(1.6) називається загальним рішенням системи (I.I).

Якщо вільним змінним додати будь-які числові значення й обчислити значення базисних змінних із системи (1.6), то вийде рішення вихідної системи, яке має назву часне. Часне рішення називається базисним, якщо вільні змінні приймають нульові значення. Рішення (1.3) є базисним.

У прикладі загальне рішення таке:


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



то система має єдине рішення; воно є й загальним, і часним , і базисним. Якщо ж k‹n , тобто жорданова форма містить вільні змінні, то система має нескінченно багато рішень.

^ 2. ЗАГАЛЬНІ ВЛАСТИВОСТІ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
2.І. Приклад задачі лінійного програмування - задача про використання обладнання
Підприємство випускає два види виробів А і В, для виробництва яких використовуються три типи верстатів. Відомі витрати часу (у годинах) верстатами на виробництво одиниці кожного виду виробів, резерви часу верстатів, а також прибуток від реалізації кожного виду виробу. Всі ці дані наведені в таблиці:

Таблиця 2.1.


Вироби

верстати


А


В


Резерви часу (у годинах)



I

Витрати часу на виробництво одиниці виробу (у годинах)







2

3

30

II

4

2

40

III

3

4

60

Прибуток від реалізації од. виробу


6


7








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

Це приклад оптимізаційної економічної задачі. Вирішення таких задач містить наступні етапи:

побудова економіко-математичної моделі;

вирішення отриманої математичної задачі яким-небудь математичним методом;

впровадження результату вирішення в практику.

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

Побудуємо економіко-математичну модель задачу про використання обладнання.

Нехай х1 - кількість виробів А, а - кількість виробів В, які будуть випущені підприємством. Тоді прибуток, отриманий підприємством, дорівнює , Змінні і потрібно підібрати так, щоб функція максимізувалася. Оскільки перший верстат може працювати не більше 30 годин, то повинно виконуватися співвідношення . Аналогічні обмеження на змінні х1 і х2 накладаються резервами часу другого й третього верстатів. З огляду на те, що змінні х1 і х2 можуть приймати тільки додатні значення, одержимо наступну економіко-математичну модель задачі:

max

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



^ 2.2. Задача про використання сировини
З математичної точки зору ця задача є узагальненням тієї, котра розглянута в попередньому параграфі. Формулюється вона так.

Підприємство випускає продукцію n видів , на виготовлення якої витрачається сировина m видів , запаси котрої на підприємстві дорівнюють відповідно . Відомі витрати сировини Si на виробництво одиниці продукції (i = ; j = ). Вартість одиниці продукції дорівнює (j = ). Потрібно скласти такий план випуску продукції, при якому прибуток від реалізації продукції був би найбільшим.

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

Нехай - кількість одиниць продукції (j = ).

Математична модель має вигляд:

f = → max

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

( 2.0)
^ 2.3. Задачі складання раціону (задача про дієту)
Для відгодівлі тварини використовується n видів кормів, що містять m видів поживних речовин. Нехай - вміст i- ої поживної речовини в одному кілограмі j - го виду корму - вартість одного кілограма j-ro виду корму Мінімальна добова потреба тварини в i-ої поживній речовині дорівнює . Необхідно скласти найбільш дешевий раціон потрібної поживності.

Позначимо через xj кількість кілограмів корму j-го виду.

Очевидно, математична модель задачі така.

f = → min
при обмеженнях:



^ 2.4. Загальна постановка задач лінійного програмування
Лінійним обмеженням, накладеним на змінні , називається співвідношення одного з наступних трьох типів:



де - дійсні числа.

Наприклад, співвідношення 2х - ≤ 1 або ≥ 0 є

лінійними, а співвідношення 3 або sin x1 не є лінійними.

Загальна постановка задачі лінійного програмування (ЗЛП) полягає в наступному.
Дано деяку лінійну функцію

f = n (2.1)

і деяка система лінійних обмежень, накладених на змінні :

(2.2)

Потрібно знайти такі значення змінних, які

задовольняли б обмеженням (2.2) і при цьому обертали б в оптимум (max і min) функцію (2.1).

Функція (2.1) називається цільовою. Кожний набір значень змінних, при яких задовольняються обмеження (2.2), називається припустимим рішенням або припустимим планом ЗЛП. Сукупність всіх припустимих рішень називається областю припустимих рішень (ОПР).

Наведені в параграфах 2.1, 2.2, 2.3 задачі є задачами лінійного програмування.

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

Говорять, що ЗЛП розв'язна, якщо вона має оптимальний план. У протилежному випадку задача називається нерозв'язною.

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

а) ОПР порожня;

б) ОПР непорожня, але цільова функція не обмежена на ОПР зверху, якщо в ЗЛП шукається її максимум, або - не обмежена знизу, якщо в ЗЛП шукається мінімум цільової функції.

Наприклад, задача: f = min

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



нерозв'язна через порожнечу ОПР.

Задача ж f = max при обмеженні

нерозв'язна через те, що цільова функція не обмежена зверху на ОПР. (Щоб переконатися в цьому, розгляньте такі припустимі рішення : і т.д.).
^ 2.5. Геометричний метод вирішення ЗЛП
У випадку, коли число змінних у ЗЛП дорівнює двом, завдання можна вирішити геометрично. Розглянемо приклади.

  1   2   3   4   5   6   7   8   9   ...   19

Схожі:

Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій вступ опорний конспект лекцій з курсу "Гроші та кредит"
Опорний конспект лекцій з курсу "Гроші та кредит" призначений для більш ефективного засвоєння студентами матеріалу цього курсу, а...
Конспект лекцій з курсу «економіко-математичне моделювання» iconНавчальна програма для вищих навчальних закладів I-II рівнів акредитації...
Предмет математики. Зв'язок математики з економікою. Економіко-математичне моделювання. Задача планування виробництва
Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій з курсу “аналітична хімія ”
Конспект лекцій до вивчення курсу «Аналітична хімія» Частина Хімічні методи аналізу для студентів напрямків хімічна технологія І...
Конспект лекцій з курсу «економіко-математичне моделювання» iconЛекція 2 17 лекція 31 тема 4 обґрунтування господарських рішень та оцінювання їх ефективності 49
Вивчення дисципліни передбачає наявність знань з наступних дисциплін: «Теорія ймовірностей та математична статистика», «Теорія статистики»,...
Конспект лекцій з курсу «економіко-математичне моделювання» iconСтислий конспект лекцій з дисципліни „ інтелектуальна власність”...
Цибульов П. М., Трибунська К. В. Інтелектуальна власність / Стислий конспект лекцій. – Донецьк.: „Донецький державний університет...
Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій з курсу "Механічна технологія текстильних матеріалів"
Конспект лекцій з курсу "Механічна технологія текстильних матеріалів" для студентів напрямку 0913 " Метрологія, стандартизація та...
Конспект лекцій з курсу «економіко-математичне моделювання» iconСистемний аналіз та математичне моделювання

Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій з дисципліни „Підприємницьке право” для студентів...
Конспект лекцій з дисципліни „Підприємницьке право” для студентів ІІ курсу денної форми навчання спеціальності „Менеджмент організації”...
Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій з курсу «Філософія» для бакалаврів усіх спеціальностей...
Конспект лекцій з курсу «Філософія» для бакалаврів усіх спеціальностей усіх форм навчання / Під загальною ред проф. Чугуєнко В. М....
Конспект лекцій з курсу «економіко-математичне моделювання» iconКонспект лекцій з курсу «політологія» для студентів усіх спеціальностей...
Конспект лекцій з курсу «Політологія» (Модуль 2) для студентів всіх спеціальностей денної І заочної форм навчання / Уклад.: А. О....
Додайте кнопку на своєму сайті:
Школьные материалы


База даних захищена авторським правом © 2015
звернутися до адміністрації
skaz.com.ua
Головна сторінка