Відмінності між версіями «Умова цілочисельності опорного плану»
Максим (обговорення • внесок) (→Теорема) |
Максим (обговорення • внесок) (→Література) |
||
| (не показано одну проміжну версію цього учасника) | |||
| Рядок 4: | Рядок 4: | ||
Якщо всі запаси <math>a_i (i= \bar{(1,n)}</math> і всі потреби <math>b_j, (j= \bar{(1,n)}</math> є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами. | Якщо всі запаси <math>a_i (i= \bar{(1,n)}</math> і всі потреби <math>b_j, (j= \bar{(1,n)}</math> є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами. | ||
| − | Доведення. Компоненти кожної системи із m+n-1 лінійно не-залежних (базисних) векторів можуть бути подані у вигляді три-кутної матриці. Нехай розглядається задача (5.1)—(5.4). Матриця з перших m+n-1 компонент базисних векторів системи (5.2), (5.3) матиме вигляд: | + | Доведення. Компоненти кожної системи із m+n-1 лінійно не-залежних (базисних) векторів можуть бути подані у вигляді три-кутної матриці. Нехай розглядається задача (5.1)—(5.4) [[Критерії опорного плану.]]. Матриця з перших m+n-1 компонент базисних векторів системи (5.2), (5.3) [[Критерії опорного плану.]] матиме вигляд: |
[[Файл:F34.png]] | [[Файл:F34.png]] | ||
Поточна версія на 10:45, 4 травня 2012
Теорема
Теорема 5.3. Якщо всі запаси Неможливо розібрати вираз (невідома помилка): a_i (i= \bar{(1,n)}
і всі потреби Неможливо розібрати вираз (невідома помилка): b_j, (j= \bar{(1,n)}
є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами.
Доведення. Компоненти кожної системи із m+n-1 лінійно не-залежних (базисних) векторів можуть бути подані у вигляді три-кутної матриці. Нехай розглядається задача (5.1)—(5.4) Критерії опорного плану.. Матриця з перших m+n-1 компонент базисних векторів системи (5.2), (5.3) Критерії опорного плану. матиме вигляд:
(5.19) Перша половина матриці від Неможливо розібрати вираз (невідома помилка): A_{1n}...A_{mn}
це m, а Неможливо розібрати вираз (невідома помилка): A_{11}...A_{1}{n-1}
це n-1.
Розв’язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки Неможливо розібрати вираз (невідома помилка): a_i (i= \bar{(1,n)}
та Неможливо розібрати вираз (невідома помилка): b_j, (j= \bar{(1,n)}
у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами.
Література
Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003. - 452 с.
