Поиск по базе сайта:
Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування» icon

Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»




НазваМетодичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»
Сторінка2/8
Дата конвертації02.08.2013
Розмір1.22 Mb.
ТипМетодичні вказівки
1   2   3   4   5   6   7   8
^

до виконання лабораторних робіт із дисципліни

«Економіко-математичне моделювання»

Розділ 1: «Математичне програмування»




Харків 2010


^ Міністерство освіти і науки України


Харківський державний технічний університет будівництва та архітектури


Напрям підготовки 6.030502


^

МЕТОДИЧні вКАЗівки




до виконання лабораторних робіт із дисципліни

«Економіко-математичне моделювання»

Розділ 1: «Математичне програмування»




Затверджено на засіданні

кафедри економічної кібернетики.

Протокол № 15 від 22.04.10 р.


Харків 2010

Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання». Розділ 1: «Математичне програмування» для студентів напряму підготовки 6.030502 – “Економічна кібернетика”/ Укладачі: О.О. Шаповалова, Л.А. Гнучих, О.В. Старкова, А.О. Ускова, М.О. Цибинога. – Харків: ХДТУБА, 2010. – 67 с.


Рецензент Н.Д. Сізова


^

Кафедра економічної кібернетики




ВСтуп


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

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

Більшість прикладних задач економіки, зокрема, пов’язаних з вирішенням проблем управління, результатом яких є числова інформація, можна розв’язати різними чисельними методами. Послідовність розв’язання такого роду задач складається з наступних етапів:

  • змістовна постановка задачі;

  • математичне формулювання моделі;

  • вибір методу розв’язання;

  • розв’язання задачі;

  • аналіз отриманих результатів.

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


^ ПЛАН ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ


  1. Засвоїти рекомендації щодо використання методів математичного програмування до різних класів задач.

  2. Обчислити приклади. Навести ілюстративний матеріал.

  3. Оформити звіт про лабораторну роботу, який включає висновки щодо отриманих планів розв’язку задач, опис прикладів, ілюстративний матеріал.


Лабораторна робота № 1

^ РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ГРАФІЧНИМ МЕТОДОМ


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

У результаті виконання роботи студент повинен:

ЗНАТИ правила побудови області припустимих рішень;

УМІТИ отримати розв’язок поставленої задачі графічно;

МАТИ УЯВЛЕННЯ про застосування графічного методу для розв’язання економічних задач.


За допомогою графічного методу розв’язуються задачі двох типів (дві змінних, або змінних більше, але можна виразити всі інші змінні через дві основних).

Нехай задача лінійного програмування (ЗЛП) задана у двовимірному просторі, тобто цільова функція Z залежить від двох змінних і всі обмеження містять також тільки дві змінні:


Z = c1x1 + с2х2max(min),


а11х1 + а12х2 < b1;

а21х1 + а22х2 < b2;

……………

am1x1 + аm2х2 < bm;

x1 >0; x2 >0.


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

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

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

2) записується вектор gradZ= (с1; с2). Для його побудови можна взяти точку (0; 0) за початок вектора, а точку 1; с2) – за кінець вектора. Якщо числа с1, с2 дуже великі або дуже малі (тобто незручні для побудови), то можна будувати не gradZ, а k*gradZ, де k - будь-яке додатне число. Вектор gradZ спрямований у бік найбільшого зростання функції;

3) лінії рівня функції Z - це геометричне місце точок, у яких функція Z набуває постійного значення. Якщо Z = с1х1 + с2х2, то лінії рівня - це прямі с1х12х= α, причому ці прямі перпендикулярні вектору gradZ.

Необхідно побудувати будь-яку лінію рівня й пересувати її паралельно самій собі (перпендикулярно вектору gradZ) у напрямку області припустимих розв’язків. Екстремальні точки (якщо вони існують) будуть визначатися граничними положеннями лінії рівня. Граничними положеннями лінії рівня вважають такі положення, за яких лінія рівня перетинає область припустимих розв’язків тільки лише в її граничних точках;

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

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


Приклад

Розв'язати графічно задачу лінійного програмування й пояснити процедуру визначення оптимальних (екстремальних) розв’язків:


mах z = 4х1 + 3х2


х1+3х2>6;

1+5х2<40;

-4х1+2х2<8;

-2х1+9х2>9;

х1>0; х2>0.


Розв’язання

Графічне розв'язання можливе, так як шуканий розв’язок, тобто план Х=(х12), є елементом двомірного простору R2.

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

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

х1+3х2= 6.

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


х1

х2

0

2

6

0

Для визначення множини точок, що задовольняють нерівності х1+3х2 > 6, необхідно обрати будь-яку точку координатної площини, яка не належить прямій х1+3х2=6 і підставити її координати замість відповідних змінних нерівності.

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

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

Зручною для визначення такої множини є точка з нульовими координатами – т. О (0,0). Шукану множину позначають штрихуванням у необхідний бік від прямої.

Подібний аналіз і побудову необхідно виконати для інших нерівностей системи обмежень. Для рівняння 8х1+5х2<40 визначаються точки обмежуючої півплощини прямої

х1

х2

0

8

5

0



x1=(0,8); х2=(5,0).

Для рівняння -4x1+2x2=8 точками прямої, що обмежують півплощину, є

х1

х2

0

4

-2

0



х1=(0,4); х2=(-2,0).

х1

х2

0

1

-4.5

0

Для рівняння -2x1+9х2=9 точками прямої, що обмежують півплощину, є


х1=(0,1); х2=(-4.5,0).

На рис. 1 штрихуванням виділені півплощини, описані відповідними нерівностями системи обмежень. Нерівності х1>0 і х2>0, що визначають умови невід’ємності змінних х1 та х2, описують перший квадрант двовимірної системи координат.

Шукана множина визначається в результаті застосування операції перетинання до отриманих множин. На рис. 1 шукана множина, що задає область припустимих розв’язків, виділена жирною лінією.

На наступному етапі знаходиться розташування площини, що є графіком двомірної цільової функції z=f(х12), стосовно області припустимих розв’язків. Для цього визначається лінія рівня вихідної функції при z=0; 4х1+3х2=0, для зображення цієї прямої знаходиться дві точки

х1

х2

0

0

1

-4/3



Рисунок 1 – Розв’язання ЗЛП графічним способом


На рис. 1. зображена лінія рівня – пряма Z.

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

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


1+5х2=40;

-4х1+2х2=8.


Розв’язання даної системи рівнянь дає координати, що характеризують шуканий план Х*=(х1*2*)=(1,11;6,22), який є оптимальним. Цільова функція на цьому плані досягає свого максимального значення zmax=4х1*+3х2*= =4*1,11+6*6,22=23,1.


Завдання до лабораторної роботи

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


№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 3x1 + 2x2   max





Z = 2x1 + 2x2   max





Z = 2x1 + x2   max





Z = 4x1 + 6x2   min




Z = 5x1 + 4x2   max





Z = 6x1 + 4x2   min






№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 3x1 – 3x2   max





Z = x1 + 3x2   max





Z = –x1 – x2   max





Z = 3x1 - 2x2   max





Z = –x1 + 2x2   min





Z = 3x1 – 2x2   max





Z = 5x1 + 3x2   max





Z = 2x1 – x2   max





Z = x1 + 3x2   max





Z = 5x1 + x2   max





Z = 2x1 + 3x2   min




Z = -x1 + 2x2   min





№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = -2x1 + 5x2   min





Z = 3x1 - 2x2   min




Лабораторна робота № 2

^ РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

З ВИКОРИСТАННЯМ СИМПЛЕКСНОГО МЕТОДУ


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

У результаті виконання роботи студент повинен:

ЗНАТИ правила побудови опорних планів;

УМІТИ здійснювати перехід під одного плану до іншого;

МАТИ УЯВЛЕННЯ про виконання критеріїв оптимальності.


Симплексний метод (СМ) – це метод цілеспрямованого перебору опірних розв’язків задачі лінійного програмування (ЛП).

Основний зміст симплекс-методу полягає в наступному:

  1. вказати спосіб знаходження початкового опорного розв’язку;

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

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

Для використання СМ задача ЛП повинна бути приведена до канонічного вигляду.

Приведення до канонічного вигляду загальної задачі ЛП відбувається додаванням до лівої частини обмеження додаткової змінної так, що .

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

Зауваження. У разі нерівності до лівої частини треба додавати змінну, у разі віднімати.


Приклад

Знаходження максимального значення цільової функції.



1   2   3   4   5   6   7   8



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації