Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання icon

Методичні вказівки щодо практичних занять з навчальної дисципліни " математичне програмування" для студентів денної та заочної форм навчання




НазваМетодичні вказівки щодо практичних занять з навчальної дисципліни " математичне програмування" для студентів денної та заочної форм навчання
Сторінка1/7
Дата26.09.2012
Розмір1.57 Mb.
ТипМетодичні вказівки
  1   2   3   4   5   6   7


МІНІСТЕРСТВО ОСВІТИ, НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

КРЕМЕНЧУЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ МИХАЙЛА ОСТРОГРАДСЬКОГО







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


ЩОДО ПРАКТИЧНИХ ЗАНЯТЬ

З НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

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

для студентів ДЕННОЇ ТА заочної форм навчання ЗА НАПРЯМОМ 6.030601– “МЕНЕДЖМЕНТ”




Кременчук 2012

Методичні вказівки щодо практичних занять з навчальної дисципліни „Математичне програмування ” для студентів денної та заочної форм навчання за напрямом 6.030601– „Менеджмент”


Укладач к.т.н., доц.   В. Є. Черніченко

Рецензент к.т..н., доц.   Л. Д. Воробйова


Кафедра економіки


Затверджено методичною радою КрНУ імені Михайла Остроградського

Протокол № від « » 2012 р.

Голова методичной ради проф. В. В. Костін





ЗМІСТ



Вступ..............................................................................................................................4

1 Перелік практичних занять ………………………………………………………..6

Практичні заняття № 1-2 (Розв΄язання задач лінійного програмування)………...6

Практичні заняття № 3 (Розв´язання задачі про розподіл ресурсів з економічним аналізом отриманих результатів)…………………………………..........................8

Практичні заняття № 4-5 (Розв´язання транспортної задачі з економічним аналізом отриманих результатів)…………………………………………………..10

Практичні заняття № 6 (Розв´язання задачі про призначення) ……………………12

Практичні заняття № 7 (Розв´язання задачі цілочислового програмування) …14

2 Варіанти практичних завдань…………………………………………………….17

3 Типовий розв΄язок задач ………………………………………...……………….30

4 Питання до заліку………… ……………………………………………………...54

Список літератури.....................................................................................................56

Додаток А Зразок оформлення титульної сторінки семестрового практичного завдання ……………………………………………………………………………...58


ВСТУП


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

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

Матеріал курсу використовується для моделювання та оптимізації виробничих економічних процесів при виконанні курсових та дипломних робіт.

У результаті вивчення дисципліни студент повинен

знати:

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

− ідею стандартного симплекс-методу, розуміти економічний зміст додаткових та штучних змінних, двоїстих оцінок та їх зв'язок з критерієм оптимізації;

− про сферу застосування симплекс-методу та ситуації, коли його застосування є неможливим;

− теорію двоїстості та теореми двоїстості, зв'язок між змінними вихідної та двоїстої задач;

− теорію економічного аналізу лінійних моделей;

− що таке збалансована та незбалансована транспортна задача, знати загальну модель транспортної задачі;

− чому застосування симплекс-методу є неефективним у випадку транспортних задач і що таке спеціальні методи розв'язування;

− такі методи визначення опорного плану транспортної задачі: ме­тод північного-західного кута, мінімального елемента, метод Фогеля;

− що таке вироджена транспортна задача і як вона виправляється;

− загальну постановку задачі про призначення і як вона розв'язується в рамках цілочислового програмування за допо­могою угорського методу;

− постановку цілочисловоі задачі лінійного програмування та ії розв'яза- ння методом Гоморі;

в м і т и :

− застосовувати графічний метод розв'язування лінійних задач у випадку двох (і більше двох) змінних;

− приводити будь-яку лінійну модель до канонічного вигляду;

− застосовувати симплекс-метод до розв'язування типових економічних задач лінійного програмування у вигляді симплекс-таблиць, застосовувати метод прямокутника та звичайних Жорданових виключень;

− будувати двоїсті моделі та розв'язувати їх, а також на їх підставі знаходити розв'язок вихідної задачі;

− проводити економічний аналіз лінійних моделей, визначати оптимальний виробничий план, встановлювати міри збитковості невигідної продукції, міри дефіцитності ресурсів, розв'язувати питання щодо доцільності розширення асортименту продукції, встановлювати діапазони стійкості для запасів ресурсів та відпус­кних цін, за яких структура оптимального плану не змінюється;

− застосовувати до розв'язування транспортних задач вказа­них вище методів;

− застосовувати угорський метод до задач про призначення;

− застосовувати метод Гоморі для розв'язання цілочислової задачі лінійного програмування.

^ 1 ПЕРЕЛІК ПРАКТИЧНИХ ЗАНЯТЬ


Практичне заняття № 1-2

Тема. Розв´язання задач лінійного програмування

Мета: навчитися методам розв´язання задач лінійного програмування.


Короткі теоретичні відомості

1. Загальна задача лінійного програмування (З З Л П)

З З Л П зображується у вигляді:

max (min) (1)

а11X1 + а12X2 + …... + а1nXn = b1

а21X1 + а22X2 + …... + а2nXn = b2 (2)

аm1X1 + аm2X2 + …... + аmnXn = bm

X1 ≥ 0; X2 ≥ 0; …..., Xn ≥ 0 (3)

де aij, bi, Cj - задані постійні величини, (i=1;..m , j=1;..n).

2. Основні визначення З З Л П.

Визначення 1. Планом чи припустимим розв´язком З.З.Л.П. називається =(X1,...Xn), що задовольняє (2-3).

Визначення 2. План називається опорним, якщо вектори , що входять у розкладання (2) з позитивними Xj (Xj>0) лінійно незалежні.

Так як вектори m-мірні, то в опорному плані число його компонент більших нуля, не може перевищувати m.

Визначення 3. Опорний план * не вироджений, якщо він містить m позитивних компонентів, якщо меньш m позитивних компонентів, то * вироджений.

Визначення 4. Оптимальним планом З З Л П 0 називається план, що доставляє мінімум функції мети Z.

3. Вимоги до З З Л П для можливості її розв´язання симплексом-методом.

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

  1. обмеження – у виді рівностей;

  2. праві частини bi≥0;

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



(4)

.


Завдання до теми

1. Постановка загальної задачі лінійного програмування.

2. За допомогою метода Жордана-Гаусса:

а) знайти початковий опорний план і обчислити Z( );

б) перейти до іншого опорного плану й обчислити Z( ).

3. Для одного з опорних планів виразити базисні змінні через вільні, перейти від рівностей в обмеженнях задачі до нерівностей і розв´язати задачу геометрично.

4. Виходячи з опорного плану з «гіршою» функцією мети замінити задачу лінійного програмування в канонічній формі та розв´язати її симплекс-методом.

5. Розв´язати вихідну задачу методом штучного базису.

Контрольні питання

  1. Задачі, що приводять до поняття математичного програмування.

  2. Загальна постановка задач математичного програмування.

  3. Загальна задача лінійного програмування (З З Л П).

  4. Властивості розв’язання З З Л П.

  5. Графічний метод розв’язання З З Л П.

  6. Симплексний метод розв’язання З З Л П.

  7. Побудова опорних планів З З Л П.

  8. Умови оптимальності опорного плану З З Л П.

  9. Алгоритм симплексного методу.

  10. Метод штучного базису.

Література: [1, с. 3768; 4, с. 4975; 7, с. 531].


Практичне заняття №3

Тема. Розв´язання задачі про розподіл ресурсів з економічним аналізом отриманих результатів

Мета: навчитися методам розв´язування задачи про розподіл ресурсів і проведення економічного аналізу отриманих результатів.


^ Короткі теоретичні відомості

Змоделюємо вихідну задачу про розподіл ресурсів. Для цього позначимо за Xj кількість одиниць j-ої продукції, планованої для виробництва.


(5)



і що доставляє:

(6)


Змоделюємо двоїсту задачу. Позначимо через yi (i=1,…,m) вартість одиниці i-го виду ресурсів. Тоді вартість усіх ресурсів дорівнює , а вартість усіх ресурсів, що йдуть на виготовлення одиниці j-го виду продукції, дорівнює .

Тоді двоїста задача формулюється так: знайти , що задовольняє:


(7)

і що доставляє:

. (8)

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

Для того, щоб знайти оптимальні плани двоїстих задач, визначимо взаємозв'язок змінних двоїстих задач і економічний зміст їх додаткових змінних. Для вихідної задачі i-а додаткова змінна

, (9)


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

Для двоїстої задачі j-а додаткова змінна


(10)

є різницію між сумарною вартістю витрат усіх ресурсів yi на одиницю j-го виду продукції та вартості одиниці цієї продукції. Тому (j=1,…,n) можна трактувати як характеристику рентабельності випуску j-го виду продукції. Якщо ym+j>0 − випуск не рентабельний (витрати більші за ціну), якщо ym+j=0 − випуск j-го виду продукції рентабельний. У силу за вищевикладеним основним змінній однієї задачі відповідають додаткові змінні інший, тобто


(11)
Xn+i Yi ,

Ym+i Xi .

Причому для оптимальних планів цих задач випливає, що

(12)

(13)

З огляду на те, що всі змінні ненегативні з (12) і (13), для оптимальних планів виконується:

X0n+i=0 y0i>0 чи X0n+i>0 Y0i=0 ;

Y0m+j=0 X0j>0 чи Y0m+j>0 X0j=0 . (14)

З (14) для оптимальних планів двоїстих задач випливає:

1) якщо i-ий ресурс цілком використовується (X0n+i=0) , то його ціна Y0i>0, якщо немає (X0n+i>0) , то його ціна y0i=0, (j=1,…,m);

2) якщо витрати на випуск одиниці j-го виду продукції більше її ціни, Y0m+j>0, то ця продукція не випускається X0j=0, якщо Y0m+j=0, то випуск j-го виду продукції рентабельний і X0j>0, (j=1,…,n).


^ Завдання до теми

  1. Побудувати модель вихідної та двоїстої задач, знайти оптимальні плани x0 і y0.

  2. Дати економічне тлумачення основних і додаткових змінних вихідної та двоїстої задач.

  3. Проаналізувати доцільне розширення асортименту продукції за рахунок включення нової продукції.

  4. Установити діапазони зміни вихідних даних за ресурсами і ціною од. продукції, за яких структура оптимального плану не змінюється.


Контрольні питання

1. Двоїсті задачі лінійного програмування.

2. Економічна інтерпретація двоїстих задач.

3. Види двоїстих задач.

4. Зв’язок основних і додаткових змінних двоїстих задач.

5. Зв’язок оптимальних розв’язків двоїстих задач ,теореми подвійності.

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

Література: [1, с. 7799; 4, с. 85102; 7, с. 533].


Практичне заняття №4-5

Тема. Розв´язання транспортної задачі з економічним аналізом отриманих результатів

Мета: навчитися методам розв´язання транспортної задачі і проведення економічного аналізу отриманих результатів.


^ Короткі теоретичні відомості

Математична модель транспортної задачі.

Нехай xij це обсяг продукції що перевозиться з i-го пункту виробництва Аi до j-й пункту споживання Bj сij витрати на перевезення одиниці продукції з i-го пункту виробництва Аi до j-й пункту споживання Bj. Тоді функцією мети L буде функція сумарних витрат на перевезення всієї продукції:

(15)

Обмеження:

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

(16)

ai – загальний обсяг виробництва на і-му пункті виробництва Аi,

bj – загальний обсяг споживання j-го пункту споживання Bj,



(17)

, ,

xij0.

Метод північно- західного кута, суть методу:

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

хij=min(ai,bj).
  1   2   3   4   5   6   7

Схожі:

Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни «бюджетна система» для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни „Бюджетна система” для студентів денної та заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних робіт з навчальної дисципліни " аудит 1, 2" для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни «Аудит 1, 2» студентів денної та заочної форм навчання зі спеціальності...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни „ податки І податкова політика для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни „Податки І податкова політика ” для студентів денної та заочної...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни " кримінальне право" для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних робіт з навчальної дисципліни “Кримінальне право” для студентів денної та заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни „ організація І методика аудиту для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни „Організація І методика аудиту” для студентів денної та заочної...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо проведення практичних занять з навчальної дисципліни: "маркетинг" для студентів денної І заочної форм навчання зі спеціальності
Методичні вказівки щодо проведення практичних занять з навчальної дисципліни “Маркетинг” для студентів денної І заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни: „ організація обліку для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни „Організація обліку” для студентів денної та заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни „ правознавство для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з вивчення навчальної дисципліни „Правознавство” для студентів денної та заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни " економічна теорія" для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни «Економічна теорія» для студентів денної та заочної форм навчання...
Методичні вказівки щодо практичних занять з навчальної дисципліни \" математичне програмування\" для студентів денної та заочної форм навчання iconМетодичні вказівки щодо практичних занять з навчальної дисципліни " мікроекономіка" для студентів денної та заочної форм навчання
Методичні вказівки щодо практичних занять з навчальної дисципліни “Мікроекономіка” для студентів денної та заочної форм навчання...
Додайте кнопку на своєму сайті:
Документи


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