2015-05-13
356
Симплексный метод - универсальный для решения любых задач линейного программирования. Однако отдельные типы задач линейного программирования (например, транспортные) в силу своей специфики могут быть решены более простыми методами.
Транспортная задача формулируется следующим образом: имеется n поставщиков однородного груза A, j-й поставщик имеет запас груза 
, (j=l,2,...,n) и m потребителей, i-й потребитель имеет потребность в грузе 
(i=1,2,...,m). Затраты на перевозку груза от j-го поставщика к i-му потребителю составляют сij. Требуется определить объемы грузоперевозок от j-го поставщика к i-му потребителю хij, при которых достигается минимальная суммарная стоимость перевозок.
Модель задачи имеет следующий вид.
Минимизировать целевую функцию
(4.1)
при ограничениях:
(4.2),
(m- ограничений),
(4.3),
(n- ограничений).
Рассматривается закрытая модель, для которой справедливо:
(4.4),
т.е. суммарные запасы груза равны потребности в нем. Любая задача может быть сведена к закрытой путем введения фиктивного поставщика или фиктивного потребителя.
|
|
|
Транспортная задача имеет следующие особенности:
· все ограничения имеют вид равенств;
· каждая переменная входит всего в два ограничения;
· коэффициенты при переменных в ограничениях равны единице.
Благодаря этим особенностям транспортная задача может быть решена более простым способом, чем симплексный.
Для решения транспортной задачи составляют специальную матрицу (таблица 4.1), причем в этой матрице построчно записаны ограничения по запасам сырья у поставщиков, а по столбцам – по потребности каждого потребителя.
Таблица 4.1
| Поставщик j | Потребитель i | Запасы груза А ( )
| ||||
| … | i | … | m | |||
| c11 x11 | c1i x1i | c1m x1m | 
| |||
| … | ||||||
| j | cj1 xj1 | cji xji | cjm xjm |
| ||
| … | ||||||
| n | cn1 xn1 | cni xni | cnm xnm | 
| ||
Потребность в грузе А ( )
| 
|
| 
|
