15. Економічна постановка і математична модель закритої транспортної задачі (тз). Властивості планів тз.

ТЗ назыв.закрытой, если сумм.спрос=сумм.предложению В закрытых моделях полностью исчерпываются запасы и полностью удовлетворяются потребности. Такая задача может быть решена при помощи симплекс-метода, но существуют менее громоздкие методы решения. Наиболее приемлемым является метод потенциалов.

Свойства планов ТЗ. Одна из важнейших особенностей ТЗ состоит в том, что любая ТЗ имеет решение. Доказательство. При изучении свойств ЗЛП были рассмотрены случаи, когда ЗЛП не имеет решения: I) система основных ограничений несовместна, т.е. множество решений ЗЛП пусто; 2) целевая функция ЗЛП, решаемой на минимум целевой функции, не ограничена снизу.

I. Докажем, что множество планов ТЗ не пусто. Для этого обозначим ∑ai=∑=Q и рассмотрим набор чисел {xij}, где xij=aibj/Q. Так как ai и bj как экономические категории положительны, а следовательно, ai,bj и Q>0, то xij>0. Таким образо, условие неотрицательности выполняется. Непосредственной подстановкой набора {xij}в ∑xij=ai(i=1,m) и ∑xij=bj(j=1,n) убеждаемся, что этим условием он удовлетворяет удовлетворяет. Действительно, например, ∑xij=∑aibj/Q=bj*(∑i)/Q=bj*(Q)/Q=bj.

Итак, набор{xij} является планом ТЗ, следовательно, множество планов ТЗ не пусто.

II. Докажем, что целевая функция z=∑∑cijxij(min) ограничена снизу. Рассмотрим коэффициенты cij и среда них выберим наименьший c=min{cij}. ТОгла cij≥c. Умножая неравенство на xij>0, получаем cijxij≥cxij.Просуммировав по i и j, получим z=∑∑cijxij≥∑∑cxij=c∑bj=cQ.

Итак, z≥cQ=const, т.е. ограничено снизу.

16. Економічна постановка і математичні моделі відкритих тз. Зведення їх до закритої тз. Інтерпретація додаткових змінних.

В открытой модели транспортные задачи имеют нарушенный баланс, то есть общие запасы превышают общие потребности или общие потребности превышают общие запасы, то есть: когда сумм. предложение превышает сумм. спрос , удовлетворение спроса потребителей не сопровождается полным вывозом товара от поставщиков. Эконом. постановка: составить план перевозок, при котором потребности всех потребителей удовлетворены, от поставщиков вывозятся товары в количествах, не превышающих их мощности, и сумм. сто - ть перевозок является мин. Вводим фиктивного потребителя. Матрица тарифов увеличивается на 1 столбец. Было n потребителей стало n+1 потребителей и в матрице тарифов появляется нулевой столбец. Перевозка к фикт. потребителю осуществляется в последний момент. Мат модель: ∑xij=bj(j=1,n); ∑xij ≤ ai (i=1,m)

Сум. спрос больше сумм. предложения - невозможно удовлетворить спрос всех потребителей. Эконом. постановка: составить план перевозок, при котором весь товар от всех поставщиков вывозится, спрос потребителей по возможности удовлетворяется и сумм. транспортные расходы –минимальны. Мат.модель-∑xij=ai(i=1,m); ∑xij≤bj(j=1,n)

17. Характеристика методу розв'язання тз і його порівняння із см. Методи складання початкового опорного плану. Умова, при якій план перевезень буде опорним.

ТЗ является ЗЛП, следовательно, её можно решить симплекс-методом! Однако в случае 3 поставщиков и 4 потребителей размерность задачи достаточно большая, следовательно задача окажется громоздкой.

Существует специфический метод решения ТЗ, основанный на использовании так званой таблицы планирования перевозок. Этот метод состоит из 3 этапов: 1)составление начального опорного плана; 2)оценки оптимальности; 3)переход от одного плана к лучшему. В таблице планирования перевозок записываются поставщики и их мощности, потребители и их спрос. На пересечении i-той строки и j-го столбца находиться клетка, называемая маршрутом и отражающая связь между Ai и Bj. Она делится на две части. В верхней част и записывается тариф, в нижней- планируемый объём перевозок по данному маршруту xij.

Методы:северо-западного угла.

Х11=min(ai;bj) Клетка становится занятой – базисной. Если удовлетворен покупатель то столбец закрывается, если все со склада вывезли то закрывается строка. И.т.д.

Если баланс по строкам и столбцам выполняется и число клеток (занятых) совпадает с рангом матрицы то получаем допустимый план. Но данный опорный план может быть далеким от оптимального, потому что не берутся в расчет расходы. Поэтому используют для этого метод минимального элемента.

Если в середине таблицы одновременно закрывается строка и столбец , а число занятых клеток не равно рангу, то в следующую клетку ставят 0 базисный и клетка считается занятой.