Міністерство освіти І науки україни харківська національна академія міського господарства icon

Міністерство освіти І науки україни харківська національна академія міського господарства




Скачати 425.55 Kb.
НазваМіністерство освіти І науки україни харківська національна академія міського господарства
Сторінка1/3
Дата07.06.2012
Розмір425.55 Kb.
ТипДокументи
  1   2   3


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




ХАРКІВСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ

МІСЬКОГО ГОСПОДАРСТВА

МЕТОДИЧНІ ВКАЗІВКИ

до виконання контрольної роботи курсу

«МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ»

(для студентів 2 і 3 курсів спеціальностей

7.050107 «Економіка підприємства”,

7.050106 „Облік і аудит” ФПО і ЗН)




Харків 2006

Методичні вказівки

до виконання контрольної роботи з курсу «Математичне програмування» (для студентів 2 і 3 курсів спеціальностей 7.050107 «Економіка підприємства”, 7.050106 „Облік і аудит” ФПО і ЗН). Укл. Воронкова Т.Б., Воронков О.О. Харків: ХНАМГ, 2006.- 20 с.

^





Укладачі : ст.викл. Т.Б. Воронкова, ас. О.О. Воронков





Рекомендовано кафедрою інформаційних систем і технологій в міському господарстві, протокол № 30 від 30.06.06 р.






^

ЗАГАЛЬНІ ВІДОМОСТІ


Вивчення дисципліни „Математичне програмування” передбачено освітньо-професійною програмою підготовки бакалавра за напрямками „Економіка і підприємництво” і „Менеджмент”.

Зміст дисципліни „Математичне програмування” ґрунтується на необхідності підготовки фахівців, які володіють математичними методами обґрунтування рішень з управління економічними системами.

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

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

Номер варіанта контрольної роботи вибирають за двома останніми цифрами номера залікової книжки студента. Усього варіантів - 25. Якщо дві останні цифри залікової книжки перевищують число 25, то номер варіанта визначають шляхом вирахування числа 25, 50 або 75. Наприклад, номеру залікової книжки, що закінчується цифрами 84, відповідає варіант 9. Контрольна робота повинна бути виконана в термін, призначений навчальним графіком. У кінці роботи необхідно навести літературу, якою студент користувався при виконанні контрольної роботи.

На титульному аркуші треба чітко написати назву дисципліни, варіант завдання, прізвище, ім’я та по батькові студента, вказати курс, спеціальність і факультет.


^ ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ ЗЛП


Нагадаємо визначення:

Функція

L = сjхj (1)

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

аijхj  bi; (i=1,m; j=1,n), xj  0 (2)

-- обмеженнями задачі ЛП.

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


Розглянемо приклад.

Приклад 1. Для виготовлення двох видів виробів А і В використовують три види сировини. На виробництво одиниці виробу А потрібно витратити сировини першого типу 4 кг, другого – 3 кг і третього - 3 кг, на виробництво одиниці виробу В потрібно витратити сировини першого типу 3 кг, другого – 4 кг і третього – 5 кг. Виробництво забезпечене сировиною першого типу в кількості 440 кг, другого – 393 кг, третього – 450 кг. Прибуток від реалізації одиниці готового виробу А дорівнює 6 грн., виробу В5 грн.

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

Умову задачі зведемо в таблицю.


Сировина

А

В

Запаси

S1

4

3

440

S2

3

4

393

S3

3

5

450


Позначимо число виробів ^ А, яке необхідно виготовити, х1, а виробів Вх2. Очевидно, що запаси сировини обмежені нерівностями

1+3х2  440

1+4х2  393

1+5х2  450

Прибуток від реалізації виробів А і В визначиться виразом

L = 6x1 + 5x2  max.

Таким чином, треба знайти такі х1 і х2, які задовольняють нерівностям і перетворюють у максимум цільову функцію L.

Будемо зображувати пару значень змінних точкою з координатами x1, x2 (рис. 1). Оскільки змінні х1, х2 повинні бути більше нуля, припустимі їхні значення лежать тільки вище осі Ох1, (на якій х2 = 0) і правіше осі Ох2 (на якій х1 =0). Це відзначимо штрихуванням, що позначає «припустиму» сторону кожної осі.

Тепер побудуємо на площині х12 область припустимих рішень або переконаємося, що її не існує. Рішенням кожної нерівності є на півплощина, що обмежує область припустимих рішень задачі. Покладемо в першому рівнянні х1 = 0, отримаємо рівняння прямої лінії, перша точка якої


2 = 440, х2 = 440 / 3 = 147 має координати (0, 147),


друга точка 1 = 440, х1 = 440 / 4 = 110 має координати (110, 0).

Аналогічно отримаємо координати точок для другого обмеження (131, 0) і

(0; 98,25) і для третього обмеження (150, 0) і (0, 90).





Отримана область є областю припустимих рішень, тобто будь-яка точка області задовольняє нерівностям-умовам, і називається припустимим планом. Зазначимо, що цих рішень - нескінченна множина, тому що будь-яка пара значень вільних перемінних, узята з ОДР, «підходить».

Очевидно, що цільова функція L обертається в максимум в одній з вершин отриманого многокутника. Для визначення цієї вершини геометричним методом побудуємо градієнт цільової функції вектор grad L = с{6,5}. Далі побудуємо лінію рівня, що відповідає L = 0; вона проходить через початок координат і перпендикулярна до вектора с. Назвемо її опорною прямою. Нагадаємо, що лінією рівня функції називається множина точок з її області визначення, в яких функція приймає те саме фіксоване значення. Градієнтом функції називається вектор, що вказує напрямок, в якому функція найбільш швидко зростає. Переміщуючи опорну пряму в напрямку вектора с={6,5}, бачимо, що найбільш віддаленою вершиною многокутника є вершина А, в якій перетинаються нерівності 1 і 2. Визначимо її координати:

.

Таким чином, для одержання максимального прибутку необхідно випустити 83 вироби А і 36 виробів В. Цільова функція при цьому досягне значення


Lmax = 6 * 83 + 5 * 36 = 498 + 180 = 678 грн.

^ СИМПЛЕКСНИЙ МЕТОД

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

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


^ КАНОНІЧНА ФОРМА ЗЛП

    Канонічною називається задача ЛП, що перебуває у встановленні екстремального значення функції

    L = сjхj (3)

    при виконанні умов

    аijхij = bi і xj  0. (4)

Будь-яку задачу лінійного програмування можна звести до форми канонічної задачі (КЗЛП).

По-перше, не принципово, що треба шукати для цільової функції – максимум або мінімум. Випадок, коли ^ L треба перетворити в максимум, легко зводиться до знаходження мінімуму, якщо змінити знак L на зворотний (мінімізувати не L, a L'= —L), тому що

min f(x1, x2,…,xn) =max[-f(x1, x2,…,xn)]... (8)

і навпаки.

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

Приклад 2. Розглянемо умову попереднього прикладу:

Знайти такі х1 і х2, що задовольняють нерівностям

1+3х2  440

1+4х2  393

1+5х2  450

і перетворюють у максимум цільову функцію L :

L = 6x1 + 5x2  max.

Приведемо задачу до канонічної форми. Для цього від системи нерівностей перейдемо до системи рівностей і отримаємо систему обмежень у вигляді рівностей:

1+3х23 = 440,

1+4х2 + х4 = 393,

1+5х2 + х5 = 450.

Отримана система рівнянь містить три рівності (m = 3) і п'ять невідомих (n = 5), тобто m < n. Нагадаємо ряд теоретичних положень.

Якщо m рівностей (4) є лінійно незалежними, то систему з m лінійно незалежних рівностей з n змінними (m < n) завжди можна розв'язати відносно m змінних, називаних базисними, виразивши їх через інші k=n- m змінних, називаних вільними. Вільним змінним можна надавати будь-які значення, не порушуючи умову (4).

План КЗЛП x=(x1, x2,…, xn) називається базисним планом задачі, якщо його компоненти, що відповідають базисним стовпцям, більше нуля (xj  0), а всі інші компоненти (не базисні) – дорівнюють нулю.

Нагадаємо основні теореми лінійного програмування.

Теорема 1. Якщо цільова функція L приймає максимальне значення в деякій точці ОДР, то вона приймає це значення і в деякій кутовій точці ОДР.

Теорема 2. Кожен припустимий базисний план є кутовою точкою ОДР.

Справедливе й зворотне ствердження: якщо план x=(x1, x2,…, xn) є кутовою точкою ОДР, то він є припустимим базисним планом задачі.


^ АЛГОРИТМ СИМПЛЕКСНОГО МЕТОДУ

  1. Визначити припустимий базисний план.

  2. Скласти симплексну таблицю.

  3. Перевірити план на оптимальність. Для цього визначити

Lj = cj*aij і оцінки векторів j = Lj – cj.

Опорний план оптимальний, якщо всі j  0, інакше задача не має розв'язання або треба перейти до нового опорного плану.

  1. Щоб знайти новий опорний план, треба визначити напрямні рядок і стовпець таблиці. У базис вводять вектор, для якого добуток j *j найбільший за абсолютною величиною, де j – найменше відношення вільних членів до позитивних коефіцієнтів вектора, що вводиться в базис:

= min (bi / aij).

  1. Визначити коефіцієнти нового опорного плану (коефіцієнти розкладання векторів Aj по векторах нового базису).

  2. Перевірити новий опорний план на оптимальність.


Приклад 3. Повернемося до задачі, умову якої приведено до канонічної форми в прикладі 2. Система обмежень задачі являє собою систему з 3 рівнянь (m=3) з 5 невідомими (n=5). Така система має нескінченну множину рішень.

У системі, де m < n, m векторівAj лінійно незалежні. Розв'язання x = (x1, x2, …, xn), залежне від будь-яких m лінійно незалежних векторів, називається базисним розв'язанням системи (у нашому випадку базис становлять m = 3 елементи рішення, не рівні нулю, а інші 2 елементи рішення дорівнюють нулю).

Додатне базисне рішення називається опорним планом.

Очевидно, що одним з рішень системи є

x = (0, 0, 440, 393, 450).

Такий план відповідає тому, що вироби А і В не випускаються і L = 0.

Складемо симплекс-таблицю.


Базис

Сбаз

Сj

6

5

0

0

0

P0

A1

A2

A3

A4

A5

A3

0

440




3

1

0

0

A4

0

393

3

4

0

1

0

A5

0

450

3

5

0

0

1




Lj

0

0

0

0

0

0




j







-5

0

0

0


Визначимо Lj = cj*aij.:

L1 = 4*0 + 3*0 + 3*0 = 0;

L2 = 3*0 + 4*0 + 5*0 = 0; …...

Визначимо j = Lj – cj.:

1 = 0 – 6 = -6;

2 = 0 – 5 = - 5;

3 = 0 – 0 = 0 …

Оскільки 1 і 2  0, план не оптимальний. Перейдемо до нового опорного плану.

Визначимо вектор, який будемо вводити в базис (A1 або A2). Це повинен бути вектор, для якого добуток j *j найбільший.

Знайдемо j для A1:

1 = min (bi / aij) = min (440/4; 393/3; 450/3) = min(110; 131; 150) = 110.

Визначимо j для A2:

2 = min (bi / aij) = min (440/3; 393/4; 450/5) = min(146,6; 98,2; 90) = 90.

Визначимо добутки. Для A1 1 *1 = 6 * 110 = 660. Для A2 2 *2 = = 5 * 90= 450. Найбільший дорівнює 660, таким чином будемо вводити в базис вектор A1.

З базису слід виводити вектор, якому відповідає найменше відношення вільних членів до позитивних коефіцієнтів вектора, що вводиться в базис. Для A1 1 = 110, що відповідає першому рядку таблиці. Виводимо вектор A3.

Складемо нову симплекс-таблицю.

Базис

Сбаз

Сj

6

5

0

0

0

P0

A1

A2

A3

A4

A5

A1

6

110

1

3/4

1/4

0

0

A4

0

63

0

7/4

-3/4

1

0

A5

0

120

0

11/4

-3/4

0

1




Lj

660

6

18/4

6/4

0

0




j




0

-2/4

6/4

0

0


Вектор, що вводиться в базис, повинен мати коефіцієнти 1, 0 , 0. Для одержання 1 у головному рядку нової таблиці розділимо всі коефіцієнти рядка, що відповідає виведеному вектору A3 , на 4. Щоб другий елемент вектора A1 дорівнював 0 (рядок, що відповідає вектору A4, дістаємо з його ж рядка в попередній таблиці), помножимо головний рядок нової таблиці на мінус 3 і складемо з другим рядком попередньої таблиці:

-330

–3

-9/4

-3/4

–0

-0

393

+3

+4

+0

+1

+0 ;

+63

+0

+7/4

-3/4

+1

+0




































-330

–3

-9/4

-3/4

–0

-0

450

+3

+5

+0

+0

+1 .

+120

+0

+11/4

-3/4

+0

+1


Третій рядок нової таблиці отримаємо аналогічно.

Таким чином отримуємо новий опорний план:

х = (110; 0; 0; 63; 120),

при якому функція цілі

L = 6*110 + 5*0 = 660 – стала більше.

Перевіримо план на оптимальність, для чого знайдемо

Lj = cj*ai і j = Lj – cj..

Оскільки 2= -2/4  0, план не оптимальний.

Перейдемо до нового опорного плану. Для цього введемо в базис вектор A2, тому що для нього 2= -2/4  0.

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

1 = min (bi / aij) = min (110/3; 252/7; 480/11) = min(146,7; 36; 44) = 36.

Виводимо вектор A4.


Складемо нову таблицю.

Базис

Сбаз

Сj

6

5

0

0

0

P0

A1

A2

A3

A4

A5

A2

5

36

0

1

-3/7

4/7

0

A5

0

21

0

0

11/28

-44/28

1

A1

6

83

1

0

16/28

-12/28

0




Lj

678

6

5

9/7

2/7

0




j




0

0

9/7

2/7

0

Вектор, що вводиться в базис, повинен мати коефіцієнти 1, 0 , 0. Для одержання 1 у головному рядку нової таблиці розділимо всі коефіцієнти рядка, що відповідає виведеному вектору A4 на 7/4. Щоб другий елемент вектора A2 дорівнював 0 (рядок, що відповідає вектору A5, отримуємо з його ж рядка в попередній таблиці), помножимо головний рядок нової таблиці на –11/4 і складемо з третім рядком попередньої таблиці. Для рядка, що відповідає A1, головний рядок помножимо на мінус ѕ:


-99

+0

-11/4

+33/28

–44/28

+0

120

+0

+11/4

-3/4

+0

+1 ;

+21

+0

+0

+11/28

-44/28

+1




-27

+0

-3/4

+9/28

–12/28

+0

110

+1

+3/4

+1/4

+0

+0 .

+83

+1

+0

16/28

-12/28

+0


Отримано новий опорний план:

х = (83; 36; 0; 0; 21),

при якому функція цілі L = 6*83 + 5*36 = 678 – стала більше. Це свідчить про те, що з кожним кроком ми наближаємося до оптимального рішення, тобто поліпшуємо план.

Перевіримо новий план на оптимальність, визначивши оцінки оптимальності j.

Всі j  0, тому отриманий план оптимальний. Функція цілі

Lmax = 678 грн.

Цей прибуток максимальний і може бути отриманий, якщо виготовити 83 вироби А і 36 виробів В.

  1   2   3

Схожі:

Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки України Харківська національна академія міського господарства В. В. Масловський Програма та робоча програма навчальної дисципліни «Спецкурс за напрямом профілізації»
Міністерство освіти І науки України Харківська національна академія міського господарства
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки України Харківська національна академія міського господарства В. В. Масловський Програма та робоча програма навчальної дисципліни «Спецкурс за напрямом спеціалізації»
Міністерство освіти І науки України Харківська національна академія міського господарства
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки україни харківська національна академія міського господарства Білянський Олександр Максимович
Робота виконана в Харківської національної академії міського господарства Міністерства освіти І науки України, м. Харків
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки, молоді та спорту україни харківська національна академія міського господарства
З дисципліни «обстеження, ремонт І реконструкція будинків міського господарства»
Міністерство освіти І науки україни харківська національна академія міського господарства iconХарківська національна академія міського господарства прасоленко Олексій Володимирович
Робота виконана в Харківській національній академії міського господарства, Міністерство освіти І науки України
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки україни харківська національна академія міського господарства сазонова людмила іванівна удк 69. 003. 658. 012 Порівняльний аналіз розвитку будівельного комплексу І суміжних галузей
Робота виконана в Харківській національній академії міського господарства Міністерства освіти І науки України
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки, молоді та спорту україни харківська національна академія міського господарства
...
Міністерство освіти І науки україни харківська національна академія міського господарства iconМетодичні вказівки
Міністерство освіти І науки україни харківська національна академія міського господарства
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки україни харківська національна академія міського господарства проблеми розвитку туризму І готельного господарства: регіональний аспект харків, хнамг
Затверджено на засіданні вченої ради Харківської національної академії міського господарства (протокол № від січня 2009 р.)
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки україни харківська національна академія міського господарства тенденції та напрямки розвитку туріндустрії україни харків, хнамг
Затверджено на засіданні вченої ради Харківської національної академії міського господарства (протокол № від січня 2012 р.)
Міністерство освіти І науки україни харківська національна академія міського господарства iconМіністерство освіти І науки україни харківська національна академія міського господарства туризм як національний пріоритет харків, хнамг
Затверджено на засіданні вченої ради Харківської національної академії міського господарства (протокол № від січня 2009 р.)
Додайте кнопку на своєму сайті:
Документи


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