Відмінності між версіями «Умова існування розв’язку ТЗ»
| Рядок 27: | Рядок 27: | ||
}{W}=\frac{b_{j} }{W}\sum\limits_{i=1}^m {a_{i} } =} \frac{b_{j} }{W}W=b_{j} | }{W}=\frac{b_{j} }{W}\sum\limits_{i=1}^m {a_{i} } =} \frac{b_{j} }{W}W=b_{j} | ||
</math>; | </math>; | ||
| + | |||
| + | Оскільки умови (2) та (3) виконуються, то <math>x_{ij} =\frac{a_{i} b_{j} }{W}</math> <math>\left( {i=\overline {1,m} ;\,\,\,j=\overline {1,n} } \right)</math> є планом наведеної транспортної задачі. | ||
| + | |||
| + | Виберемо з елементів <math>c_{ij} \;\,\left( {i=\overline {1,m} ;\,j=\overline {1,n} } \right)</math> найбільше значення і позначимо його через <math>\overline {c } =\max \,c_{ij}</math>. Якщо замінити в цільовій функ¬ції (1) всі коефіцієнти на , то, враховуючи (2), матимемо: | ||
Версія за 15:33, 16 травня 2012
Теорема: необхідною і достатньою умовою існування розв’язку транспортної задачі (1)—(4) є її збалансова-ність: Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {a_{i} } =\sum\limits_{j=1}^n {b_{j} }
Доведення. Необхідність. Нехай задача (1)—(4) має розв’язок Неможливо розібрати вираз (невідома помилка): X^{\ast }(x_{11}^{\ast } ,x_{12}^{\ast } ,...,x_{mn}^{\ast } )
, тоді для нього виконуються рівняння-обмеження (2) і (3). Підсумуємо відповідно ліві та праві частини систем рівнянь (2) і (3). Матимемо:
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij}^{\ast } } } =\sum\limits_{i=1}^m {a_{i} }
(6)
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij}^{\ast } } } =\sum\limits_{j=1}^n {b_{j} }
(7)
Оскільки ліві частини рівнянь (6) та (7) збігаються, то пра-ві також рівні одна одній, отже, виконується умова:
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {a_{i} }
Неможливо розібрати вираз (невідома помилка): =\sum\limits_{j=1}^n {b_{j} }
(8)
Достатність. За умовою Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {a_{i} }
Неможливо розібрати вираз (невідома помилка): =\sum\limits_{j=1}^n {b_{j} }
= W > 0. Розглянемо величини Неможливо розібрати вираз (невідома помилка): x_{ij} =\frac{a_{i} b_{j} }{W}
Неможливо розібрати вираз (невідома помилка): \left( {i=\overline {1,m} ;\,\,\,j=\overline {1,n} } \right)
.
Підставивши значення Неможливо розібрати вираз (невідома помилка): x_{ij}
в систему обмежень задачі (1)—(4), матимемо:
Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {x_{ij} } =\sum\limits_{j=1}^n {\frac{a_{i} b_{j} }{W}=\frac{a_{i} }{W}\sum\limits_{j=1}^n {b_{j} } =} \frac{a_{i} }{W}W=a_{i}
Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {x_{ij} } =\sum\limits_{i=1}^m {\frac{a_{i} b_{j} }{W}=\frac{b_{j} }{W}\sum\limits_{i=1}^m {a_{i} } =} \frac{b_{j} }{W}W=b_{j}
Оскільки умови (2) та (3) виконуються, то Неможливо розібрати вираз (невідома помилка): x_{ij} =\frac{a_{i} b_{j} }{W}
Неможливо розібрати вираз (невідома помилка): \left( {i=\overline {1,m} ;\,\,\,j=\overline {1,n} } \right)
є планом наведеної транспортної задачі.
Виберемо з елементів Неможливо розібрати вираз (невідома помилка): c_{ij} \;\,\left( {i=\overline {1,m} ;\,j=\overline {1,n} } \right)
найбільше значення і позначимо його через Неможливо розібрати вираз (невідома помилка): \overline {c } =\max \,c_{ij}
. Якщо замінити в цільовій функ¬ції (1) всі коефіцієнти на , то, враховуючи (2), матимемо:
