сують обмеження, і функція мети є лінійними. В
Лекція 2.
1.7. Транспортна задача
Вугілля, що видобувається в двох родовищах, відправляється трьом споживачам (заводам, електростанціям і т.п.). Відомо, скільки вугілля видобувається з кожного родовища, наприклад за місяць, і відомо, скільки його потрібно в цей же строк кожному споживачеві.
Відомі також відстані між родовищами та споживачами та умови сполучення між ними.
Враховуючи ці дані, можна підрахувати, у що обійдеться перевезення кожної тонни вугілля з будь-якого родовища в будь-який пункт призначення.
Потрібно спланувати перевезення вугілля так, щоб витрати на них були мінімальними.
споживачі
В В
відправники
П 1
П 2
П 3
Всього
надіслано
Про 1
c 11
x 11
c 12
x 12
c 13
x 13
а1
Про 2
c 21
x 21
c 22
x 22
c 23
x 23
а2
Всього
привезено
b 1
b 2
b 3
а 1 + а 2 =
= b 1 + b 2 + b 3
В
Побудуємо математичну модель:
a) х kn кількість тонн вугілля, яке потрібно
перевезти від O k до П n ;
b) обмеження:
В В В В В В В
c ) мета - витрати на перевезення повинні бути мінімальними, т.е
В В
2. Канонічна і стандартна завдання лінійного програмування
2.1. Канонічна задача лінійного програмування
У канонічній завданню система обмежень, крім тривіальних, містить тільки рівняння. Прикладом канонічної задачі може служити транспортна задача.
2.2. Стандартна задача лінійного програмування
У стандартній задачі всі обмеження складаються тільки з нерівностей.
Прикладами стандартних завдань є завдання про дієту, завдання про банк, завдання про використання ресурсів .
Стандартна і канонічна завдання зводяться одна до іншої.
2.3. Зведення стандартної задачі лінійного програмування до канонічної на прикладі задачі про дієту.
Стандартна Канонічна
a) x 1 , х 2 , x 3
b)
с)
a) x 1 , х 2 , x 3 , x 4 , х 5 , x 6
b)
с)
x 4 , х 5 , x 6 - балансові змінні
2.4. Зведення канонічної завдання до стандартної
Нехай д...
