В данной статье рассматривается понятие линейного программирования, а также наиболее распространенная задача данного класса математического моделирования — транспортная задача. Приводится классификация по разным признакам: критериям времени и стоимости, сбалансированности. Рассматриваются основные методы решения различных типов транспортных задач. Описывается разработанный алгоритм решения с использованием программирования в САПР MathCAD.
Ключевые слова:линейное программирование, транспортная задача, система автоматизированного проектирования, MathCAD, программирование.
Введение
Математические знания и навыки нужны практически во всех профессиях, прежде всего, в связанных с естественными науками, техникой и экономикой. Профессиональный уровень экономиста зависит от того, освоил ли он современный математический аппарат и умеет ли использовать его при анализе сложных экономических процессов. Неопределенность экономических процессов, значительный разброс и большой объем информации обуславливают необходимость привлечения к исследованию экономических задач различных методов: теории вероятностей и математической статистики, моделирования, элементов теории оптимизации, в т. ч. линейного программирования. Линейное программирование является одним из разделов математического программирования — области математики, разрабатывающей теорию и численные методы решения многомерных задач с ограничениями. Одной из задач линейного программирования является транспортная задача — задача о наиболее экономном плане перевозок однородного продукта из пунктов производства в пункты потребления.
Актуальность исследованиясостоит в постоянном расширении сфер применения математического моделирования; практической применимости рассматриваемых методов при решении реальных задач математики и экономики.
Цель исследования: изучение методов решения транспортных задач и апробирование их в опытно-экспериментальной работе с применением системы автоматизированного проектирования (САПР) MathCAD.
Задачи исследования:
1. Рассмотреть типы транспортных задач и методы их решения.
2. Составить алгоритм для реализации методов решения транспортных задач в MathCAD.
3. Апробировать разработанный алгоритм в экспериментальной работе с использованием элементов программирования в MathCAD.
Математическая модель транспортной задачи.
Транспортная задача — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Классическая транспортная задача — это задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах со статичными данными (это основные условия задачи). [5] Под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т. д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т. п. Целью транспортной задачи является обеспечение доставки продукции потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов. Цель считается достигнутой при выполнении шести условий: 1. нужный товар… 2. необходимого качества… 3. в необходимом количестве доставлен… 4. в нужное время… 5. в нужное место… 6. с минимальными затратами.
Рассмотрим постановку транспортной задачи на примере. Пусть некоторый однородный груз сосредоточен у m поставщиков в объемах 
. Данный груз необходимо доставить n потребителям в объемах 
. Известны 
(i=1,2,…,m, j=1,2,…,n) — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице или в виде векторов запасов поставщиков, запросов потребителей и матрицы стоимостей.
Неизвестные параметры транспортной задачи обозначим 
(i=1,2,..,m, j=1,2,..,n) — объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок
.
Т. к. произведение 
определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны 
.
По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция (функция, связывающая цель с управляемыми переменными в задаче оптимизации) имеет вид 
.
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:
, i=1,2,…,m.
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей [2, с.153]:
, j=1,2,…,n.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
, (1)
, i=1,2,…,m, (2)
, j=1, 2, …, n, (3)
, i=1,2,,…,m, j=1,2,…,n (4)
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т. е. 
. Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи 
, i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).
Типы транспортных задач и методы их решения
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). [2, с.157]
|
1. По критерию стоимости:
|
2. По критерию времени:
|
Также различают три вида транспортных задач согласно условию сбалансированности [3, с. 75]:
- сбалансированная транспортная задача, в случае, если количество произведенной продукции равно суммарной потребности в ней;
- транспортная задача в условиях перепроизводства, в этом случае для сведения ее к сбалансированной транспортной задаче необходимо ввести фиктивный пункт потребления, стоимость перевозки единицы продукции в который равен нулю;
- транспортная задача в условиях дефицита, в этом случае для сведения ее к сбалансированной транспортной задаче необходимо ввести фиктивный пункт производства, стоимость перевозки с которого можно принять равной 0.
Для решения любой транспортной задачи необходимо, в первую очередь, составить опорный план. Это можно сделать различными способами, однако для всех способов непременным является требование, чтобы в процессе заполнения распределительной таблицы в каждую загружаемую клетку вписывалась максимально возможная по величине поставка. В таком случае каждый раз будет либо исчерпываться весь запас груза у поставщика, либо полностью удовлетворяться спрос потребителя. Рассмотрим три основных метода составления опорного плана. [6]
1) Метод «северо-западного угла»
При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного 
и заканчивается в клетке неизвестного 
, т. е. идет как бы по диагонали таблицы перевозок.
2) Метод минимальной стоимости
При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.
3) Метод Фогеля
Суть данного метода состоит в следующем: в распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и в двух других методах.
Далее можно приступать к основной части решения транспортной задачи. Для этого также существует несколько методов. Наиболее распространены два: метод потенциалов и метод прямоугольников. [3, с.87]
1. Метод потенциалов:
- Построить опорный план таблицы.
- Провести ноль-преобразование в таблице тарифов, т. е. такое преобразование, в результате которого все тарифы в клетках с не нулевыми перевозками равны 0, а в остальных клетках при этом нет отрицательных тарифов. Если в результате ноль-преобразования имеются отрицательные тарифы, то переходим к следующему пункту, если нет, задача решена оптимально.
- Построить новое решение, в котором стоимость перевозки будет меньше в исходной таблице тарифов.
2. Метод прямоугольников:
- Построить опорный план задачи.
- Выписать все неправильные прямоугольники, т. е. прямоугольники, в которых сумма тарифов по одной диагонали не равна сумме тарифов по другой диагонали.
- Определить мощности неправильных прямоугольников и выбрать прямоугольник наибольшей мощности. Мощность неправильного прямоугольника называют величину, на которую уменьшиться стоимость перевозки при преобразовании неправильного прямоугольника в правильный.
- Заменить прямоугольник наибольшей мощности на правильный и подставить его в таблицу, получив новое решение.
- Осуществлять переход к пункту 2 до тех пор, пока, не останется ни одного неправильного прямоугольника в таблице.
- Если неправильных прямоугольников в таблице нет, значит, необходимое условие выполнено, и надо перейти к проверке достаточного условия, т. е. провести ноль преобразования.
- Если ноль преобразований проходит, то продолжаем решать задачу методом потенциалов. Если ноль преобразования не проходит и контур не строиться то, можно найти в таблице нейтральный прямоугольник, преобразовать его и получить новое решение, цена которого будет такая же, а план другой. А затем опять провести ноль преобразований.
Решение транспортных задач при помощи САПР MathCAD
Рассмотрим пример транспортной задачи при условии сбалансированности.
В кондитерский концерн входят три фабрики и пять магазинов. Фабрики производят 250, 275 и 225 единиц продукции в неделю. Пяти магазинам требуется 100, 200, 50, 275 и 125 единиц продукции еженедельно. Стоимость перевозки единицы продукции с завода в магазин приведена в таблице.
|
Магазины |
|||||
|
1 |
2 |
3 |
4 |
5 |
|
|
Фабрика 1 |
1.5 |
2 |
1.75 |
2.25 |
2.25 |
|
Фабрика 2 |
2.5 |
2 |
1.75 |
1 |
1.5 |
|
Фабрика 3 |
2 |
1.5 |
1.5 |
1.75 |
1.75 |
Необходимо составить план перевозок с целью минимизации суммарных транспортных расходов.
Рассмотрим математическую модель задачи. Пусть xij — неизвестный объем перевозок с i-й фабрики в j-й магазин. Необходимо минимизировать суммарные транспортные расходы 
, где cij — стоимость перевозки с i-й фабрики в j-й магазин. Неизвестные xij должны удовлетворять следующим ограничениям:
- объемы перевозок не могут быть отрицательными (
);
- вся продукция должна быть вывезена с заводов 
, где ai — объем производства на i-м заводе;
- потребности всех магазинов должны быть полностью удовлетворены 
, где bj — потребности j-го магазина.
Таким образом, получается следующая оптимизационная задача. Найти значения матрицы X(xij), при которых функция цели Z достигает своего минимального значения, и удовлетворяются отграничения, сформулированные выше. [4, с.84]
При решении транспортной задачи в САПР MathCAD с помощью решающего блока необходимо:
1. Определить матрицу С и вектора a и b.
2. Сформировать функцию цели Z.
3. Задать матрицу начального приближения X.
4. В решающем блоке ввести ограничения, для этого необходимо сформировать массивы, в которых хранятся 
и 
.
5. Решить задачу оптимизации с помощью функции Minimize.
Исходные данные для рассматриваемой транспортной задачи в САПР MathCAD формируются следующим образом:
Рис. 1. Формирование исходных данных транспортной задачи в САПР MathCAD
Затем необходимо осуществить поиск оптимального решения задачи с использованием блока Given — Minimize. [1, с.29] В качестве условий принимаются следующие утверждения:
1. Значения всех искомых переменных xij должны быть неотрицательными.
2. Массив, получаемый при использовании функции суммирования по строкам, должен быть равен вектору производственных мощностей фабрик.
3. Массив, получаемый при использовании функции суммирования по столбцам, должен быть равен массиву потребностей по магазинам.
Рис. 2. Решающий блок для сбалансированной задачи в MathCAD
В результате выполнения данного алгоритма получим оптимальный план перевозок для данных условий и соответствующее значение целевой функции.
Теперь рассмотрим алгоритм решения транспортной задачи в условиях перепроизводства в MathCAD. Условие задачи. В кондитерский концерн входят три фабрики и пять магазинов. Фабрики производят 250, 275 и 235 единиц продукции в неделю. Пяти магазинам требуется 100, 200, 50, 275 и 125 единиц продукции еженедельно. Стоимость перевозки единицы продукции с завода в магазин приведена в таблице. Необходимо спланировать план перевозок с целью минимизации суммарных транспортных расходов.
Задача является несбалансированной. Для ее решения введем фиктивный магазин, в который необходимо перевести количество продукции, равное разности между произведенной на всех фабриках продукцией и необходимой магазинам. В данном случае эта разница равна 10. Стоимость перевозки в фиктивный магазин примем равной 0. Внеся некоторые изменения в решение предыдущей задачи, получим решающий блок для транспортной задачи в условиях перепроизводства.
Рис. 3. Решающий блок для транспортной задачи в условиях перепроизводства в MathCAD
Решающий блок транспортной задачи в условиях дефицита в MathCAD формируется аналогично. Рассмотрим пример такой задачи. В кондитерский концерн входят три фабрики и пять магазинов. Фабрики производят 250, 275 и 225 единиц продукции в неделю. Пяти магазинам требуется 100, 200, 50, 275 и 150 единиц продукции еженедельно. Стоимость перевозки единицы продукции с завода в магазин приведена в таблице. Необходимо спланировать план перевозок с целью минимизации суммарных транспортных расходов. Данная задача также не является сбалансированной. Необходимо ввести фиктивную фабрику, производящую недостающее количество продукции. Стоимость перевозки с этой фабрики примем равной 0.
Рис. 4. Решающий блок для транспортной задачи в условиях дефицита в MathCAD
Заключение
Транспортная задача может решаться многими способами: вручную, с помощью стандартных программных средств (Excel), либо с помощью специальных программ. Однако изучение данного класса задач без использования современных программ требует довольно глубоких знаний в данной области и отнимает много времени. Таким образом, решать транспортные задачи «в ручном режиме» за строго определенный интервал времени могут лишь специалисты в области прикладной математики. Тем не менее, количество областей применения линейного программирования постоянно увеличивается. Методы математического моделирования применяются как при изучении отдельных проблем математики, так и в прикладных областях: экономики, логистики, программировании.
Существуют различные программные комплексы, имеющие в своем распоряжении необходимый инструментарий для построения математических моделей и решения задач линейного программирования (в том числе, транспортных задач). В данной статье были рассмотрены возможности системы автоматизированного проектирования MathCAD в области математического моделирования, составлены алгоритмы для решения транспортных задач с различными условиями.
Практическая значимость данного исследования заключается в том, что алгоритм и методы решения транспортной задачи могут быть использованы как при изучении некоторых тем математики, экономики в школе и ВУЗах, так и при проведении исследовательских работ, для решения реальных экономических и технических задач.
Литература:
1. Алейников И. А. Практическое использование пакета MathCAD при решении задач. — М.: Российский государственный открытый технический университет путей сообщения Министерства путей сообщения Российской Федерации, 2002.
2. Доманова Ю. А., Черняк А. А., Черняк Ж. А. Высшая математика на базе Mathcad: общий курс. — С-Пб: БХВ-Петербург, 2003.
3. Ермаков В. И. Общий курс высшей математики для экономистов. — М.: ИНФА, 2008.
4. Карманов В. Г. Математическое программирование. — М.: ФИЗМАТЛИТ, 2011.
5. Wikipedia: [Электронный ресурс]. URL: http://ru.wikipedia.org/wiki/Транспортная_задача (Дата обращения: 15.12.13г.)
6. Semestr: [Электронный ресурс]. URL: http://math.semestr.ru/transp/task_3.php (Дата обращения: 8.01.14г.)
