Умова існування розв’язку ТЗ

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
      Теорема: необхідною і достатньою умовою існування розв’язку транспортної задачі (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)