19

Содержание

Введение              4

1. Теоретическая часть              6

1.1. Оптимизационные задачи и модели              6

1.2. Транспортные задачи              7

1.3. Методы решения транспортной задачи              9

1.3.1 Диагональный метод, или метод северо-западного угла              9

1.3.2 Метод минимального элемента              10

1.3.4 Метод наименьшей стоимости              10

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

1.3.6 Метод потенциалов как метод решения транспортной задачи              14

1.4. Выводы по главе              17

2. Практическая часть              19

2.1. Постановка транспортной задачи              19

2.2. Решение задачи в MS Excel              21

2.3. Решение задачи в MathCAD              23

2.4. Выводы по главе              25

Заключение              27

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

Приложения              31

Введение

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

Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования [2].

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

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

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

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

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

1. Теоретическая часть

1.1. Оптимизационные задачи и модели

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

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

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

      управляемых переменных;

      неуправляемых переменных;

      формы функции (вида зависимости между ними).

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

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

      на линейные и нелинейные;

      детерминированные и стохастические.

Стохастические ограничения являются возможными, вероятностными, случайными.

Задачи решаются методами математического программирования, которые подразделяются:

      на линейное программирование;

      нелинейное программирование;

      динамическое программирование;

      целочисленное программирование;

      выпуклое программирование;

      исследование операций;

      геометрическое программирование и др.

Главная задача математического программирования — это нахождение экстремума функций при ограничениях в форме уравнений и неравенств.[3]

1.2. Транспортные задачи

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

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi …, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Ai в пункт Вj, i 1, …, m; j 1, ..., n. Предположим, что

                                                                      (1),

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

Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой(1.2):

                                                                      (1.2)

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте(1.3).

, i 1, …, m                                                         (1.3)

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

, j 1, …, n                                                                        (1.4)

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

xij 0, i 1, ..., m; j 1, ..., n                                                         (1.5)

1.3. Методы решения транспортной задачи

1.3.1 Диагональный метод, или метод северо-западного угла

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

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

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

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

Общий объем перевозок в тонно-километрах для этого плана составит

.

1.3.2 Метод минимального элемента

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

1.3.4 Метод наименьшей стоимости

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

Таблица1.1

Первоначальный опорный план

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

1.3.6 Метод потенциалов как метод решения транспортной задачи

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj.

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи[9].

Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

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

Составим двойственную задачу

1. ,  - любые

2.

3.

Пусть есть план

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

      если ,                                                                 (1.6)

   если .                                                                (1.7)

числа  и называются потенциалами пунктов отправления  и назначения соответственно.

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

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

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия (1.7).

1.4. Выводы по главе

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

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

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

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

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

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

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

Таким образом, важность решения данной задачи для экономики несомненна.

2. Практическая часть

2.1. Постановка транспортной задачи

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

Далее, предполагается, что

                                                        (1)

где bi есть количество продукции, находящееся на складе i, и aj – потребность потребителя j.

Замечание. Если то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью и положим транспортные расходы pi,n+1 равными 0 для всех i.

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

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

В данной работе необходимо решить данную ниже транспортную задачу.

Три завода производят однородную продукцию в количествах 750, 950 и 800 единиц соответственно. Четыре потребителя нуждаются в этой продукции в количествах 550, 820, 370 и 700 единиц. Затраты на перевозку единицы продукции (тыс. руб.) от каждого завода к каждому потребителю заданы  таблицей 2.1.

Таблица 2.1

Затраты на перевозку единицы продукции

1.        Постройте оптимальный план перевозок  так, чтобы суммарные транспортные затраты были минимальными;

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

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

        Решение задачи необходимо выполнить в пакетах прикладных программ Microsoft Excel и MathCAD.

2.2. Решение задачи в MS Excel

Microsoft Excel (также иногда называется Microsoft Office Excel) — программа для работы с электронными таблицами, созданная корпорацией Microsoft для Microsoft Windows, Windows NT и Mac OS. Она предоставляет возможности экономико-статистических расчетов, графические инструменты и, за исключением Excel 2008 под Mac OS X, язык макропрограммирования VBA (Visual Basic для приложений). Microsoft Excel входит в состав Microsoft Office и на сегодняшний день Excel является одним из наиболее популярных приложений в мире.

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

После чего следует выбрать в Excel пункт меню Данные/Поиск решения, в окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения. Как правила используются ограничения следующего вида:

1.      Неотрицательность плановых значений;

2.      Равенство суммарного планового потребления спросу для всех пунктов потребления продукции;

3.      Равенство суммарного планового производства объему произодства для всех пунктов производства продукции;

4.      Иногда бывает необходимо задать целечисленные ограничения на плановые значения.

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

Довольно часто транспортная задача бывает представлена в так называемом несбалансированном виде (суммарная потребность превышает суммарное производство). В этом случае для приведения транспортной задачи к сбалансированному виду следует добавить в таблицу фиктивный пункт производства или потребления [14].

Для решения поставленной задачи воспользуемся пакетом Microsoft Excel версии 2007, входящий в состав Microsoft Office 2007. Процесс решения разбиваем на три этапа:

                 разметка рабочего листа;

                 ввод исходных параметров;

                 ввод ограничений и запуск мастера поиска решений

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

Рис. 2.1. Окно «Поиск решения»

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

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

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

2.3. Решение задачи в MathCAD

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

Mathcad был задуман и первоначально написан Алленом Раздовом из Массачусетского технологического института (MIT), соучредителем компании Mathsoft, которая с 2006 года является частью корпорации PTC (Parametric Technology Corporation).

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

Некоторые из математических возможностей Mathcad (версии до 13.1 включительно) основаны на подмножестве системы компьютерной алгебры Maple (MKM, Maple Kernel Mathsoft). Начиная с 14 версии — использует символьное ядро MuPAD.

Работа осуществляется в пределах рабочего листа, на котором уравнения и выражения отображаются графически, в противовес текстовой записи в языках программирования. При создании документов-приложений используется принцип WYSIWYG (What You See Is What You Get — «что видишь, то и получаешь»).

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

Mathcad достаточно удобно использовать для обучения, вычислений и инженерных расчетов. Открытая архитектура приложения в сочетании с поддержкой технологий .NET и XML позволяют легко интегрировать Mathcad практически в любые ИТ-структуры и инженерные приложения. Есть возможность создания электронных книг (e-Book).

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

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

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

Хочется отметить, что блок оператора «Given», работает в совокупности с функциями минимизации и максимизации в системе MathCAD.

В нашем случае блок «Given», будет завершен именно вызовом функции минимума «Minimize». При использовании данной функции необходимо учесть ряд параметров. Во-первых, функция должна формироваться написанием слово «Minimize», при этом очень важен регистр, начинающийся с заглавной буквы. Во-вторых, необходимо передать для работы функции как минимум два параметра (функция, переменная x), перечисляемые через запятую в скобках непосредственно после ключевого слова.

Итогом работы программы MathCAD, является вывод минимального значения функции. В нашем случае, данное значение  совпадает с вычислениями пакета Microsoft Excel.

Работу с программой завершаем сохранением рабочего листа в формате *xmcd, либо *mcd, но во втором случае мы рискуем потерять ряд возможностей более поздних версий программы, а формат *xcmd, сохраняет все возможности, правда он недоступен для открытия в более ранних версиях программы.

2.4. Выводы по главе

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

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

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

Заключение

     Исторически методы линейного программирования начали развиваться именно из анализа транспортных задач. Изучение транспортных задач имеет исключительное практическое значение, так как позволяет снизить транспортные расходы предприятия на 10 – 30 %,  и решить большое количество прикладных задач, описываемых математическими моделями, подобно моделям транспортных задач.

Методы линейного программирования делятся на две группы: универсальные и специальные.

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

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

- все ограничения заданы в виде уравнений;

- каждое неизвестное входит лишь в два уравнения;

- коэффициенты при неизвестных - единицы.

Среди этих методов наиболее известны:

- распределительный метод;

- модифицированный распределительный метод (или метод потенциалов), предложенный Л. В. Канторовичем и М. К.Гавуриним, позже, независимо от них, Дж. Данцигом;

- венгерский метод, предложенный Э. Эгервари и усовершенствованный X. Куном для решения частного случая транспортной задачи: задачи о назначении (или о выборе), а позднее обобщенный Дж. Манкресом на транспортную задачу общего вида;

- метод приложений А. Л. Лурье;

-  метод дифференциальных рент А. Л. Брудно.

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

MathCAD Конец формы

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

1.      Аттетков А.В. Введение в методы оптимизации: учеб. пособие / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. - М.: Финансы и статистика; ИНФРА-М, 2008. - 272 с.

2.      В.Е. Барбаумов,  В.И. Ермаков, Н.Н. Кривенцова, А.С. Лебедев, В.И. Матвеев, Б.М. Рудык, Е.А. Силаева, О.К. Смагина Справочник по математике для экономистов: Учебное пособие / Под редакцией профессора В.И. Ермакова. – 3-е изд., перераб. и доп. – М.: ИНФРА-М, 2007. – 464с. – (100лет РЭА им. Г.В. Плеханова).

3.      Введение в анализ, синтез и моделирование систем: Учебное пособие / В.М. Казиев – 2-е изд., - М.: БИНОМ, 2007. – 244 с.

4.      Дик В.В. Методология формирования решений в экономических системах и инструментальные среды их поддержки. –М: Финансы и статистика, 2001. – 300с.

5.      Коновцова М.М., Кошелев И.В. Информационные системы и технологии в экономике. Учебное пособие. Пятигорск: РИА-КМВ, 2010. – 176с.

6.      Коновцова М.М., Стрельцова Е.Ю. Имитационное моделирование экономических процессов. Учебное пособие. Пятигорск: РИА-КМВ, 2010. – 72с.

7.      Красс М.С. Математика в экономике. Математические методы и модели:   учебник / М.С. Красс, Б.П. Чупрынов. - М.: Финансы и статистика, 2007.-544 с.

8.      Красс М.С., Чупрынов Б.П. Математика для экономистов. – СПб.:Питер, 2008. – 464 с.

9.      Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие. – 3-е изд., перераб. и испр. / Б.А. Суслакова. – М.: Дашков и К, 2007. – 352 с.

10. Лавренов С.М. Excel: Сборник примеров и задач.- М.: Финансы и статистика, 2007. -  336 с.

11. Математика в экономике: Учебник: В 2-х ч. Ч.1,Ч.2 / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. - 2-е изд.,перераб. и доп. - М.: Финансы и статистика, 2007. - 944 с.

12. Мединов О.Ю. Excel. Мультемидийный курс (+DVD). – СПб.: Питер, 2009. – 208 с.

13. Минько А.А. Принятие решений с помощью Excel. Просто как дважды два / А.А. Минько. – М.: Эксмо, 2007. – 240с. – (Просто как дважды два).

14. Минько А.А. Прогнозирование в бизнесе с помощью Excel. Просто как дважды два / А.А. Минько. – М.: Эксмо, 2007. – 208с. – (Просто как дважды два).

15. Охорзин В.А. Оптимизация экономических систем. Примеры и алгоритмы в среде Mathcad: Учеб.пособие. -М.: Финансы и статистика,2008.-144 с.

16.    Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002. – С.140

         17.Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003. – С.92

          18. А.И., Сливина Н.А. Mathcad 2000. Математический практикум для экономистов и инженеров: Учебное пособие.- М.: Финансы и статистика, 2008 -656 с.

          19.Розен В.В.. Математические модели принятия решений вэкономике. Уч. пос., 2007 – 198 с.

          20.Тюрина А.Д. Макроэкономика: конспект лекций / А.Д. Тюрина, С.А. Шилина. – М.: Эксмо, 2008. – 160 с.

          21.Федотова Е.Л. Информационные технологии в профессиональной деятельности: Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2011. – 368 с.

           22. Шелухин О.И. Моделирование  информационных систем. Учебное пособие. Изд. Горячая линия. 2011. – 359 с.

ПРИЛОЖЕНИЯ

Приложение 1

Результат работы мастера поиска решений

Окно мастера поиска решений для первого условия

            Окно мастера поиска решений для второго условия

Окно мастера поиска решений для третьего условия

Приложение 2

Решение задачи в среде MathCAD для первого условия

Решение задачи в среде MathCAD для второго условия

Решение задачи в среде MathCAD для третьего условия