непарного числа. В результаті 0.
Приклад побудови еквівалентних матриць.
Вибираємо найбільший 74 і зробимо з нього 0, віднімемо від стовпця, або рядка, +56 ???, щоб 56+18=74-74=0
Алгоритм розподільчого методу.
Приклад розв’язування транспортної задачі розподільчим методом.
Вироджені транспортні задачі. Критерій виродження транспортної задачі. Методи розв’язування транспортних задач.
Нехай ми маємо транспортну задачу.
???
Будуємо початковий базисний план транспортної задачі , тим самим ми будемо мати .
Від матриці в-тей С ми переходимо до матриці оцінок , в якій на місці Х вибраних елементів робимо 0.
Шукаємо . Клітка lk із набором буде творити хоча б один замкнутий ланцюг які ми позначимо через Q/
.
це ??? маса.
Робимо перенос ??? маси по ???
Тільки тепер від будемо переходити до і т. д. |
85 | 5
90 | 120 | 110 | 130
105 |
12 |
9 | 105
7 |
11
95 | 165 |
4 | 35
3 |
12 | 130
2
5 | 180 | 90
5 | 85
17 | 5
9 |
4
105
35 | 130
90 | 85 | 5
??? перевозки плану потрібно
12 | 3 | 7 | 11 | -15
4 | 3 | 12 | 2 | -3
5 | 17 | 9 | 4 | -14
+12 | +8 | +1
9 | -6 | 0 | -3
1? | 0 | 17 | 0 | -12
0 | 0 | 0 | -12
+12 | +12
С= =
5. (l,k)=(3,4)
6.
9 | 6 | 0 | 9
1 | 0 | 5 | 0
0 | 12 | 0 | 0
|
105
120 | 45
90 | | 5 | 85
=
??? ??? бо всі > 0.
Зауваження 1.
Якщо в матриці оцінок, що відповідає оптимальному плану є 0 крім Х вибраних 0, це є ознакою того, що дана транспортна задача має не єдиний оптимальний план.
Зауваження 2.
Із вище викладеної теорії слідує, що якщо ми маємо сквозні пункти, то запаси в цих пунктах і самі пункти можна об’єднувати і вважати як єдиний пункт, це слідує з того, що оптимальні плани транспортних задач з еквівалентними вартостями співпадають.
3 | 4
1
2
На відміну від задачі ЛП, де випадок виродження зустрічається рідко, випадок виродження в транспортній задачі досить рідко. виродженим в транспортній задачі можу ??? в 2 випадках:
а) при будові початкового базисного плану, коли запаси і потреби деяких пунктів ??? одна.
б) коли критична маса серед елементів парного ланцюга при переході від одного плану до іншого вибирається не однозначно.
Як показала практика виродження в транспортній задач відбувається тоді, коли в ній існують деяка група підпунктів виробництва та підпунктів споживання, для якої виконується частковий баланс мас.
Транспортна задача вироджена тоді і тільки тоді, коли в ній є в наявності частковий баланс мас.
(довести самостійно)
На практиці випадку виродження уникають слідуючим чином.
Аналогічно поступаємо і у випадку б.
Про деякі моделі, що зводяться до транспортних.
а) задача про ???.
Нехай ми маємо n видів робіт і нехай є n виконавців , будь-який виконавець .
Нехай - продуктивність з виконавця при виконанні ним і роботи, і нехай це є умова того, що j виконавець виконує і вид роботи.
Якби ми задавались вихідним параметром час, то вона б мала такий вигляд:
б) Задача оптимального розподілу станкового парку.
Нехай m – кількість типів станків
n – кількість типів станків
Нехай - план випуску деталей j виду на певний плановий період.
- загальний час роботи станків і типу.
Нехай - продуктивність виконання j типу деталей і типом станків.
Нехай - вартість обробки j типу деталей і типом станків (задані за одиницю часу).
- час роботи j типу деталей і типом станків.
, тому, що продукція залежить від типу станків і типу деталей.
Параметричне програмування.
Постановка задачі параметричного програмування.
Параметричне програмування вивчає поведінку розв’язку задач ЛП в залежності від тих чи інших коефіцієнтів
(2)
В загальному виді ЗЗП
Т – може бути відрізок, промінь або вісь.
Буде займатись вивчених задач виду
- це ??? вектора, а t то є параметр, який належить Т
Розв’язати задачу (2) для кожного параметра вказати оптимальний план цієї задачі, а також вказати ті границі, при яких даний план буде оптимальним.
Геометричний зміст параметричного програмування, коли вектор коефіцієнтів ЛФ залежить від параметру.
Пряма МС, яка відповідає параметру .
??? для задачі (2).
Виявляється , що точка А букде оптимальною не тільки , а ще в деякому околі точки .
// //
- значення параметра.
- , тоді з рисунка видно, що точка А буде оптимальною вершиною для тих значень параметра t, які будуть межами між і .
Розв’язати задачу (2) – це значить для кожного параметра вказати оптимальний план цієї задачі. Виберемо довільні і для вибраного розв’яжемо задачу (2).
Може бути два випадки.
І) ми знайшли оптимальний план задачі (2);
ІІ) при розв’язуванні задачі (2) для вибраного на деякій стислій таблиці ми зробимо висновок, що ЛФ є необмежена на множині своїх планів.
Знайти план .
З теоретичних основ ??? методу ми знаємо, що раз ми маємо оптимальний план задачі, то вектор оцінок повинен бути не від’ємний. А раз є оптимальний план (2), то .
Раз компонент вектора коефіцієнтів залежить від параметра t, значить і компонент вектора оцінок залежить від t.
Постараємось вивчити поведінку розв’язку (2) в залежності від параметра t, нас будуть цікавити параметри t, для яких виконується
(3)
(3) – це система лінійних алгебраїчних нерівностей з одним невідомим, якраз ми її і використаємо для знаходження кінців оптимального плану .
При розгляді нерівності (3) можуть зустрітися 3 випадки:
а) ;
б) ;
в) .
а) Якщо , то на параметр
