11780

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

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

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

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

Украинкский

2013-04-11

465 KB

39 чел.

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


 

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

57523. Люблінська унія. Початок польського володарювання на українських землях 89.5 KB
  Мета: розкрити причини основні положення Люблінської унії зясувати політику Речі Посполитої щодо України її політичний устрій та державну систему; показати суттєву зміну становища українських земель...
57524. Політичний і соціально-економічний розвиток Галицького і Волинського князівств. Піднесення Галицького князівства за Володимира та Ярослава Осмомисла 86 KB
  Піднесення Галицького князівства за Володимира та Ярослава Осмомисла. Вчити учнів вмінню показувати на карті території князівств часів роздробленості Русі порівнюючи їх із територіями колишніх племінних союзів східних словян...
57525. Україна в період кризи радянської системи (1964-1985 рр.) 143.5 KB
  Навчальна: Продовжити формування хронологічної, просторової, логічної компетенцій в процесі узагальнення, систематизації та конкретизації подій, явищ та фактів з теми.
57526. The Golden Horse-shoe of Cherkasy Region 48.5 KB
  Objectives: to develop students’ cognitive and creative skills; to provide students with an opportunity to practise listening, reading, writing and speaking skills; to encourage students to work on projects...
57527. Об'єднане королівство Великобританії та Північної Ірландії 96 KB
  There are a lot of countries in the world. And every country has its own customs and traditions. So has Great Britain. Every country has its own flag, symbols and national holidays.
57528. Проблеми жінки у світі. Статус жінки у суспільстві (The problems of a woman in the world. The status of a woman in the society) (Граматичний матеріал) Пряма/Непряма мова - Direct/reported speech) 53.5 KB
  Everyone knows that men and women are very often confused by each other (it`s not surprising). The author of the international bestseller John Gray says it is so because they are from different planets. Men are from Mars, women are from Venus.
57529. Письменники англомовних країн. Книги в нашому житті 54 KB
  Розвиток навичок аудіювання з метою вилучення інформації з прослуханого тексту; активізація вживання граматичних структур Past Indefinite Passive в усному мовленні; Виховувати в учнів почуття любові та інтерес до книги. Розширювати літературний кругозір учнів.
57530. Свята в англомовних країнах 50 KB
  Освітня Познайомитись з традиціями англомовних країн Познайомитись з історією деяких свят Виховна Виховувати в учнів повагу до традицій інших народів.
57531. Защита окружающей среды на Украине 58 KB
  The problem of environment protection has become of vital importance not obly in Ukraine. After watching some shots you must answer the question: What will we do to help to protect the environment?