Определение двойственных оценок однородной задачи линейного программирования симплекс-методом.

 

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).

Тарифы для данного поставщика равны нулю.

После того, как задача приведена к закрытому виду можно приступать к поиску начального опорного решения.