Определение двойственных оценок однородной задачи линейного программирования симплекс-методом.
31) Транспортная задача линейного программирования, ее математическая модель.
Под названием транспортная задача объединяется широкий круг задач ЛП с единой математической моделью, т.к. это задача ЛП, то для ее решения может применятся один из уже известных методов( симплексный, двойственный, искусственный базис) Однако, в силу специфики мат. модели для их решения был разработан специальный метод- метод потенциала. Данный метод, как и симплексный, начинается с поиска начального решения, затем найденное решение проверяется на оптимальность и при необходимости осуществляется построение более оптимального плана.
Постановка задачи:
Однородный груз сосредоточен у m поставщиков А1, А2…..Am в объемах а1, а2…аm.
Данный груз необходимо доставлять n потребителям В1, В2…Вn, которые формируют заявки на груз в объемах в1, в2…вn.
Известны затраты (тарифы) на перевозку единицы груза от i-го поставщика J-му потребителю.
Сij( i=1,m , j=1,n)- затраты на перевозку.
Требуется составить такой план перевозки, при котором запасы всех поставщиков будут вывезены, заявки всех потребителей удовлетворены, а суммарные затраты на перевозку всех грузов будут минимальны.
Занесем все условия задачи в специальную транспортную таблицу
| Потребит поставщ | B1 | B2 | … | Bn | Запасы ai |
| A1 | c11 x11 | c12 x12 | … | c1n x1n | a1 |
| A2 | c21 x21 | c22 x22 | … | c2n x2n | a2 |
| … | … | … | … | … | … |
| Am | cm1 xm1 | cm2 xm2 | … | cmn xmn | am |
| Спрос bj | b1 | b2 | … | bn | ∑ai(i=1,m) ∑bj(j=1,n) |
Математическая модель транспортной задачи:
Пусть Х= х11 х12… х1n
х21 х22… х2n
………………………
xm1 xm2…xmn
- это план перевозки грузов
от каждого поставщика к каждому потребителю хij≥0 (i=1,m; j=1,n)
Суммарные затраты на перевозку грузов будут составлять ∑∑сij xij.
Поскольку эти затраты нужно минимизировать, то имеем целевую функцию
F(X)= ∑∑cij xij->min
Груз, выводимый от одного поставщика, определяется суммой всех переменных по строке
∑ xij( j=1,n).
И так как весь груз должен быть выведен, то эта сумма должна равняться запасам поставщика
∑xij=ai( j=1,n) i=1,m.
Груз, направляемый одному потребителю, т.е. сумма переменных по столбцу должен полностью удовлетворять его потребностям
∑xij= bj (i=1,n)
J=1,n
Т.о. математическая модель задачи принимает вид: найти оптимальный план перевозки грузов от поставщиков к потребителям, минимизирующие затраты на перевозку
F(x)= ∑∑cij xij->min при ограничениях:
∑хij=ai(j=1,n)
∑xij=bj(i=1,m)
xij≥0
32)Открытая и закрытая модели транспортной задачи. Приведение открытой модели к закрытой.
Модель ТЗ называется закрытой(задача с правильным балансом), если суммарные запасы поставщиков совпадают с суммарным спросом потребителей.
Если данное условие не выполняется, т.е. ∑ai≠∑bj (i=1,m, j=1,n) , то модель открытая, а задача с неправильным балансом.
Открытую модель необходимо привести к закрытому виду, при этом возможно 2 случая:
1) ∑ai>∑bj (i=1,m. j=1,n) запасов больше, чем заявок. В этом случае вводят фиктивного потребителя Вn+1, который формирует спрос на груз в объеме bn+1=∑ai-∑bj( i=1,m j=1,n).
Тарифы данного потребителя считаем равными нулю.
2) ∑ai< ∑ bj( i=1, m j=1,n) спрос превышает имеющиеся запасы, в этом случае вводят фиктивного поставщика Am+1,запасы которого составляют am+1= ∑bj- ∑bi( j=1,n i=1,m).
Тарифы для данного поставщика равны нулю.
После того, как задача приведена к закрытому виду можно приступать к поиску начального опорного решения.