Материал: Математические методы и модели в разработке и принятии управленческих решений. методические указания. Амелин С.В

где(λij xij )– количество работ j-го вида, выполненных i-м исполнителем.

Решение задач транспортного типа

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

Транспортная задача. Общая постановка задачи. В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза от m поставщиков A1, A2,…, Am до n потребителей В1, В2,..., Вn. Обозначим количество груза, имеющегося у каждого из m поставщиков (запасы), соответственно a1, a2, …, am, а заказы каждого из потребителей (потребности) обозначим соответственно b1, b2, …, bn. Тогда при условии Σai = Σbj, мы имеем закрытую модель, а при условии Σa i ≠ Σbj – открытую модель транспортной задачи. Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены, и при этом на некоторых базах остаются излишки груз (Σai > Σbj), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (Σai < Σbj). Также существуют одноэтапные модели задач, где перевозка осуществляется напрямую с базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется «перевалочный пункт», например склад. План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок.

11

Математическая модель задачи.

Целевая функция (минимизация транспортных расходов на доставку продукции):

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

где xij – количество товара, перевозимого из i-го пункта отправления в j-й пункт назначения, шт;

cij – затраты на перевозку единицы товара из i-го пункта отправления в j-й пункт назначения, ден. ед.;

ai – предложение i-го поставщика, шт.; bj – спрос j-го потребителя, шт.;

m – количество поставщиков; n – количество потребителей.

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

12

xij ≥ 0 , i = 1,m , j = 1,n.

Транспортно-производственная задача. В исследованиях, посвященных вопросам определения границ зон сбыта продукции или рациональных связей по прикреплению потребителей к поставщикам, должны учитываться не только транспортные, но и производственные затраты. Такие задачи получили название транспортно-производственных. В качестве cij = Si + tij выступают транс- портно-производственные затраты, т. е. Si – затраты на производство единицы продукции (себестоимость, цена единицы продукции или приведенные удельные затраты) i-м поставщиком; tij – затраты на перевозку продукции между i-м поставщиком и j-м потребителем. Если увеличить или уменьшить на одну и ту же величину все показатели cij в матрице или в строке, или в столбце, то свойства матрицы не изменятся. Суммарные мощности поставщиков равны суммарному спросу потребителей. Следовательно, какой бы ни была стоимость производства, потребители для удовлетворения своего спроса возьмут продукцию у всех поставщиков. От каких поставщиков получит каждый потребитель продукцию, зависит от транспортных затрат.

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

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

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 3 РЕШЕНИЕ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ОПТИМИЗАЦИЯ РЕШЕНИЯ О КАПИТАЛОВЛОЖЕНИЯХ

В НЕСКОЛЬКО ОБЪЕКТОВ ЕДИНОВРЕМЕННО

Допустим имеется возможность вложения средств С в группу из n предприятий на реконструкцию и модернизацию оборудования. Известен возмож-

13

ный прирост продукции на каждом предприятии в зависимости от выделенных ему средств ri(x); i = 1, n .

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

Составим основное функциональное уравнение. Обозначим через f1 – максимально возможный прирост выпуска продукции на одном предприятии при различных значениях вкладываемых средств х. Каждому значению х отвечает определённый результат r1(x):

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

На следующем шаге - оптимальный эффект от вложения средств в два предприятия получаем максимизируя объём прироста продукции на втором предприятии r2(x) плюс оптимальный результат, полученный на предыдущем шаге:

где yn-2 – средства, вкладываемые в два предприятия; х – средства, выделяемые второму предприятию;

(yn-2 – x) – средства, вкладываемые в первое предприятие.

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

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4 РЕШЕНИЕ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

14

ничения отсутствовали, то нечего было бы выбирать, не было бы и в ариантов решений.

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

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

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

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

вопределении наибольшего или наименьшего значения целевой функции

f(x1, х2,.........., xn)

при условиях

gi(x1, х2,.........., xn) ≤ bi,

где f и gi — заданные функции,

bi — некоторые действительные числа.

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

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

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

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

15