Симплексный метод - универсальный для решения любых задач линейного программирования. Однако отдельные типы задач линейного программирования (например, транспортные) в силу своей специфики могут быть решены более простыми методами.
Транспортная задача формулируется следующим образом: имеется 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 | |||
Потребность в грузе А () |