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

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




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

Алгоритм розв’язання транспортної задачі методом потенціалів:


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

2 Будують початковий опорний розв’язок.

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

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

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

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

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


Приклад

Розв’язати транспортну задачу, вихідні дані якої наведені в наступній таблиці.

bj

ai

100

100

300

300

100

1


2



3


1


200

2


3


4


6


300

3


4


7


12



Розв’язання

1 Перевірка збалансованості задачі:





Задача є незбалансованою, тобто до неї необхідно додати фіктивного виробника а4=800-600=200 з нульовою вартістю перевезень.

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

Х1



















bj

ai

100

100

300

300




100

1

100


2



3


1





200

2

0


3

100


4

100


6





300

3



4


7

200

12

100




200

0



0


0


0

200

2 Після заповнення таблиці перевіряється кількість базисних комірок. m+n1=4+41=7, тобто план є базисним.

За таких обсягів перевезень загальна вартість складає: F(X1) = 100*1 +
+0*2 + 100*3 +100*4+200*7+100*12+200*0=3400 грошових одиниць.

3 За базисними комірками визначаються потенціали рядків і стовпчиків.

u1+ v1=1

u2+ v1=2

u2+ v2=3

u2+ v3=4

u3+ v3=7

u3+ v4=12

u4+ v4=0

Для визначення 8 невідомих із 7 рівнянь один з потенціалів покладається рівним 0. Нехай u1=0, тоді:

u1 =0 v1=1

u2 =1 v2=2

u3 =4 v3=3

u4 =-8 v4=8

4 Отриманий план перевіряється на оптимальність, визначаються оцінки вільних комірок, наприклад:

S12= u1+ v2-cij=0+2-2=0.

Значення оцінок записуються в лівому нижньому кутку вільних комірок. Від’ємні значення можна не вказувати, достатньо вказати знак «-».

Х1


v1=1

v2=2

v3=3

v4=8


bj

ai

100

100

300

300


u1=0

100

0

0

7

3

-

2

2

-

-

+

+

+

-

-

-

1

100


2

3


1


u2=1

200

2

0


3

100


4

100


6


u3=4

300

3


4


7

200

12

100


u4=-8

200

0


0


0


0

200

Найбільшу оцінку має комірка (1;4), тому для неї необхідно побудувати цикл.

Починаючи з вільної комірки, в циклі проставляються по черзі знаки «+» та «-». Серед комірок, що мають знак «-», обирається значення, на яке відбудеться переміщення обсягів перевезень.


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

5

Х2




v1=1

v2=2

v3=3

v4=1




bj

ai

100

100

300

300


u1=0

100

1

0

0

-

2

2

2

0

1

+

+

-

-

-

0


2



3


1

100


u2=1

200

2

100


3

100


4

0


6



u3=4

300

3



4


7

300

12



u4=-1

200

0



0


0


0

200

Обчислюються потенціали та визначаються оцінки вільних комірок, на основі чого робиться висновок, що Х2 не є оптимальним планом, бо має позитивні оцінки вільних комірок. Будується цикл для комірки (3;2):


Х3




v1=1

v2=0

v3=3

v4=1




bj

ai

100

100

300

300


u1=0

100

1

+

-

0

-

2

2

0

-

+

-

-

-

-

0


2



3


1

100


u2=1

200

2

100


3


4

100


6



u3=4

300

3



4

100


7

200

12



u4=-1


200

0



0


0


0

200

Х3 не є оптимальним планом, бо має позитивні оцінки вільних комірок. Будується цикл для комірки (3;1):


Х4


v1=1

v2=0

v3=3

v4=1


bj

ai

100

100

300

300


u1=0

100

+

-

0

-

4

-

0

1

+

-

-

-

-

-

+

1

0


2

3


1

100


u2=1

200

2


3


4

200


6


u3=4

300

3

100


4

100


7

100

12


u4=-1

200

0


0


0


0

200

Для комірки (4;3) будується цикл:


У результаті такого циклу відбувається переміщення базисного нуля.


Х5


v1=-3

v2=-2

v3=1

v4=1


bj

ai

100

100

300

300


u1=0

100

1



-
2


-

-


3


1

100


u2=3

200


-
2


-



3



-
4


-
200


6


u3=6

300

3

100


4

100


7

100

12


u4=-1

200

0


-



0


-



0

0

0

200


Оскільки всі оцінки вільних комірок є від’ємними, то розв’язок є оптимальним:

min F(X)=F(X5)= F(X4)=2300


при .


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


Визначити оптимальний план закріплення замовників до підприємств з урахуванням мінімуму сумарних витрат на виробництво та перевезення продукції, якщо відомі обсяги виробництва на трьох підприємствах: а1=360+α, а2=340-α, а3=200+2α (α – номер студента за списком). Продукція цих підприємств знаходить постійний попит у чотирьох замовників у відповідних обсягах: b1=330-α, b2=250+α, b3=120+2α, b4=160+α.

Витрати на виготовлення одиниці продукції на кожному підприємстві визначаються за наступними величинами: d1=α, d2=8+α, d3=2α.

Транспортні витрати на перевезення одиниці продукції від виробника замовнику задаються наступною матрицею:

.


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

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

МЕТОДОМ ЛАГРАНЖА


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

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

ЗНАТИ алгоритм методу Лагранжа;

УМІТИ складати функцію Лагранжа;

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


^ Задача нелінійного програмування формулюється так само, як і загальна задача оптимального програмування, тобто у вигляді (1) (3) з наступними вимогами до цільової функції й допустимої області: цільова функція f(X) = f(x1,x2,…,xn) або (і) хоча б одна з функцій

є нелінійними:

f(x1,x2,...,xn)  max(min), (1)

gi(x1,x2,...,xn) {<,=,>} bi, i = 1,m, (2)

хj >0, j = 1,n. (3)

На деякі змінні x1,x2,…, xn можуть накладатися умови невід’ємності та цілочисловості.

Задачі нелінійного програмування значно складніші ніж задачі ЛП і для них не існує загального універсального методу розв'язання (аналогічного симплексному методу).

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

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

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

max(min)Z = f(x1,x2,...,xn), (4)

gi(x1,x2,...,xn) = 0, i = 1,m, (5)

для розв'язання яких можна скористатися класичним методом оптимізації Лагранжа, або методом розв'язувальних множників. При цьому припускають, що функції f і gi (i = 1,m) безперервні разом зі своїми першими частинними похідними.

Для розв’язання задачі складають функцію Лагранжа:



L(x1,..., хп, λ1,..., λт) = f(x1,x2,...,xn) +


визначають частинні похідні цієї функції за змінним xj () і множниками Лагранжа λi ( ), прирівнюють їх до нуля й одержують систему рівнянь:




Розв'язуючи систему (6), одержують множину стаціонарних точок, у яких функція Z може мати екстремальні значення. При цьому, як правило, невідомий спосіб визначення точок глобального максимуму або мінімуму. Однак, якщо розв’язки системи знайдені, то для визначення глобального максимуму або мінімуму достатньо знайти значення функції у відповідних точках області визначення.


Приклад

Знайти умовний екстремум функції z=5х2+(у-4)2 в області х2213 за умови х+4у=8 за допомогою методу множників Лагранжа. Навести графічну ілюстрацію розв’язання задачі.


Розв’язання

Для визначення множини, що містить точки, в яких досягаються умовні екстремуми заданої нелінійної цільової функції, необхідно виконати побудову в двовимірній системі координат області х22  13 (коло з центром у початку координат радіусом ) та прямої х+4у=8.

Множину, що відшукується, складають точки прямої, що знаходяться в колі. Графіком цільової функції є параболоїд обертання, вісь обертання якого проходить через точку (0;4). Лінії рівня даної функції є еліпсом з центром у тій самій точці (рис. 3).


Рисунок 3 – Ілюстрація розв’язку задачі нелінійного програмування

Для визначення стаціонарних точок умовного екстремуму, що відшукується за методом Лагранжа, складається функція Лагранжа

L(X,)= 5х2+(у-4)2 +( х+4у-8).

Необхідні умови екстремуму функції L(X,) дають наступну систему рівнянь:

;


;


.


Перенісши в праві частини перших двох рівнянь та прирівнюючи ліві частини, можна отримати 10х=0,5(у-4). Розв’язання даного рівняння разом з третім х+4у-8=0 дасть відповідь х=-0,099 та у=2,02, тобто т.А.(-0,099;2,02). Змінну можна не визначати, бо вона відіграє допоміжну роль. Значення цільової функції zmin(-0,099;2,02)=3,95.

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

х22=13;

х+4у=8.

Знайдені точки В(х11)=(-2,48;2,62) та С(х22)=(3,4;1,15) дають можливість оцінити значення цільової функції та визначити максимальне значення функції z серед точок допустимої множини розв’язків: z(х11)=32,66 та z(х22)=65,92.

Таким чином, екстремальні значення, що визначаються в завданні, знаходяться в точках хmin=(-0,099;2,02), zmin=3,95 та хmах=(3,4;1,15), zmах =65,92.


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


Знайти умовний глобальний екстремум функції за допомогою методу множників Лагранжа. Навести графічну ілюстрацію розв’язання задачі:


  1. z = 2х2 + 3у2, якщо х + 3у = 1 при х2 + у2 ≤ 4;

  2. z = (х-5)2 + (у-2)2, якщо х + 2у = 6 при х2 + у2 ≤ 10;

  3. z = 3x2 + 2y2, якщо2х + 3у=1 при х2 + у2 ≤ 8;

  4. z = (х-3)2 + (у-5)2, якщо у - 2х = 5 при х2 + у2 ≤ 16;

  5. z = (х-4)2 + (у-3)2, якщо х + у = 3 при х2 + у2 ≤ 9;

  6. z = 2(x-l)2 + 3(y-3)2, якщо 2х + у = 3 при х2 + у2 ≤ 16;

  7. z = (х-2)2 + 2(у-3)2, якщо 3х - 2у = 4 при х2 + у2 ≤ 9;

  8. z = (х-4)2 + (у-2)2, якщо х + 2у = 5 при х2 + у2 ≤ 10;

  9. z = 2(x-l)2 + 3(y-2)2, якщо 2х + у = 5 при х2 + у2 ≤ 9;

  10. z = 2x2 + 3y2, якщо 2х + у = 4 при х2 + у2 ≤ 12;

  11. z = (х-2)2 + (у-3)2, якщо х + 3у = 2 при х2 + у2 ≤ 4;

  12. z = (х-3)2+ 2(у-1)2, якщо 2х + 3у= 1 при х2 + у2 ≤ 10;

  13. z = (x-2)2 + (y-l)2, якщо х + у = 6 при х2 + у2 ≤ 9;

  14. z = (х-3)2 + 3(у-2)2, якщо 2х + 3у = 6 при х2 + у2 ≤ 12;

  15. z= (х-4)2 + 2(у-3)2, якщо 2х + у = 6 при х2 + у2 ≤ 16;

  16. z = 2(х-2)2 + (у-3)2, якщо 3х + у = 2 при х2 + у2 ≤ 10;

  17. z = (х-3)2 + (у-5)2, якщо 3х + 2у = 6 при х2 + у2 ≤ 9;

  18. z = 3(х-2)2 + (у-4)2, якщо х + 3у = 4 при х2 + у2 ≤ 10;

  19. z = 2(х-1)2 + (у-3)2, якщо 3х + 4у = 6 при х2 + у2 ≤ 12;

  20. z = 2х2 + 3у2, якщо 3х - у = 5 при х2 + у2 ≤ 9.

Список джерел інформації


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

  2. Бугір М. Математика для економістів. – К.: Академія, 1998. – 272 с.

  3. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч.-метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.

  4. Зайченко Ю.П., Шумилова С.А. Исследование операций: Сборник задач. – К.: Высш. шк., 1999. – 239 с.

  5. Иванов С.Н., Йозер Хауншмид. Математические методы исследования операций. – Донецк: ДонГУ, 1999. – Ч. 1. – 242 с.

  6. Колихман И.Л. Сборник задач по математическому программированию. – М.: Высш. шк., 1975. – 267 с.

  7. Колодяжный В.М. Математическое программирование и элементы теории «Исследование операций»: Учебн. пособие. – Харьков: Нац. аэрокосмический ун-т «ХАИ», 2001. – 229 с.

  8. Конюховский П.В. Математические методы исследования операций. – СПб.: Питер, 2001. – 192 с.

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

  10. Конюховский П.В. Математические методы исследования операций: Пособие для подготовки к экзамену. – СПб. – М. – Х. – Минск, 2001. – 192 с.

  11. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. – 2-е изд., испр. – М.: Дело, 2001. – 688 с.

  12. Кузнецов Ю.Н. Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие. – М.: Высш. шк., 1980. – 300 с.

  13. Михайленко С.В., Свищева Е.В. Математическое программирование: Пособие для самост. изуч. дисциплины. – Х.: НУА, 2005. – 188 с.

  14. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. – М.: Финансы и статистика, 1999. – В 2-х ч., Ч.1. – 224 с.

  15. Таха Х. Введение в исследование операций / Х. Таха. – М.–СПб.–К.: Издательский дом «Вильямс», 2001. – 912 с.

  16. Холод Н.И. Пособие к решению задач по линейной алгебре и линейному программированию. – Минск: Изд. БГУ, 1971. – 176 с.

  17. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбергов и др./ под ред. В.В. Федосеева. – М.: ЮНИТИ, 2001. – 391 с.



ЗМІСТ


Вступ 3

План виконання лабораторних робіт 4

Лабораторна робота №1. Розв’язання задач лінійного програмування графічнім методом 5

^ Лабораторна робота №2. Розв’язання задач лінійного програмування з використанням симплексного методу 11

Лабораторна робота №3. Розв’язання задач лінійного
програмування з використанням симплексних таблиць 17

^ Лабораторна робота №4. Розв’язання задач лінійного програмування з використанням методу штучного базису (М-методу) 23

Лабораторна робота №5. Розв’язання задач лінійного програмування двоїстим методом 28

Лабораторна робота №6. Цілочислове математичне програмування 33

Лабораторна робота №7. Аналіз оптимальних розв’язків економічних задач на основі теорії двоїстості 38

^ Лабораторна робота №8. Розв’язання лінійних задач транспортного типу 51

Лабораторна робота №9. Розв’язання задач нелінійного програмування методом Лагранжа 61

Список джерел інформації 65

^

Навчальне видання

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







Укладачі: Шаповалова Олена Олександрівна

Гнучих Лариса Анатоліївна

Старкова Ольга Володимирівна

Ускова Анна Олексіївна

Цибинога Марина Олександрівна


Відповідальна за випуск Л.П. Шевченко


Редактор В.І. Пуцик



План 2011 р., поз. 10

Підп. до друку

Надруковано на ризографі.

Тираж 50 прим.

Формат 60х84 1.16.

Облік.-вид. арк. 3,4.

Умов. друк. арк. 3,2.

Зам. № 1926.



Папір друк. № 2.

Безкоштовно.

________________________________________________________________

ХДТУБА, 61002, Харків, вул. Сумська, 40

Підготовлено та надруковано РВВ

Харківського державного технічного університету

будівництва та архітектури
1   2   3   4   5   6   7   8



Схожі:




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