Відмінності між версіями «Умова існування розв’язку ТЗ»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 15 проміжних версій цього учасника)
Рядок 10: Рядок 10:
 
=\sum\limits_{j=1}^n {b_{j} }
 
=\sum\limits_{j=1}^n {b_{j} }
 
</math>                                    (7)
 
</math>                                    (7)
 +
 +
Оскільки ліві частини рівнянь (6) та (7) збігаються, то пра-ві також рівні одна одній, отже, виконується умова:
 +
 +
<math>\sum\limits_{i=1}^m {a_{i} }</math> <math>=\sum\limits_{j=1}^n {b_{j} }</math>                      (8)
 +
 +
Достатність.
 +
За умовою  <math>\sum\limits_{i=1}^m {a_{i} }</math> <math>=\sum\limits_{j=1}^n {b_{j} }</math> = W > 0. Розглянемо величини <math>x_{ij} =\frac{a_{i} b_{j} }{W}</math> <math>\left( {i=\overline {1,m} ;\,\,\,j=\overline {1,n} } \right)</math>.
 +
 +
Підставивши значення <math>x_{ij}</math> в систему обмежень задачі (1)—(4), матимемо:
 +
 +
<math>\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}
 +
</math>;
 +
 +
<math>\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}
 +
</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) всі коефіцієнти на <math>\overline {c }</math> , то, враховуючи (2), матимемо:
 +
 +
<math>\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \le \overline c
 +
\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij} } } =\overline c
 +
\sum\limits_{i=1}^m {a_{i} } =\bar{{c}}W
 +
</math>.
 +
 +
Виберемо з елементів <math>c_{ij} \;\,\left( {i=\overline {1,m} ;\,j=\overline {1,n} } \right)</math> найбільше значення і позначимо його через <math>\underline{c}=\min \,c_{ij}</math>. Якщо замінити в цільовій функції (1) всі коефіцієнти на <math>\underline{c}</math> , то, враховуючи (2), матимемо:
 +
 +
<math>\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \ge
 +
\underline{c}\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij} } }
 +
=\underline{c}\sum\limits_{i=1}^m {a_{i} } =\underline{c}W
 +
</math>
 +
 +
Тобто цільова функція на множині допустимих планів транс-портної задачі є обмеженою:
 +
 +
<math>\underline{c}W\le</math> <math>\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \le \bar{{c}}W</math>.
 +
 +
Теорему доведено.

Поточна версія на 15:53, 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) всі коефіцієнти на Неможливо розібрати вираз (невідома помилка): \overline {c }

, то, враховуючи (2), матимемо:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \le \overline c \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij} } } =\overline c \sum\limits_{i=1}^m {a_{i} } =\bar{{c}}W .

Виберемо з елементів Неможливо розібрати вираз (невідома помилка): c_{ij} \;\,\left( {i=\overline {1,m} ;\,j=\overline {1,n} } \right)

найбільше значення і позначимо його через Неможливо розібрати вираз (невідома помилка): \underline{c}=\min \,c_{ij}

. Якщо замінити в цільовій функції (1) всі коефіцієнти на Неможливо розібрати вираз (невідома помилка): \underline{c}

, то, враховуючи (2), матимемо:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \ge \underline{c}\sum\limits_{i=1}^m {\sum\limits_{j=1}^n {x_{ij} } } =\underline{c}\sum\limits_{i=1}^m {a_{i} } =\underline{c}W


Тобто цільова функція на множині допустимих планів транс-портної задачі є обмеженою:

Неможливо розібрати вираз (невідома помилка): \underline{c}W\le

Неможливо розібрати вираз (невідома помилка): \sum\limits_{i=1}^m {\sum\limits_{j=1}^n {c_{ij} x_{ij} } } \le \bar{{c}}W

.

Теорему доведено.