Балансировка задач

Для 2-ой ситуации:

Вводится фиктивный B_n+1 потребитель. В таблице будет добавлен еще один столбец.

Транспортные тарифы у фиктивного потребителя будут равны 0, т.к. реальных перевозок груза к нему осуществляться не будет, таким образом, в группе ограничений по поставщикам будет добавлено ограничение:

Для 3-ей ситуации: для балансировки будет добавлен фиктивный поставщик - A_m+1

В таблице добавится еще одна строка, транспортные тарифы будут также равны 0.

При балансировке ТЗ 2-ой и 3-ей случаев возникает неудовлетворенность некоторых потребителей или невывезенный груз у некоторых поставщиков. Среди них могут оказаться: те потребители, потребность которых обязательно нужно удовлетворить или те поставщики, груз у которых нужно обязательно вывезти. В этом случае применяется метод ЗАПРЕЩЕНИЯ ПЕРЕВОЗОК. Тогда транспортные тарифы для перевозки грузов поставщиков и потребителей принимаются равными не 0, а числу M.

№19 метод с-з угла. Вырожденный план. Правильность расстановки нулей

Т.з. решаются в 2 этапа. На 1 ом шаге строится исходный план т.з. На 2м шаге – находим оптимальный план т.з. Основные методы построения исходного плана:

1) метод сев-западного угла

2) метод мин элемента. Метод потенциала – для нахождения оптимального плана.

ТЗ содержит m•n переменных и m+n ограничений за исключением условий неотрицательности.

Любое ограничение ТЗ является линейной комбинацией остальных => сис-ма ограничений ТЗ линейно зависима и содержит только m+n-1 независимых уравнений. Поэтому исходный допустимый невырожденный базисный план должен иметь m+n-1 базисную переменную. И его можно получить из данной таблицы. Все остальные переменные будут небазисными, их значение =0, в тр.таблице их значения не отражаются.

Вырожденный и невырожденный план.

Если кол-во базисных клеток = m+n-1, то план является невырожденным. Если кол-во базисных (запасы) клеток < m+n-1, то план – вырожденный.

Чтобы превратить вырожд план в невырожд в базис вводят новые перменные с минимальными транспортными тарифами, значении к-х принимается равным 0 до тех пор, пока кол-во заполн клеток не станет = m+n-1. Однако при расстановке нулей необходимо помнить, что в трансп.таблице не должно быть ни одного прямоугольника, вершины которого являются заполненными клетками.

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

Значение переменной х11 соответствует 1ому поставщику, 1 ому потребителю из значений а1 и b1 выбирают минимальное:

а) а1<b1 => x11=a1 и первая строка транспортной таблицы исключается из дальнейшего рассмотрения. А потребность в грузе 1 ого потребителя b1 уменьшается на наличие груза у 1ого поставщика на а1

б) а1>b1 =>x11=b1, 1ый столбец исключается из дальнейшего рассмотрения, а наличие груза у 1ого поставщика а1 уменьшается на b1.

в) а1=b1 1ый столбец и 1ая строка исключаются. Это чаще всего приводит к появлению вырожденного плана.

Берётся самая с 3 клетка и аналогичные действия проводятся с остальными.

На последнем шаге процесса останется 1 строка и 1 столбец. После заполнения клетки, стоящей на их пересечении процесс завершён. Далее исходный план проверяется на вырожденность. Если план – вырожденный, необходимо привести его к невырожденному.

№20 Использование метода минимального элемента для построения исходного плана