11780

Математичні методи дослідження операцій. Лабораторні роботи

Лабораторная работа

Информатика, кибернетика и программирование

ЛАБОРАТОРНІ РОБОТИ 16 з дисципліни Математичні методи дослідження операцій ЛАБОРАТОРНА РОБОТА № 1 ТЕМА: Графічний метод розв’язування задач лінійного програмування ЛП. МЕТА: Опанувати графічний метод побудови допустимої області ЗЛП та ліній рівн

Украинкский

2013-04-11

465 KB

30 чел.

ЛАБОРАТОРНІ РОБОТИ  1-6

з дисципліни

Математичні методи дослідження операцій

ЛАБОРАТОРНА РОБОТА № 1

ТЕМА: Графічний метод розв’язування задач лінійного програмування (ЛП).

МЕТА: Опанувати графічний метод побудови допустимої області ЗЛП та ліній рівня цільової функції; засвоїти зв'язок між екстремальними точками цільової функції та кутовими точками многокутника; встановити зв'язок між лініями рівня цільової функції та її антиградієнтом.

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Поняття випуклої множини.
  2.  Поняття многокутника, випуклої лінійної комбінації точок та крайніх (кутових) точок фігури.
  3.  Многокутник, як випукла комбінація вершин. Кутові точки, як точки можливого екстремуму лінійної функції.
  4.  Взаємозв'язок між паралельним переносом лінії рівня цільової функції та її антиградієнтом.
  5.  Виділити випадок необмеженої допустимої області ЗЛП.
  6.  Можливість альтернативного розв'язку та відсутність розв'язку в ЗЛП.
  7.  Зведення задач ЛП вищої розмірності до плоского випадку.

ЗАВДАННЯ

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


1.1.

1.2.

1.3.

1.4.

1.5.

1.6 .

1.7.

1.8 .

1.9.

1.10.

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


2.1.

2.2.

2.3.

2.4.

2.5.

2.6 .

2.7.

2.8 .

2.9.

2.10.

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

ЛАБОРАТОРНА РОБОТА № 2

ТЕМА: Симплекс-метод розв’язування задач лінійного програмування (ЛП).

МЕТА: Опанувати симплекс-метод розв’язування задач лінійного програмування

користуючись програмою Microsoft Excel.

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Поняття опорного (базисного) плану кутової точки багатогранника.
  2.  Поняття оптимального  плану задачі ЛП, та його ідентифікація у симплекс-таблиці.
  3.  Алгоритм знаходження опорного плану методом відбору.
  4.  Алгоритм знаходження опорного плану методом штучних змінних.
  5.  Алгоритм знаходження оптимального плану.
  6.  Випадок виродження системи обмежень.
  7.   Випадок, коли  лінійна форма не обмежена.

ЗАВДАННЯ

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


1.1.

1.2.

1.3.

1.4.

1.5.

1.6 .

7.

1.8 .

1.9.

1.10.

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

2.1.

2.2.

Параметр  дорівнює , де .

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

ЛАБОРАТОРНА РОБОТА № 3

ТЕМА: Транспортна задача.

МЕТА: Засвоїти метод потенціалів розв’язування транспортної задачі.

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Дати економічну і математичну постановку транспортної задачі.
  2.  Чим відрізняється транспортна задача від загальної задачі лінійного програмування?
  3.  Властивості опорних планів транспортної задачі.
  4.  Чим відрізняється відкрита транспортна задача від закритої ?
  5.  Як перетворити відкриту транспортну задачу на закриту ?
  6.  Метод лінійного елементу  побудови опорного плану.
  7.  Знаходження потенціалів та умови оптимальності.
  8.  Алгоритм методу потенціалів розв’язання транспортної задачі.
  9.  Випадок вродженості опорного плану.

ЗАВДАННЯ

1.  Знайти оптимальний план транспортної задачі.

Додаткова умова:

1.1.

ai = (20; 25; 20; 10);

bj = (20; 30; 40; 15);

попит третього споживача задовольнити повністю.

1.2.

ai = (20; 16; 14; 22);

bj = (16; 18; 12; 15);

ресурси четвертого постачальника використати повністю.

1.3.

ai = (10; 8; 15; 12);

bj = (15; 10; 5; 20);

попит першого та четвертого споживачів задовольнити повністю.

1.4.

ai = (75; 80; 70);

bj = (30; 70; 70; 35);

ресурси першого та третього постачальників використати повністю.

1.5.

ai = (100; 150; 180; 70);

bj = (100; 200; 230; 80);

повне задоволення потреб першого та другого споживачів

1.6.

ai = (40; 30; 20; 40);

bj = (20; 40; 30);

ресурси першого та другого постачальників в оптимальному плані використати повністю.

1.7.

ai = (75; 40; 35; 40);

bj = (20; 60; 180);

повністю задовольнити попит третього споживача та неможливо виконувати перевезення за маршрутами А1В2 та А3В1.

1.8.

ai = (80; 40; 60; 40);

bj = (45; 65; 20; 80);

повністю використати ресурси четвертого постачальника та не виконувати перевезення за маршрутами А2В3 та А3В4.

1.9.

ai = (5; 20; 10; 15);

bj = (10; 25; 15; 5);

попит другого споживача задовольнити повністю та за маршрутом А2В3 перевезти рівно 10 од. продукції.

1.10.

ai = (10; 20; 20; 30);

bj = (20; 15; 25; 10);

якщо ресурси четвертого постачальника потрібно використати повністю і за маршрутом А4В3 перевезти 20 од. продукції.

2.  Знайти оптимальний план транспортної задачі.

Параметри k, t  дорівнюють  

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

ЛАБОРАТОРНА РОБОТА № 4

ТЕМА: Метод Гоморі. Знаходження цілочисельного розв’язку задачі лінійного

програмування (ЛП).

МЕТА: Опанувати метод Гоморі (метод відсікаючи площин) знаходження

цілочисельного розв’язку задачі лінійного програмування (ЛП).

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Дати загальну постановку задачі цілочисельного програмування.
  2.  Геометрична інтерпретація задачі цілочисельного програмування.
  3.  Геометрична інтерпретація методу Гоморі (метод відсікаючи площин).
  4.  Алгоритм методу Гоморі.
  5.  Обчислювальні можливості методу Гоморі.

ЗАВДАННЯ

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

1. ,

  

2. ,

  

3.

    

4.

   ,   

5.

  

  

6.

      

  

7.

  

 

8. ,

  

9. ,

  

10. ,

  

2.  Розв’язати задачу цілочисельного програмування методом Гоморі.

1. ,

  

2. ,

  

3. ,

  

4. ,

  

5. ,

  

6. ,

  

7.  ,

     

8. ,

  

9.  ,

  

  

10. ,

  

   

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

ЛАБОРАТОРНА РОБОТА № 5

ТЕМА: Метод гілок та мереж у розв’язанні задач цілочисельного програмування .

МЕТА: Опанувати метод гілок та мереж знаходження цілочисельного розв’язку

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

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Дати загальну постановку задачі цілочисельного програмування.
  2.  Геометрична інтерпретація методу гілок та мереж.
  3.  Алгоритм методу гілок та мереж.
  4.  Обчислювальні можливості методу гілок та мереж.

ЗАВДАННЯ

1.  Методом гілок та мереж розв’язати задачу цілочисельного програмування.

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

1. ,

  

2. ,

  

3 . ,

  

4. ,

  

5. ,

  

6. ,

  

7. ,

  

8.  ,

  

9. ,

  

10. ,

  

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

ЛАБОРАТОРНА РОБОТА № 6

ТЕМА: Динамічне програмування (метод Беллмана).

МЕТА: Опанувати метод багатокрокової оптимізації (метод Беллмана) розв’язання динамічних задач.

КОНТРОЛЬНІ ЗАПИТАННЯ

Дати короткі теоретичні відомості, в яких відобразити наступні питання:

  1.  Загальна постановка задачі динамічного програмування.
  2.  Принцип динамічного програмування: умовно-оптимальні плани.
  3.  Принцип оптимальності Р. Беллмана і рекурентні відношення.
  4.  Алгоритм Р. Беллмана  розв’язування задачі.

 

ЗАВДАННЯ

1. Фірма планує нарощувати виробничі потужності на трьох підприємствах, виділяючи для цього 18 млн грн. За кожним із підприємств розроблено інвестиційний проект із зазначенням прогнозованих сумарних витрат С та доходів D, що пов’язані з його реалізацією. Розробити план інвестування.

Інвестиційний проект

Підприємство

1

2

3                                                                 

Інвестиції, млн грн.

Прибуток,
млн грн.

Інвестиції,
млн грн.

Прибуток,
млн грн.

Інвестиції,
млн грн.

Прибуток,
млн грн.

1

0

0

0

0

0

0

2

2

6

6

12

7

9

3

4

8

7

14

8

10

4

5

11

9

18

10

14

2. Розв’язати попередню задачу (1), якщо розмір інвестицій становить 20 млн грн., а перший інвестиційний проект (ситуація, коли певному підприємству не виділяється коштів) є неприпустимим.

3. Розв’язати задачу 1, якщо модернізація має проводитися ще на одному — четвертому підприємстві фірми, для якого розроблено три інвестиційні проекти:

Проект

Інвестиції, млн грн.

Прибуток, млн грн.

1

0

0

2

4

6

3

5

8

Врахувати, що інвестиційний портфель збільшиться на 2 млрд грн.

4. Знайти оптимальний розподіл 6 млрд грн. між трьома підприємствами галузі. Прибуток, який можна одержати від капіталовкладень певного розміру в кожне з підприємств, відбиває таблиця:

Розмір
капіталовкладень,
млн грн.

Прибуток по підприємствах, млн грн.

I

II

III

1

0,27

0,34

0,21

2

0,31

0,44

0,35

3

0,42

0,57

0,46

4

0,65

0,69

0,68

5

0,74

0,87

0,74

6

0,93

0,95

0,85

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

Проект

Підприємство

1

2

3

4

Інвестиції,
млн грн.

Прибуток,
млн грн.

Інвестиції,
млн грн.

Прибуток,
млн грн.

Інвестиції,
млн грн.

Прибуток,
млн грн.

Інвестиції,
млн грн.

Прибуток,
млн грн.

1

1

5

2

4

3

8

2

5

2

3

6

3

7

4

11

3

6

3

4

8

4

9

5

12

6

9

6. Розв’язати чотириетапну задачу управління запасами за вихідними даними:

Етап

Попит, од.

Витрати
на розміщення замовлення, грн.

1

70

100

2

58

115

3

64

98

4

85

86

Відомо, що витрати на зберігання одиниці продукції протягом одного етапу сталі і становлять 2 грн., витрати на придбання одиниці продукції — 3 грн. для всіх етапів. Вихідний запас на початок досліджуваного періоду — 10 од.

7. Розв’язати попередню задачу (6), якщо вихідний запас дорівнює 40 од., а витрати на зберігання змінюються поетапно і становлять відповідно 1; 1,5; 2; 5 грн.

8. Розв’язати п’ятиетапну детерміновану задачу управління запасами:

Етап

Попит, од.

Витрати на розміщення
замовлення, грн.

Витрати
на зберігання, грн.

1

110

40

1

2

70

20

2

3

90

45

2

4

80

37

1

5

115

48

1

Функція витрат на розміщення замовлення визначає питомі витрати: 20 грн. для перших 50 од. та 10 грн. за кожну додаткову одиницю (знижка на кількість).

9. Розв’язати на ПК десятиетапну детерміновану задачу управління запасами, вважаючи, що вихідний запас дорівнює 65 од.

Етап

Попит

Витрати
на придбання, грн.

Витрати
на зберігання, грн.

Витрати на розміщення
замовлення, грн.

1

140

7

1

100

2

160

8

3

100

3

130

9

2

120

4

50

10

1

110

5

80

4

2

180

6

90

3

2

200

7

110

6

3

160

8

170

5

1

150

9

190

9

2

200

10

75

11

4

300

10. Розв’язати задачу, розв’язок якої наведено в прикладі 9.1, якщо розмір інвестицій становить 10 млн грн., а перший інвестиційний проект має наступні характеристики

Проект

Підприємство

1

2

3

4

1

1

2

2

3

1

3

2

4

Номер варіанта обирається згідно останньої цифри залікової книжки!

Звіт про виконання лабораторної роботи повинен містити:

  •  формулювання задачі;
  •  хід розв’язку;
  •  отримані чисельні результати;
  •  аналіз результатів;
  •  висновки.

PAGE   \* MERGEFORMAT 3


 

А также другие работы, которые могут Вас заинтересовать

52538. Дитинство Ісуса Христа 116 KB
  Мета: ознайомити учнів з дитинством Спасителя, вказуючи на Його чесноти; розвивати бажання брати собі за взірець Христа; виховувати послух, покірність та повагу до батьків.
52539. Всі ми родом із дитинства 97 KB
  Евеліна Хромченко Дитинство Дитинствоказка мов чарівна мить Там завжди сонячно і світло. Надія Красоткіна Дитинство це коли день починається з першим променем сонця звуком тихих маминих кроків запахом теплого хліба співом птахів і триває довгодовго це коли дерева великі а ти внизу і помічаєш так багато: і мурашки і бджолу на квітці і пухнасту гусеницю і чуєш як росте трава і можеш залізти на найвище дерево і переплести саму широку річку і все можеш зробити сам. Варто подумати про дитинство і пам’ять підкине дивні...
52540. Свято здоровя 43 KB
  Підвищувати відповідальність за особисте здоровя, здоровя родини; пропагувати і заохочувати до співпраці дітей та батьків; розвивати і зміцнювати в учнів почуття прекрасного в побуті, працьовитість, повагу до звичаїв і традицій рідного народу; виховувати повагу в особистих стосунках, почуття колективізму та взаємодопомоги.
52541. Сценарій свята для учнів 2-х класів «Різдвяне диво» 81 KB
  Заходять колядники звіздар ангел зірка коза дохтур Звіздар. Де коза ходить там жито родить Де коза ногою там жито копою Де коза рогом там жито стогом. Коза скаче а потім падає Пуць Коза впала нежива стала Ой Ой Яка добра тваринка була Що ж то робити Усі. Де тут хто тут пацієнт Виліковую в момент Робить козі укол коза оживає встає танцює танець всі плескають у долоні Усі.
52542. Ти наше диво калинове, кохана українська мово 61 KB
  Ведуча Мова А що таке мова Народ говорить слово до слова зложиться мова а Т . Ведучий Найбільше і найдорожче добро кожного народу – це його мова ота жива схованка людського духу його багата скарбниця в яку народ складає і своє давнє життя і свої сподіванки розум досвід почуття. Добута з надр далеких поколінь Ти – скарб наш вічний українська мова. Мова ...
52543. ДИВОСВІТ. Методичні рекомендації 8.27 MB
  Методичні рекомендації «Дивосвіт» вихователя Менського дошкільного закладу «Сонечко» Шевель Наталії Володимирівни допоможуть педагогічним працівникам дошкільних закладів у створенні та облаштуванні розвивального простору в групах дошкільних навчальних закладів.
52544. Методичний проект «Центр дитячої творчості Дивосвіт як заклад життєвої компетентності» 58.5 KB
  Підвищити рівень орієнтованності навчально виховного процесу закладу на розвиток життєвої компетентності особистості учня. Націлити педагогів закладу до розробки та впровадження авторських програм навчальних посібників нового покоління 3. Переорієтнувати виховну систему закладу відповідно до вимог часуформування через освіту здорового способу життя дітей та молоді інтеграцію освіти до європейського та світового освітнього простору 5.
52545. Україно! Мій духмяний дивоцвіт 53 KB
  Разом: Збулося Хлопчик: 24 серпня 1991 року Верховна Рада України урочисто прийняла Акт проголошення України незалежною самостійною демократичною державою. На цьому шляху загинула незліченна кількість кращих синів і дочок України які відстоювали її незалежність. Шлях України позначений високими степовими могилами руїнами та прекрасними безіменними невідомо коли і ким складеними піснями. Хлопчик: Народе України Твоєю силою волею.
52546. Внутрішні гіперпосилання на веб-сторінках 107.5 KB
  Ввести поняття внутрішнього посилання, ознайомити з правилом запису внутрішнього посилання, навчити учнів створювати внутрішні гіперпосилання на веб-сторінці, розвивати пізнавальну активність, вміння індивідуально працювати за комп’ютером, виховувати інтерес до інформатики і біології, формувати інтерес учнів до природи рідного краю і питань збереження рослин.