11780

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

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

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

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

Украинкский

2013-04-11

465 KB

31 чел.

ЛАБОРАТОРНІ РОБОТИ  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


 

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

67066. Інтегрований урок з хімії 53.5 KB
  Мета: поглибити знання учнів по хімії, сформувати уявлення про тісний зв'язок хімії з іншими навчальними предметами та про важливість знань з хімії для освіченої, ерудованої людини; формувати пізнавальний інтерес, розвивати логічне мислення, розширити кругозір учнів...
67067. Искусство эффективного слушания 34 KB
  Применить на практике навыки эффективного слушания на занятиях Оценить приоритеты эффективного слушания для говорящего и слушающего Материалы: листы бумаги маркер. Напишите на бумаге цветными маркерами основные понятия искусства слушать: Находиться рядом с говорящим; Узнавать мнение и позицию говорящего...
67068. Материки южного полушария 3.34 MB
  Цели и задачи: систематизировать и обобщить знания о материках южного полушария (общие географические закономерности, рельеф, климатические условия, гидроресурсы, растительный и животный мир, природные комплексы материков); применять имеющиеся знания в поисках решения проблемных ситуаций...
67070. Свято дитячої іграшки 198.66 KB
  Захід проводиться у святково-прикрашеній актовій залі гімназії. Учням запропоновано прийти на захід з своїми улюбленими іграшками. Ведуча. Доброго дня, дорогі друзі, шановні гості! Щиро вітаємо вас в нашій залі та гостинно запрошуємо на ... Богдан. Зачекай, Насте, нехай присутні самі здогадаються, який захід чекає на них сьогодні.
67071. ПОЛЕ ЧУДЕС «ПРОГНОЗ ПОГОДИ». СЕРІЯ ІГОР 101 KB
  Серію ігор міжпредметного характеру «Поле чудес «Прогноз погоди» проводять учні 10 – 11 класів під керівництвом вчителя фізики для учнів початкової та середньої ланок під час тижня фізики. Девіз заходу: навчився сам – навчи іншого. Мета серії ігор «Поле чудес «Прогноз погоди»: сформувати вміння орієнтуватися в оточуючому середовищі...
67072. Імен таємнича влада. Засідання мовного гуртка «Юний філолог» 83.5 KB
  Слово вчителя: У безкінечному ряді живих істот людини наділена одним незвичайним правом: вона і тільки вона має привілей вибирати наймення собі дітям своїм усьому навколишньому містам селам річкам звірам рослинам А хто знає як називається наука яка вивчає систему особових імен...
67073. Вправи на змінювання іменників за числами. Іменники, що вживаються лише в однині або лише в множині 41.5 KB
  То що ж називає іменник На які питання відповідає А чому ми ставимо до іменника питання хто і що Що ви ще можете сказати про іменник іменники бувають власні загальні. Перевірка А як ви думаєте які найважливіші іменники у житті кожної людини мама тато життя здоров’я хліб мова праця хата батьківщина мир...
67074. Робота з комп’ютерними програмами на підтримку вивчення української мови. М’які і тверді приголосні 2.86 MB
  Мета. Продовжувати вчити дітей працювати з комп’ютерними програмами підтримки вивчення української мови, перевірити вміння диференціювати звуки на твердість та м’якість; закріплення навичок фонетичного аналізу слова; розвивати логічне мислення, увагу, зосередженість; виховувати дисциплінованість та культуру навчальної праці при роботі з комп’ютером.