Транспортная задача линейного программирования

Размещено на http://www.allbest.ru/

Введение

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

Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования. Исходя из этого, объектом исследования в рамках курсовой работы стала область применения методов линейного программирования при решении экономических задач, а предметом - ее применение на конкретном предприятии.

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

Цель курсовой работы - освоить математическую постановку транспортной задачи линейного программирования и методы нахождения ее первоначального опорного и оптимального плана.

Задачи:

1) рассмотреть актуальность и значимость минимизации транспортных затрат на предприятии;

2) изучить методы решения транспортной задачи;

3) применить полученные знания к решению конкретной задачи;

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

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

Информационной базой для написания курсовой работы послужили популярные учебные пособия отечественных авторов: Алесинской Т.В. - Учебное пособие по решению задач по курсу «Экономико-математические методы и модели», А.И. Орлова - «Теория принятия решений», «Исследование операций в экономике» под редакцией Н.Ш. Кремера и другие.



1. Актуальность и значимость минимизации транспортных затрат торгового предприятия

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т. п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Во многих снабженческих, транспортных и других организациях во всем мире рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями, например, в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции, оптимизируется доставка грузов с промежуточными базами (складами).

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

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

1) нужный товар;

2) необходимого качества;

3) в необходимом количестве доставлен;

4) в нужное время;

5) в нужное место;

6) с минимальными затратами.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

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

К таким задачам относятся следующие:

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

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

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

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

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

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



2. Транспортная задача линейного программирования

2.1 Постановка задачи и ее математические модели

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз потребителям .

Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени). Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно , а общее количество имеющегося в наличии груза :

Заказы каждого из потребителей (потребности) обозначим соответственно, а общее количество потребностей - :



Тогда при условии .

мы имеем закрытую модель, а при условии .

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

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

План перевозок с указанием запасов и потребностей удобно записывать в виде таблицы, называемой таблицей перевозок (Таблица 2.1).

Таблица 2.1 - План перевозок с указанием потребностей и запасов:

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

Очевидно, переменные должны удовлетворять условиям:



Система содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

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

При таком выборе базиса, по крайней мере, один из двух их индексов равен единице.

Следовательно, свободные неизвестные определяются условием , .

Перепишем систему в виде:



Где символы и означают суммирование по соответствующему индексу. Так, например:

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

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

Или короче:



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

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

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

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



Следовательно, и ранг системы:

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

Таблица 2.2 - Совокупность тарифов, объединенная с матрицей перевозок и данными о запасах и потребностях:

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

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

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

То среди всех неизвестных выделяется элемент базисных неизвестных, а остальные (m-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми.

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

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

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

2.2 Методы определения первоначального опорного плана

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

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

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

Начиная с первоначально данной таблицы и повторив:



Раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, мы и получим искомый опорный план.

Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная “потребность” в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль (“запас” или “потребностью” - безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.

Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки:

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



Таблица 2.3 - Пример составления первоначального опорного плана методом северо-западного угла:

Заполнение таблицы начинается с ее северо-западного угла, т. е., клетки с неизвестным . Первая база может полностью удовлетворить потребность первого заказчика:

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

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

Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .

Теперь переходим к заполнению клетки для неизвестного и т. д.

Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными . Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам. Общий объем перевозок в тонно-километрах для этого плана составит:

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

Таблица 2.4 - Пример составления первоначального опорного плана методом наименьшей стоимости:



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

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

Третья база может полностью удовлетворить потребность второго заказчика .

Полагая , вписываем это значение в клетку и исключаем из рассмотрения второй столбец.

На базе остается изменённый запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами клеткой с наименьшим значением клетка, где . Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки:

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

Можно было выбрать для заполнения другую клетку, положив , что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит:

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

3. Метод аппроксимации Фогеля.

Шаг 1. Составляют транспортную таблицу.

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

Шаг 3. В строке или в столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. Переход к шагу 4.

Шаг 4. В выбранную клетку, аналогично предыдущим методам, записывают максимально возможное число единиц продукции, которое разрешается ограничениями на предложение и спрос. После этого вычеркивают либо строку, если предложение поставщика исчерпано, либо столбец, если спрос потребителя удовлетворен.

Если все клетки таблицы заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета вычеркнутых и заполненных клеток.

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

Таблица 2.5 - Пример нахождения начального плана методом аппроксимации Фогеля:



Разности по строкам будем записывать в правой части табл. 2.5, разности по столбцам - внизу табл. 2.5. Максимальную разность будем отмечать кружком. Наименьший тариф в первой строке равен 1. Ближайший к нему равен 3. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1. В первом столбце наименьший тариф c₂₁ = 4. Во втором столбце наименьшее значение c₃₂ = 3. Третий столбец: с₁₃ = 1. Четвертый столбец: с₁₄ = 2.

Максимальная из всех разностей 4 находится в четвертом столбце. В этом столбце клетка с наименьшим тарифом с₁₄ = 2 находится в первой строке. В эту клетку помещаем максимально возможное значение: х₁₄ = min(110,160) = 110. Четвертый потребитель полностью удовлетворил свой спрос, и четвертый столбец вычеркиваем.

Повторяем предыдущие действия без учета вычеркнутых и заполненных клеток.

Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке с₁₃ = 1. В эту клетку помещаем х₁₃ = min(160 -110,190) = 50. Вычеркиваем первую строку.

Повторяем все действия без учета первой строки и четвертого столбца.

Максимальная разность равна 6 и стоит в третьем столбце. Минимальный из оставшихся тарифов в этом столбце с₃₃ = 3. Спрос третьего потребителя удовлетворен, третий столбец вычеркиваем. Вновь составляем разности для не вычеркнутых строк и столбцов. Максимальная разность стоит в третьей строке. Минимальный тариф в этой строке с₃₂ = 2. Предложение поставщика исчерпано, и третью строку вычеркиваем.

Осталась одна строка транспортной таблицы. Это вторая строка.

В этой строке сначала заполняем клетку с наименьшим тарифом c₂₁ = 4.

Оставшееся предложение второго поставщика записываем в единственную свободную клетку х₂₂ = min.

Полученный по методу Фогеля план перевозок имеет вид:

Затраты на перевозку по этому плану составляют:

S₃ = 50 * 1 + 110 * 2 + 120 * 4 + 20 * 5 + 30 * 2 + 140 * 3 = 1430.

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

При этом затраты на перевозки уставляют соответственно:

S₁ = 3220;

S₂ = 1530;

S₃ = 1430.

Метод Фогеля наиболее трудоемкий, однако начальный план перевозок, построенный с его использованием, обычно бывает близок к оптимальному плану.

В некоторых случаях является оптимальным планом.

2.3 Понятие цикла при решении транспортной задачи

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

Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

Одно из неизвестных последовательности свободное, а все остальные - базисные.

Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

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

Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

Например, в указанном выше цикле для свободного неизвестного получим:

Очевидно, если снабдить вершины цикла поочередно знаками “+” и “-“, приписав вершине в свободной клетке знак “+”, то можно сказать, что в вершинах со знаком “+” число прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком “-“ это число вычитается из прежнего значения неизвестного, находящегося в этой вершине.

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

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

Так, например, в рассмотренном выше цикле имеем отрицательные вершины и .

Следовательно вместо прежнего базисного решения получаем новое базисное решение, представленное в Таблице 2.6.



Таблица 2.6 - Получение нового базисного решения с помощью цикла:

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

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

Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.

Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.

Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета. Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше. Пусть - некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом . Если вершине цикла, находящейся в строке и столбце таблицы перевозок, приписан знак “+”, то значение неизвестного , находящегося в этой вершине, увеличивается на , что в свою очередь вызывает увеличение затрат на . где - тариф, соответствующий этой клетке, если же указанной вершине приписан знак “-”, то значение неизвестного уменьшается на , что вызывает уменьшение затрат на . Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла, полученную разность назовем алгебраической суммой тарифов для данного свободного неизвестного . Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).

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

Так, например, для цикла в рассмотренной задаче алгебраическая сумма тарифов:



Значит, пересчет по этому циклу снижает расходы. И действительно, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет:

.

Тогда как по исходному плану он составил . Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна -15, а пересчет по циклу осуществляется с помощью числа (изменение затрат равно ).

2.4 Методы определения оптимального плана транспортной задачи

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

Так что:

Где:

- тарифы, соответствующие клеткам, заполненным базисными неизвестными.

Эти числа и называются потенциалами соответствующих баз и потребителей.

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

Так, например, для цикла в рассмотренной выше задаче имеем:

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

Называют косвенным тарифом этой клетки. Следовательно, алгебраическая сумма тарифов для свободной клетки равна разности ее настоящего (“истинного”) и косвенного тарифов:



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

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

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

Затем из четвертого уравнения:



Из пятого уравнения:

Из шестого уравнения:

И, наконец, из седьмого уравнения:

Положив, например, , получаем значения потенциалов:

Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами:

Для клеток с неизвестными и косвенные тарифы больше истинных.

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

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

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

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

Критерий оптимальности базисного решения транспортной задачи.

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

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

Через конечное число шагов приходят к искомому оптимальному базисному решению.

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

Задача, двойственная к транспортной.

Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления и назначения отвечает определенное ограничение:

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

Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления , через , а пункту назначения - через .

Поэтому соответствующее ограничение в двойственной задаче имеет вид:

Правая часть неравенства равна , потому что именно с этим коэффициентом неизвестная . Оптимизируемая форма двойственной задачи имеет вид:

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

Подчеркнем, что знак значений неизвестных и может быть произвольным.

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

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



- для всех свободных неизвестных .

Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.



3. Применение транспортной задачи на примере конкретного торгового предприятия

В городе N имеется 3 склада Аi, на которых хранится ткань (в рулонах) и 4 магазина Bj, занимающихся продажей ткани. Ниже, в Таблице 3.1, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.

Таблица 3.1 - Количество рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj:

Математическая модель транспортной задачи:

F = ?? * c_ijx_ij

Проверим необходимое и достаточное условие разрешимости задачи:

?a = 45 + 50 + 53 = 148.

?b = 31 + 40 + 44 + 20 = 135.

Как видно, суммарная потребность груза в магазинах превышает запасы груза на складах.

Следовательно, модель исходной транспортной задачи является открытой.

Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 13 (148-135). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Занесем исходные данные в распределительную таблицу.

Таблица 3.2 - Исходные данные для задачи:

Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла:

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.



Таблица 3.3 - Опорный план, полученный методом северо-западного угла:

Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 1 * 31 + 4 * 14 + 4 * 26 + 2 * 24 + 6 * 20 + 3 * 20 + 0 * 13 = 419.

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

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

1) Искомый элемент равен 1.

Для этого элемента запасы равны 45, потребности 31.

2) Искомый элемент равен 2.

Для этого элемента запасы равны 50, потребности 44.



Таблица 3.4 - Опорный план, полученный методом наименьшей стоимости:

Таблица 3.5 - Потенциалы по занятым клеткам:



Заключение

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

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

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

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

экономический математический минимизация



Список используемой литературы

1. Акулич И.Л. Математическое программирование в примерах и задачах. / И.Л. Акулич. - Минск: Высшая школа, 2004 год.

2. Алесинская Т.В. Учебное пособие по решению задач по курсу «Экономико-математические методы и модели». Таганрог: Изд-во ТРТУ, 2002.

3. Гельман В.Я. Решение математических задач средствами Excel: Практикум. / В.Я. Гельман. - СПб.: Питер, 2003. - 237 с.

4. Ермаков В.И. “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2008 г.

5. Зайченко Ю.П. Исследование математических операций 1979 г.

6. Иванов Ю.П., Лотов А.В. Математические модели в экономике. / Ю.П. Иванов. - М., Наука, 1978 год.

7. Карасев А.Н., Кремер Н.Ш., Савельева Т.Н. “Математические методы в экономике”, М. 2000.

8. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе. Учебник-3-е изд., исп. - М. Дело, 2009. - 688 с.

9. Кузнецов, А.Г., Новикова, Г.И., Холод И.И. Высшая математика. Математическое программирование. / А.Г. Кузнецов, Г.И. Новикова, И.И. Холод. - Минск: Высшая школа, 2001 год.

10. Лунгу К.Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005. - 128 с.

11. Моисеев, Н.Н., Иванов, Ю.П., Столяров, Е.М. Методы оптимизации. / Н.Н. Моисеев, Ю.П. Иванов, Е.М. Столяров. - М., Наука, 2008.

12. Орлов А.И. Теория принятия решений: Учебное пособие. - М.: Издательство «Март», 2004.

Размещено на Allbest.ru

...