3. Питання для захисту роботи

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

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

3. Які методи розв’язання задач лінійного програмування вам відомі?

4. Який план задачі лінійного програмування називається опорним, а який оптимальним?

5. Що таке многокутник планів?

6. Яку інформацію крім оптимального плану можна отримати за допомогою опції «Поиск решений»

3. Задачі для самостійного розв’язання

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

1. 2)

3) 4)

5) 6)

7) 8)

9) 10)

11) 12)

5. Лабораторна практична робота №6

Транспортна задача

6.1. Мета роботи

Ознайомлення з особливостями побудови математичної моделі транспортної задачі за критерієм витрат та алгоритмом її розв’язання.

6.2. Порядок виконання роботи

1. Вивчити теоретичну частину (лекційний матеріал) : загальний вигляд транспортної задачі, методи побудови опорного плану, критерій оптимальності методу потенціалів. Виконати завдання, що відповідають номерові Вашого варіанта.

2. Оформите звіт по лабораторній роботі, що повинний містити:

• Формулювання завдання (варіант завдання вибирається відповідно до номера в журналі).

• Результати виконання програми

• Висновки (інтерпритація отриманих результатів).

6.3. Методичні рекомендації

Виражаю свою вдячність за данні наробітки Лебедевої І. Л.

Змістовна постановка задачі та її математична модель. Класична транспортна задача за критерієм витрат має таку постановку. Є постачальники ( ), в яких накопичені запаси однорідної продукції у кількості ( ), і є споживачі ( ), потреби яких у цій продукції сягають ( ). Причому виконується умова збалансованості:

, (6.1)

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

Якщо позначити через кількість вантажу (в умовних одиницях), яка перевозиться від -го постачальника -му споживачеві, то план перевезень утворює матрицю . Оскільки в даній задачі критерієм ефективності є загальна вартість перевезень , яка досліджується на мінімум, то цільова функція має вигляд:

. (6.2)

Керованими змінними в транспортній задачі є кількість вантажу ( , ), які повинні задовольняти певним обмеженням. Визначимо ці обмеження. Отже, запаси всіх постачальників необхідно вивезти:

, (6.3)

а потреби всіх споживачів треба задовольнити:

. (6.4)

Перевезення здійснюються тільки в одному напрямку: від постачальника до споживача, отже, не можуть бути від’ємними:

, , . (6.5)

Системи рівнянь (6.3) та (6.4) утворюють основну систему обмежень, нерівності (6.5) – це обмеження на знак. Отже, математична модель транспортної задачі за критерієм витрат задана співвідношеннями (6.2 – 6.5). Розв’язком цієї задачі буде оптимальний план , який задовольняє системі обмежень і при якому цільова функція досягає мінімуму. Транспортна задача має розв’язок за умов, якщо виконується співвідношення (6.1), тобто задача є закритою, або збалансованою. Якщо ж балансова умова порушена, то задачу спочатку треба закрити, ввівши фіктивного учасника: чи то споживача (якщо ), чи то постачальника (якщо ).

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

Вихідні дані:

;	.
;

Перевіряємо, чи виконується балансова умова транспортної задачі:

; .

Отже, задача є закритою, і вводити фіктивних учасників нема потреби.

Формалізація задачі. За вихідними даними задачі укладемо її математичну модель:

, , .

Оптимізація моделі за допомогою команди Поиск решения. Занесемо вихідні дані до робочого аркуша книги MS Excel, дотримуючись математичної моделі задачі. Спочатку виділяємо у вигляді таблиці місце для розв’язку − це масив клітин, що містять керовані змінні В3:F5. Їх вихідні значення зручно вважати рівними одиниці. Отже, у вихідному стані комірки В3:F5 містять самі одиниці (табл. 6.1).

Таблиця 6.1