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

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

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

Введение

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

В общем, виде математическая постановка экстремальной задачи состоит в определении наибольшего и наименьшего значения целевой функции f (x1,x2, …,xn) при условиях gi (x1,x2, …,xn) ? bi (i=), где f и gi -заданные функции, а bi - некоторые действительные числа.

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

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

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

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

1. Сущность транспортной задачи линейного программирования

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

Таблица 1. Экономико-математическая модель транспортной задачи

Примечание. Аi - название пункта отправления; Вj - название пункта назначения; ai - производственная мощность поставщиков; bj - спрос потребителей; m - число поставщиков; n - число потребителей; i - номер строки (i-й поставщик) i = 1…m; j - номер столбца (j-й потребитель) j = 1…n; cij - показатель критерия оптимальности, удельные затраты на транспортировку единицы продукции (себестоимость перевозок) от поставщика i до потребителя j; xij - количество продукции, перевозимое от поставщика i до потребителя j, план перевозок, распределение поставок, корреспонденция грузов.

Условия задачи в принятых обозначениях следующие.

1. Каждый поставщик должен дать ровно столько продукции, столько у него есть, т. е. сумма поставок по каждой строке должна будет равна мощности ai этой строки:

. (1)

2. Каждый потребитель должен получить ровно столько продукции, сколько ему требуется, т.е. сумма поставок по каждому столбцу должна будет равна спросу bi этого столбца:

. (2)

3. Из вышеприведённых условий (1) и (2) следует:

. (3)

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

Чтобы определить суммарные затраты на перевозки, достаточно просуммировать произведения объёмов каждой поставки на соответствующие им удельные затраты на транспортировку. План будет оптимальным, если эта сумма (целевая функция F) будет сведена к минимуму:

. (4)

Транспортная задача является закрытой, если соблюдается условие (3). Если данное условие не соблюдается, то для приведения открытой транспортной задачи к закрытому виду вводится фиктивный потребитель ФВ или фиктивный поставщик ФА. Разница между производственной мощностью и спросом относится на его счёт. Расходы по доставке груза до фиктивного потребителя или фиктивного поставщика равны нулю, так как груз фактически не перевозится.

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

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

Для описания алгоритма используем формульно-словесный способ. Рассмотрим пример транспортной задачи (табл. 2).

Таблица 2. Исходная транспортная матрица

В табл. 2 по строкам матрицы представлены пункты (станции) отправления от А1 до А4 и объемы погрузки в тоннах - 100, 150, 90, 30 т, а по столбцам - пункты (станции) назначения от В1 до В5 и объемы выгрузки - 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (ai = bj = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А1 и станцией выгрузки В1, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом - 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, - оптимальным планом перевозок.

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

Операция 1. Построение опорного плана.

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

Таблица 3. Метод северо-западного угла

Берем «северо-западную» клетку матрицы - это клетка А1В1 и записываем в нее максимально возможную поставку - 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А1 не исчерпаны, следуем по первой строке вправо и записываем в клетку А1В2корреспонденцию равную максимально возможной величине - 60 т. Таким образом получается, что ресурсы станции А1 полностью использованы, однако спрос станции выгрузки В2 не удовлетворен. Тогда от клетки А1В2 опускаемся вниз до клетки А2В2 и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 2.3) составит:

Fсев-зап. = 40 • 10 + 60 • 9 + 20 • 7 + 110 • 13 + 20 • 6 + 30 • 7 + 60 • 1 + + 30 • 2 = 2960 ткм.

После расстановки корреспонденции матрица проверяется на вырождение, т.е. должно выполняться условие:

, (5)

где m - количество строк, n - количество столбцов, Nбаз - количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 8 = 4 + 5 - 1. План транспортной задачи, отвечающий условию (n + m - 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

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

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

Таблица 4. Метод наименьшего элемента в матрице

Далее отыскиваются клетка, имеющая следующее по величине расстояние. В нашей матрице это две клетки с расстоянием 2 км в пятом столбце. Однако в эти клетки поставки корреспонденцию грузов ставить нельзя, поскольку спрос станции В5 полностью удовлетворен со станции А3. Поэтому столбец 5 из дальнейшего построения плана исключаем. Следующие по величине показателя критерия оптимальности клетки с расстоянием 4 км это клетки А2В1 и А4В2. Выбираем одну из них, например, А2В1 и записываем в нее поставку 40 т. Далее идет клетка А4В2 - поставка 30 т, потом А1В4 - 50 т, А2В2 - 50 т. Все оставшиеся ресурсы по станциям погрузки распределяем между клетками третьего столбца в клетки А1В3 и А2В3. После составления опорного плана во избежание ошибок целесообразно проверить балансы погрузки, выгрузки и суммы корреспонденций по строкам и по столбцам матрицы. Функционал F плана, составленного методом наименьшей стоимости, равен 2150 ткм. Таким образом, построенный план значительно лучше плана, построенного методом северо-западного угла. Однако число базисных клеток в плане - 7. Это не соответствует условию (5), т. е. меньше требуемого на единицу. Такой план математики назвали вырожденным (случай вырождения). Случай вырождения «лечат» путем введения в матрицу недостающего количества базисных клеток с нулевыми поставками. Нулевую поставку необходимо вводить в матрицу рядом с базисной клеткой, которая обусловила «пропажу» базисной клетки.

Для того чтобы понять, почему «пропадают» поставки, обратимся к методу северо-западного угла. Из табл. 3 следует, что как только была заполнена «северо-западная» клетка, рядом с ней сразу появляется соседняя базисная клетка, потом еще одна и т.д. Цепочка базисных клеток без разрыва следует до «юго-восточного угла» матрицы. Однако если бы в этой цепочке появилась клетка, связывающая поставщика и потребителя с равными объемами погрузки и выгрузки, и в нее была бы записана такая же поставка, то это привело бы к пропаже базисной клетки. Описанная ситуация имела место в табл. 2.4, когда в клетку А3В5 была введена корреспонденция объемом 90 т, равная объемам погрузки и выгрузки по соответствующим станциям. Поэтому необходимо ввести в план дополнительную базисную клетку с нулевой поставкой. Эта клетка должна стоять рядом с клеткой А3В5. Из трех соседних клеток следует выбрать клетку с минимальным расстоянием, например, А2В5. Записываем в нее корреспонденцию, равную «0» (табл. 5).

Таблица 5. Добавление нулевой поставки

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

Операция 2. Проверка плана на оптимальность.

Операция 2.1. Расчет потенциалов.

Проверка плана транспортной задачи в описываемом методе на оптимальность осуществляется с помощью потенциалов. Потенциалы - это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим ui, потенциалы столбцов - vj. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А2В3. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u3 = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле

. (6)

Потенциал первого столбца v1 = u2 + c21 = 0 + 4 = 4;

второго: v2 = u2 + c22 = 0 + 7 = 7;

третьего: v3 = u2 + c23 = 0 + 13 = 13;

пятого: v5 = u2 + c25 = 0 + 2 = 2.

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

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и базисной клетке А1В3 по формуле:

, (7)

где u1 = v3 - c31 = 13 - 8 = 5.

Для строки 3 потенциал будет равен:

u3 = v5 - c35 = 2 - 1 = 1.

Также рассчитываем потенциалы для всех строк и столбцов (табл. 6).

Таблица 6. Расстановка потенциалов и перераспределение поставок

Операция 2.2. Проверка небазисных клеток на соответствие их условию оптимальности.

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

. (8)

Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже cij, значит, использование данного маршрута не улучшит план, а если cij ниже разности потенциалов, т.е. условие (8) не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.

Проверим условие (8) для табл. 6.

Клетка А1В1: 4 - 5 < 10, условие выполняется.

Клетка А1В2: 7 - 5 < 9, условие выполняется и т. д.

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

Однако для нашего примера это не так. Не выполняется условие для клетки А2В4 (10 - 0> 6), клетки А3В3 (13 - 1 > 9), а также для клеток А3В4, А4В3, из чего следует, что разработанный опорный план не оптимален. Отметим эти клетки.

Операция 3. Улучшение плана.

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

Операция 3.1. Построение цепи (контура, цикла) перераспределения поставок.

Улучшение плана осуществляется по одной из небазисных клеток, для которой условие оптимальности оказалось невыполненным. В нашем плане имеется четыре такие клетки. Выбираем одну из них, для которой условие оптимальности не выполняется в наибольшей степени. В нашем плане это клетка А2В4. Для нее условие оптимальности не выполнено на 4 единицы (10 - 0 - 6 = 4). Для этой клетки строим цепь перераспределения поставок. Цепь перераспределения поставок - это такая замкнутая ломаная линия, которая проходит по клеткам матрицы ходом шахматной ладьи. В вершинах контура обязательно лежит одна небазисная клетка (несоответствующая условию оптимальности, найденная ранее), а остальные соответствуют только базисным клеткам. Линии контура могут пересекаться. Для небазисной клетки А2В4 цепь будет проходить по клеткам А1В4, А1В3, А2В3 (табл. 7).

Таблица 7. Возможные варианты построения цикла перераспределения

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

Операция 3.2. Перераспределение поставок.

Перераспределение поставок (см. табл. 6) производится по цепи. Вначале определим объем перераспределения поставок. Для этого присвоим клеткам - вершинам цепи - знаки. В небазисную клетку А2В4 ставим «+», поскольку в нее будет вводиться поставка. Далее, чередуя «+» с «-», расставляем знаки по остальным вершинам контура. Величина объема перераспределения поставок принимается равной минимальной поставке в отрицательной клетке. Для нашего случая это 50 единиц груза. Перераспределение заключается в том, что к поставкам в положительных клетках найденный объем прибавляется, а для отрицательных клеток отнимается. Результат представлен в табл. 6.

Функционал F' нового плана, представленного в табл. 6 (выделенные поставки), составляет 1950 ткм, что на 200 ткм меньше значения функционала F предыдущего плана.

Полученный улучшенный план, представленный в табл. 2.6, в свою очередь, требует проверки на оптимальность, поэтому необходимо вернуться к операции 2.

Совокупность действий, описанных в операциях 2 и 3, в процессе решения задачи повторяется до тех пор, пока не будет получен оптимальный план. Эта совокупность носит итеративный (циклический) характер, поэтому она называется итерацией. Через определенное число итераций план становится оптимальным. После этого осуществляется переход от второй операции к четвертой (табл. 8).

Таблица 8. Повторение операций 2, 3

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

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

Проверка плана на оптимальность свидетельствует о том, что для двух клеток условия оптимальности не выполняются. После перераспределения поставок по клетке А4В3, получаем новый план (табл. 9).

Таблица 9. Оптимальный план поставок

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

3. Решение транспортной задачи линейного программирования с помощью надстройки «Поиск решения» в MS Excel

Рассмотрим последовательность решения предыдущего примера надстройки «Поиск решения» в MS Excel.

Вначале вводятся исходные данные (рис. 1).

Рис. 1. Исходные данные

Расчет ограничений транспортной задачи необходимо выполнять в нижеприведенной последовательности: в ячейки столбика С15:С18 вводим зависимость с помощью функции СУММ Мастера функций. Для этого в соответствующем диалоговом окне вводим адрес строки. На рис. 2 представлен адрес для ячейки С15. Аналогичные расчеты следует выполнить для всех пунктов производства и потребления.

Рис. 2. Ввод ограничительных уравнений

Затем в ячейку D12 вводим целевую функцию (рис. 3), представляющую собой сумму произведений себестоимости перевозки тонны груза на один километр и соответственно объем перевозок, условно принятый за единицу по всем пунктам производства и потребления.



Рис. 3. Ввод целевой функции

математический транспортный линейный нулевой

На следующем этапе запускаем «Поиск решения» и заполняем соответствующие ячейки (рис. 4.). В поле с единицами располагаются изменяемые ячейки.

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



Рис. 4. Этап «Поиск решения»

Во вкладке «Параметры» отметить «Линейная модель» и «Неотрицательная значения». Затем нажать «Выполнить» и сохранить полученное значение (рис. 5.).



Рис. 5. Результаты этапа «Поиск решения»

Как видно из рис. 5, функционал (F = 1920 ткм), найденный с помощью метода потенциалов, совпадает со значением целевой функции определённой с помощью надстройки «Поиск решения» в MS Excel.

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

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

аi - производственные мощности предприятий по производству запасных частей по пунктам размещения i;

bj - потребности в запасных частях в пунктах j;

xij - объемы перевозок запасных частей между пунктами производства и пунктами потребления i, j;

Зi - затраты на производство единицы (удельные затраты) запасных частей у предприятий по пунктам i;

сij - затраты на транспортировку единицы запасных частей между пунктами производства и потребления;

аi' - загрузка производственных мощностей предприятий по производству запасных частей по пунктам размещения i.

Тогда экономико-математическая модель может быть сформулирована следующим образом: найти совокупность переменных аi', минимизирующих целевую функцию F:

(9)

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

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

а1 = 500 т; а2 = 400 т; а3 = 700 т;

З1= 45 тыс. руб.;З2 = 49 тыс. руб.; З3 = 40 тыс. руб.

Потребности в пунктах потребления:

b1 = 350 т; b2 = 320 т; b3 = 190 т; b4 = 270 т; b5 = 230 т.

Затраты на транспортировку одной тонны запасных частей между пунктами производства и потребления представлены в матрице (табл. 10).

Таблица 10. Затраты на транспортировку одной тонны запасных частей

Номера пунктов производства i	Номера пунктов потребления j
	В1	В2	В3	В4	В5
А1	3	5	4	7	6
А2	10	8	11	9	13
А3	8	5	6	7	4

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

т.

Матрица, отражающая особенности решаемой задачи, принимает следующий вид (табл. 11).

Таблица 11. Транспортная таблица

Пункты производства и их мощности	Потребители и их спрос
	В1	В2	В3	В4	В5	ФВ
	350	320	190	270	230	240
А1	500		48		50		49		52		51		0
А2	400		59		57		60		58		62		0
А3	700		48		45		46		47		44		0

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

Сформулированная таким образом задача решается с помощью одного из известных алгоритмов транспортной задачи линейного программирования или с помощью «Поиска решения» в MS Excel. Результаты решения транспортной задачи целесообразно представить в виде табл. 12. Алгоритм решения был рассмотрен ранее (подразд. 2, 3).

Таблица 12. Матрица поставок

Пункты производства и их мощности	Потребители и их спрос
	В1	В2	В3	В4	В5	ФВ
	350	320	190	270	230	240
А1	500		48		50		49		52		51		0
		350				150
А2	400		59		57		60		58		62		0
								160				240
А3	700		48		45		46		47		44		0
				320		40		110		230

Анализ результатов решения показывает следующее. Предприятие А1 отправляет реальным потребителям В1 и В2 соответственно по 350 и 150 т запасных частей, что в сумме составляет 500 т. Иначе говоря, мощности предприятия А1 полностью вошли в оптимальный план. Следовательно, загрузка мощностей этого предприятия равна также 500 т, т. е. 100 %. То же самое имеет место для предприятия А3. Предприятие А2 реальному потребителю В4 отправляет 160 т продукции. Оставшиеся мощности 240 т, как видно из табл. 2.12, приходятся на фиктивного потребителя. Это говорит о том, что мощности А2 востребованы не полностью. Следовательно, загрузка А2 составляет 160 т, т. е. 40 %. Предприятия, которые не полностью используют производственную мощность, необходимо переориентировать на выпуск нового вида продукции или закрыть.

Из табл. 12. видно, что функционал, т. е. суммарные производственные и транспортные затраты, составляет 64 960 тыс. руб. Из них производственная составляющая - первый член целевой функции [формула (10)] - равна 58 340 (500 • 45 + 400 • 160 + 700 • 40) тыс. руб., на транспортную составляющую приходится соответственно 6620 тыс. руб., или 11 %. Высокий удельный вес транспортной составляющей - свыше 5 % - свидетельствует о том, что транспортный фактор оказывает существенное значение на загрузку производственных мощностей для рассматриваемого примера.

5. Исходные данные

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

Первая группа - это показатели производственных мощностей по пунктам их размещения. К ним относятся собственно мощности предприятий по производству запасных частей аi и удельные затраты на производство Зi. Мощности предприятий приведены в табл. 13.

Таблица 13. Производственные мощности предприятий

Пункты производства Ai	Мощности ai по производству запасных частей в тоннах по вариантам
	1	2	3	4	5	6	7	8	9	10
A1	490	500	550	670	1000	450	670	540	640	570
A2	380	350	690	500	390	600	300	760	290	930
A3	600	640	370	850	740	840	880	580	850	810
A4	750	850	950	450	600	760	490	670	700	350
A5	800	700	450	620	520	620	750	450	580	490

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

. (10)

Вторая группа показателей - это потребности в запасных частях по пунктам размещения потребителей в тоннах bj. Эти данные по вариантам приведены в табл. 14.

Таблица 14. Потребности в запасных частях

Пункт потребления	Потребности bj пунктов потребления по вариантам, т
	1	2	3	4	5	6
B1	170	340	140	190	180	360
B2	230	190	330	340	140	410
B3	260	220	520	150	360	230
B4	310	300	120	380	170	390
B5	120	210	390	420	300	100
B6	350	360	250	170	110	250
B7	290	320	100	310	320	310
B8	270	460	310	250	470	350
B9	400	250	430	390	490	220
B10	360	100	140	110	160	100

Третья группа показателей - это затраты на транспортировку запасных частей между пунктами производства и потребления на рассматриваемом полигоне железнодорожной сети. Полигон железнодорожной сети представлен в табл. 15. Применительно к заданному полигону по вариантам указаны номера узлов железнодорожной сети, в которых размещены предприятия по производству запасных частей (индексы i), и номера узлов, в которых размещены потребители запасных частей (индексы j) (табл. 16).

Таблица 15. Исходные данные для построения транспортной сети

Номера узлов	1-2	1-3	1-4	2-3	2-6	2-10	3-5	3-7	3-8	4-5
Расстояние, км	110	75	90	160	69	130	150	170	130	98
Номера узлов	5-8	5-9	6-7	6-10	7-8	7-11	8-9	8-12	9-12	9-13
Расстояние, км	49	112	125	98	117	135	100	95	110	113
Номера узлов	10-11	10-14	11-12	11-14	12-13	12-15	13-15	14-15	14-16	15-16
Расстояние, км	95	117	150	105	190	170	200	140	79	130

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

Вар.	Номера узлов размещения мощностей - индексы i	Номера узлов размещения потребителей - индексы j
1	1	8	10	13	16	2	3	5	6	7	9	11	12	14	15
2	3	5	6	13	14	1	2	4	7	8	9	10	11	12	16
3	2	4	7	9	15	3	5	8	6	10	11	12	13	14	16
4	1	5	6	11	16	2	3	7	8	9	10	12	13	14	15

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

. (11)

где е - расходная ставка на 10 ткм. Для рассматриваемого рода груза принимается равной 4 руб.; L - минимальное расстояние, рассчитываемое для заданного полигона между пунктами производства и потребления, км.

6. Последовательность решения задачи

Решение задачи осуществляется по вариантам (см. табл. 13, 14 и 16). Расчет вариантов должен быть приведен в работе. Выполнение задачи осуществляется в следующем порядке.

1. Постановка задачи и формулировка экономико-математической модели в соответствии с заданной размерностью.

2. Определение показателей производственных мощностей. Величины мощностей берутся из табл. 13, а производственные затраты рассчитываются по формуле (10).

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



Рис. 6. Фрагмент транспортной сети

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

Результаты расчета заносятся в таблицу (см. форму табл. 11). Затраты на транспортировку рассчитываются по формуле (11) в таблице аналогичной формы.

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

5. Расчет оптимального плана транспортной задачи для расчетной матрицы. Расчет может быть выполнен без применения вычислительных средств с помощью метода потенциалов или с помощью «Поиска решения» в MS Excel, как это было показано ранее с приложением листинга. Результат решения транспортной задачи оформляется согласно табл. 12. Студенты очного отделения решают задачу без применения вычислительных средств и с помощью «Поиска решения». Студенты заочного отделения выбирают способ решения самостоятельно.

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

7. Анализ показателей оптимального плана и выводы.

7.1. Сравнить решения, полученные с помощью метода потенциалов и надстройки MS Excel «Поиск решения».

7.2. Оценить долю транспортных затрат.

7.3. Дать рекомендации по размещению пунктов производства и потребления.

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

1. Экономико-математическое моделирование. Учеб. для ВУЗов / Под ред. А.Д. Дрогобыцкого. - М.: Экзамен, 2004.

2. Карпелович Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. - М.: Физматгиз, 1963.

3. Нестеров Е.П. Транспортные задачи линейного программирования. - М.: Транспорт, 1971.

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

...