Відмінності між версіями «Умова цілочисельності опорного плану»
Максим (обговорення • внесок) (→Теорема) |
Максим (обговорення • внесок) (→Література) |
||
| Рядок 13: | Рядок 13: | ||
Розв’язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки <math>a_i (i= \bar{(1,n)}</math> та <math>b_j, (j= \bar{(1,n)}</math> у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами. | Розв’язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки <math>a_i (i= \bar{(1,n)}</math> та <math>b_j, (j= \bar{(1,n)}</math> у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами. | ||
| − | |||
| − | |||
| − | |||
| − | |||
== Література == | == Література == | ||
Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003. - 452 с. | Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003. - 452 с. | ||
Поточна версія на 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 с.
