Транспортная задача с открытой моделью. Способ решения

 

     Так как для закрытой модели транспортной задачи , то полученные нами уравнения одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

     Итак, преобразование системы свелось  к замене двух уравнений (первого  горизонтального и первого вертикального) уравнение. Остальные уравнения  остаются неизменными. Система приняла вид

 

     В системе выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного . В системе имеется уравнений, выделенный базис содержит неизвестных, а, следовательно, и ранг системы .

     Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы , т. е. стоимость перевозки единицы груза с базы потребителю .

     Совокупность  тарифов  также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу (приложение Б).

     Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных :

     Требуется в области допустимых решений  системы уравнений и найти  решение, минимизирующее линейную функцию.

     Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.

     Замечание 2. Под величинами , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой, является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

     Таким образом, мы видим, что транспортная задача является задачей линейного  программирования. Для ее решения  применяют также симплекс-метод, но в силу специфики задачи здесь  можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений⁸. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

     Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Решение транспортной задачи с открытой моделью  на примере метода минимального элемента

      Чтобы решить транспортную задачу с открытой моделью, необходимо преобразовать  её в модель закрытую, т.е. где  . Если суммарный груз превышает суммарные потребности, то тогда добавляют фиктивного потребителя, т.е в таблицу добавляют дополнительный столбец с нулевыми тарифами. Если объем поставок меньше чем объем груза, который нужен потребителю, в таблицу добавляется ещё одна строка с нулевыми показателями.

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

     Пример 

     Составить первоначальный опорный план методом  минимального элемента для транспортной задачи вида:

 

     Решение:

     Задача  сбалансирована.

     Строим  первоначальный опорный план методом  минимального элемента.

1. Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;
4. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

     Опорный план имеет вид; 

 
 
 
 
 
 
 
 
 

Заключение

     В работе изложены основные подходы и  метод решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки⁹. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

     Алгоритм  и методы решения транспортной задачи могут быть использованы при решении  некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи¹⁰. К таким задачам относятся следующие:

     - оптимальное закрепление за станками  операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;

     - оптимальные назначения, или проблема  выбора. Имеется m механизмов, которые  могут выполнять m различных работ  с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

     - задача о сокращении производства  с учетом суммарных расходов  на изготовление и транспортировку  продукции;

     - увеличение производительности  автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;

     - решение задач с помощью метода  запрещения перевозок. Используется  в том случае, если груз от  некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки¹¹. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Список использованных источников

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
2. Баумоль У. Экономическая теория и исследование операций. – М.; Наука, 2004.
3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
4. Боровков А.А. Математическая статистика. М.: Наука, 2004.
5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.
7. Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.
8. Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.
9. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. – 3-е изд., исп. – М.: Дело, 2002.
10. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005
11. Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003.
12. Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
13. Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебное пособие. - Димитровград, 2002.

 
 
 
 
 

Приложения

Приложения  А Таблица перевозок