- •Економічна інформатика
- •1) Лінійні і нелінійні задачі:
- •2) Дискретні та неперервні задачі:
- •3) Детерміновані та стохастичні (ймовірностні) задачі:
- •4) Статичні (однокрокові) та динамічні (багатокрокові) задачі:
- •Зміст виконання завдання
- •Зміст виконання завдання
- •Критерій оптимальності – мінімум затрат праці - запишемо як
- •Зміст виконання завдання
- •Скласти план вантажних перевезень з мінімальним вантажообігом.
- •Втрати живої ваги при перевезенні худоби, кг на 1 т
- •Площі попередників озимої пшениці, га
- •Площа сортів озимої пшениці, га
- •Середня урожайність озимої пшениці за попередниками, ц з 1 га
- •Зміст виконання завдання
- •Зм 3. Двоїстість у лінійному програмуванні
- •Зм 4. Цілочислове програмування
- •6.1. Метод відтинання Гоморі
- •6.2. Метод гілок і меж
- •Зм 5. Оптимізаційні економіко-математичні моделі
- •7.1. Моделювання виробничих систем в рослинництві
- •7.2. Моделювання виробничих систем в тваринництві
- •7.3. Моделювання виробництва і реалізації продукції
- •Зміст виконання завдання
- •Зм 6. Оптимізаційні задачі управління запасами Завдання 8. Детерміновані та стохастичні моделі управління запасами
- •Детермінована статична однономенклатурна модель управління запасами без дефіциту
- •Стохастична модель управління запасами за умови, що попит характеризується нормальним законом розподілу
- •Стохастична модель управління запасами за умови штрафу за дефіцит
- •Зм 7. Моделі задач масового обслуговування
- •Зміст виконання завдання
- •Зм 8. Задачі упорядкування та координації
- •Зміст виконання завдання
- •Зм 9. Задачі та моделі заміни обладнання Завдання 11. Моделювання заміни обладнання
- •Отже, рекурентне співвідношення для періоду т буде мати вигляд:
- •Якщо обладнання після списання реалізується, то рекурентне свіввідношення має вигляд
- •Зміст виконання завдання
- •Зм 10. Задачі з умовами невизначеності та конфлікту
- •Задачі для самостійного розв’язування
- •Зміст виконання завдання
- •Зміст виконання завдання
- •Зм 11. Багатокритеріальні задачі
- •Зміст виконання завдання
- •Додаток а Приклад використання надбудови SimplexWin для розв’язування задач лінійного програмування в симплексних таблицях
- •Додаток б Приклад використання Excel для розв" язання симплексних задач лінійного програмування за допомогою надбудови "Поиск решения"
- •Додаток в Приклад використання Excel для розв’язання транспортних задач лінійного програмування (тзлп) за програмою "Поиск решения"
- •Список рекомендованої літератури Підручники та навчальні посібники
- •Електронні ресурси
- •Марченко Володимир Петрович Економічна інформатика
Зміст виконання завдання
1. Запис умов задачі за індивідуальним варіантом.
2. Формулювання економіко-математичної моделі задачі.
3. Розв'язок задачі на ПЕОМ в симплексних таблицях (додаток А) та за допомогою надбудови MS Excel ”Поиск решения” (додаток Б).
4. Висновки за результатами розв'язку задачі.
Завдання 4. Транспортна задача.
Теоретична частина . В класичній постановці транспортна задача формулюється так: нехай на m визначених пунктах (постачальники) зосереджено однорідний вантаж у кількостях ai (i = 1,m ), який потрібно перевезти до n інших пунктів (споживачі) у кількостях bj (j = 1,n ). Відомо, що відстань перевезення вантажу із i-го до j-го пункту дорівнює сij (i = 1,m; j = 1,n ). Обсяг перевезеного вантажу із i-го до j-го пункту позначимо через хij.
Скласти оптимальний план перевезення всього вантажу від постачальників до споживачів з умовою повного забезпечення потреби споживачів при мінімумі вантажоперевезень.
В загальному вигляді задачі транспортного типу розв"язуються як на мінімум, так і на максимум цільової функції. Математичний запис задачі транспортного типу такий: знайти вектор невідомих х = (х1, х2, ..., хj, ..., хn), при якому цільова функція Z досягає екстремуму
n m
Zext = ∑ ∑ cij xij
j=1 i =1
при обмеженнях:
n
1) ∑ xij = bi j (1,n); i (1,m)
j=1
m
2) ∑ xi j = аj
i =1
3) xij >= 0
Алгоритм розв’язання транспортної задачі, як і алгоритм симплексного методу, поділяється на два етапи.
1-й етап - знаходження початкового розв’язку задачі -застосовуються декілька методів:
а) діагональний або північно-західного кута - у верхню ліву клітину (північно-західний кут) транспортної таблиці записуємо максимально можливий вантаж, який можна перевезти від 1-го постачальника до 1-го споживача - порівнюються обсяги вантажу 1-го постачальника (стовпчик) і потреба 1-го споживача (рядок) і вибираєтьсянайменшечисло. Якщо потреба 1-го споживача задоволена або весь вантаж 1-го постачальника перевезено, то всі інші клітини 1-го рядка
або 1-го стовпчика транспортної таблиці будуть незаповненими (небазисними). В наступну клітину 2-ої колонки або 2-го рядка знову записуємо максимально можливий вантаж. Розрахунки продовжуютьсядоти, поки не буде розподілено за споживачами весь вантаж. Недоліком цього методу є те, що вантаж розподіляється без врахування оцінки клітини сij транспортної таблиці, внаслідок чого отримуємо початковий розв’язок задачі далекій від оптимального, що збільшує кількість ітерацій для отримання оптимальногорозв’язку, аперевагою - відсутність виродженого опорного розв’язку задачі;
б) подвійної переваги -спочатку окремо в кожному рядку і кожному стовпчику транспортної таблиці відмічаються клітини знайменшими(при розв’язанні задачі намінімумцільової функції) або знайбільшими(при розв’язанні задачі намаксимум цільової функції) оцінками клітинсij. У клітини, що мають найменшу (найбільшу) оцінку як по рядку, так і по стовпчику ставимо максимально можливийобсяг вантажу і так доти, поки не буде розподілено весь вантаж. Недоліками цього методу є велика ймовірність отриманнявиродженогоопорного розв’язку, що потребує виконання додаткових розрахунків з метою подолання виродженості, та трудоємкість пошуку клітин з найменшими (найбільшими) оцінками як по рядках, так і по стовпчиках транспортної таблиці при достатньо великих розмірах транспортної задачі, а перевагою – менша кількість ітерацій порівняно з методом північно-західного кута;
в) “найкращого” елементу матриці (транспортної таблиці) – в транспортній таблиці (матриці) знаходиться клітина з найменшою (при розв"язанні задачі на мінімум цільової функції) або з найбільшою (при розв"язанні задачі на максимум цільової функції) оцінкою сij клітини, в яку ставиться максимально можливий обсяг вантажу, потім наступна за нею клітина і так далі, поки не буде розподілено весь вантаж. Недоліки і переваги цього методу такі ж, як і в методі подвійної переваги.
Допустимий опорний план транспортної задачі, отриманий за будь-яким із наведених вище методів, повинен задовольняти таким умовам:
1) транспортна задача повинна бути закритою,тобто сумарна потужність всіх постачальників повинна дорівнювати сумарній потребі всіх споживачів. Для перетворення відкритої транспортної задачі в закриту вводитьсяштучний постачальник, якщо сумарна потреба споживачів більша сумарної потужності постачальників, абоштучний споживач, якщо сумарна потреба постачальників більша сумарної потужності споживачів, з нульовими оцінками клітинта обсягом вантажу, який дорівнює різниці між сумарними потужностями постачальників та потребами споживачів;
2) при розрахунках повинен забезпечуватися балансвантажів по кожному рядку і по кожному стовпчику транспортної таблиці;
3) заповнені клітини (базисні невідомі) транспортної таблиці не повинні утворювати циклів (замкнутих контурів);
4) кількість заповнених клітин в транспортної таблиці повинна дорівнювати m + n – 1, де m - кількість рядків, а n - кількість стовпчиків. Якщо кількість заповнених клітин менше m + n – 1, то отриманий опорний план задачі буде виродженим. Для подолання виродженості кількість заповнених клітин доповнюється нуль-поставками до кількості m + n – 1, але так щоб утворювана сукупність заповнених клітин разом з нуль-поставками була ациклічною.
2-й етап-знаходження оптимального розв’язку транспортної задачі - умовою оптимальності розв'язку транспортної задачі є:
1) ui+vj = cij – для базисних невідомих (заповнені клітини);
2) ui+vj cij – для небазисних невідомих (незаповнені клітини) при розв'язанні
задачі на мінімум цільової функції;
3) ui+vj cij – для небазисних невідомих (незаповнені клітини) при розв'язанні
задачі на максимум цільової функції,
де ui - потенціали рядків,
vj – потенціали колонок.
Розрахунок потенціалів проводять за такою схемою: поклавши u1=0, значення решти потенціалів отримуємо згідно умови ui+vj = cij. Оптимальність розв'язку задачі на мінімум цільової функції перевіряємо для кожної незаповненої клітини за умовою ui+vj cij, а при розв'язку задачі на максимум цільової функції за умовою ui+vj cij. Якщо розв’язок не оптимальний, то виконуються такі розрахунки:
1. Серед „неоптимальних” клітин вибирається та, у якої різниця між сумою потенціалів і оцінкою клітини найбільша (початкова клітина циклу перерахунків). Якщо ці різниці однакові для деяких клітин, то серед них вибирається клітина з меншою оцінкою при розв'язку задачі на мінімум цільової функції, або з більшою оцінкою при розв'язку задачі на максимум цільової функції.
2. До вибраної клітини будується цикл перерахунків, в якому всі клітини крім вибраної повинні бути заповненими (базисними). При цьому будь-якому рядку або будь-якому стовпчику транспортної таблиці можуть належати тільки дві вершини циклу перерахунку. Перехід від однієї клітини до іншої може бути тільки в заповненій клітині під кутом 90о. Цикл повинен замикатися на першій (вибраній) незаповненій клітині (тобто там, де він починався).
Цикли можуть бути різної конфігурації, наприклад:
3. У вибрану „неоптимальну” клітину циклу ставимо знак "+", а далі у вершинах циклу знаки по черзі "-", "+", "-" так, щоб у будь-якому рядку або у будь-якій колонці були тільки протилежні знаки, тобто "+" і "-". Отримуємо додатній "півцикл" з вершинами "+" і від'ємний "півцикл" з вершинами "-".Увід'ємному"півциклі" знаходимо вершину знайменшим числом (вантажем), яке додаємо в клітинах циклу із знаком "+" і віднімаємо в клітинах із знаком "-". В результаті отримуємо новий базисний розв'язок транспортної задачі.Розрахунки повторюються на кожній ітерації до отримання оптимального розв'язку.
Контрольні питання
Як сформулювати транспортну задачу лінійного програмування і записати її математичну модель у вигляді транспортної таблиці ?
Які є методи побудови початкового опорного плану транспортної задачі ?
Яка модель транспортної задачі називається відкритою, а яка закритою ?
Як відкриту модель транспортної задачі перетворити у закриту ?
Які змінні транспортної задачі називаються базисними, а які небазисними ?
Скільки базисних змінних повинно бути у не виродженому опорному плані ?
Як подолати виродженність опорного плану транспортної задачі ?
Як знайти значення потенціалів?
Ознаки оптимальності опорного плану транспортної задачі ?
10. Які є правила побудови циклу перерахунків?
11. Як перейти до нового базисного плану транспортної задачі ?
Приклад 4.1. Потрібно перевезти мінеральні добрива з трьох складів (постачальники) ємністю по 200 т кожний до чотирьох господарств (споживачі), потреба яких в мінеральних добривах становить відповідно 150, 100, 150 та 200 т.
Відстані від складів до господарств наведені в таблиці, км
Склади |
Господарства | |||
S1 |
S2 |
S3 |
S4 | |
D1 |
5 |
6 |
7 |
8 |
D2 |
8 |
9 |
10 |
11 |
D3 |
7 |
14 |
15 |
20 |