IX Международная студенческая научная конференция Студенческий научный форум - 2017

ВВЕДЕНИЕ

Человеческая деятельность связана с принятием множества решений по способам достижения поставленных целей. При принятии решений приходится учитывать много факторов, отметим среди таких факторов, в первую очередь, ограниченность ресурсов, неопределенность внешних условий, присутствие конкурирующих сторон, которые стремятся достичь своих целей, не всегда совпадающих с нашими. Как известно, экономика занимается изучением того, как в обществе распределяются ограниченные ресурсы. Как правило, у экономической системы (семьи, фирмы, государства) есть некоторая цель, но на пути к достижению этой цели стоят ограничения по количеству используемых ресурсов. Рассмотрим задачи распределения неоднородных ресурсов, к числу которых относятся задачи планирования производства, оптимальное управление запасами, планирование и анализ проектов, а также транспортные задачи, решение которых мы рассмотрим в среде ЭТ MS Excel и математического пакета Mathcad.

1. Общая задача оптимизации

Задача оптимизации – задача для нахождения экстремума целевой функции (минимума или максимума) в какой-либо области конечномерного пространства, ограниченной системой линейных и/или нелинейных неравенств и/или равенств. [5]

1.1 Постановка задачи оптимизации

Одной из главных особенностей нового этапа развития науки и техники является рост уровня требований к качеству и сложности создаваемых систем, технологий и процессов. Разработка компьютеризированных методов проектирования и осуществление создания систем на ее основе автоматизированного проектирования вычислительных систем, которые решают уже не вспомогательные, а главные задачи. Это все определяется противоречием между традиционными подходами и усложнением создаваемых современных систем. Т.е. речь идет о разработке методологии и алгоритмического обеспечения систем поддержки принятия проектных и управленческих решений. [5] Эта программа предполагает разработку методов, а также алгоритмов, которые помогают вести направленный поиск оптимальных (наилучших) показателей и структур, а также позволяют контролировать изменение этих показателей в момент, когда система разрабатывается и эксплуатируется. Потребности сокращения времени разработки систем, уменьшении материальных и трудовых трат на разработку систем без понижения надежности и качества. Формализация главных этапов управления и проектирования должно лежать в основе создания хорошо функционирующих систем компьютерной поддержки принятия решений, как проектных, так и управленческих. Идея оптимизации, направленность к оптимальным, a не ко всем допустимым решениям насквозь проходит через процессы проектирования систем и управления их работой. Под оптимальным проектированием обычно понимают процесс принятия наилучших (оптимальных)

в некотором смысле решений, что осуществляется с помощью ЭВМ. Также

предполагается наличие формализованных критериев математических моделей проектируемых устройств и оптимизации. Наиболее общим критерием оптимизации функционирования является технико-экономический. Это критерий эффективности всей проектируемой системы. Обобщенный критерий часто включает в себя ряд других частных критериев, вот почему оптимальное проектирование является задачей многокритериальной оптимизации. [3]

1.2 Классификация методов решения оптимизационных задач

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

1. методы исследования функций классического анализа;

2. методы, основанные на использовании неопределенных множителей Лагранжа;

3. вариационное исчисление;

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

5. принцип максимума;

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

7. нелинейное программирование.

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

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

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

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

1.2.1. Методы исследования функций классического анализа

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

При этом надо решить конечную систему конечных уравнений, обычно нелинейных, для этого приходится применять численные методы, которые аналогичны методам нелинейного программирования. Из-за того, что система уравнений, которая получается в результате применения методов классического анализа, обеспечивается только лишь необходимые условия оптимальности возникают дополнительные трудности во время решения оптимизационной задачи. Поэтому все возможные решения данной системы (a их может быть и несколько) должны быть проверены на достаточность. [2] В результате данной проверки сначала отбрасывают решения, не определяющие максимальные и минимальные значения критерия оптимальности, а затем среди оставшихся экстремальных решений выбирают решение, удовлетворяющее условиям оптимизационной задачи, т. е. наименьшему или наибольшему значению критерия оптимальности в зависимости от постановки задачи. При существовании ограничений на область изменения независимых переменных методы исследования можно применять только лишь для нахождения экстремальных значений, входящих в указанную область. Особенно это имеет отношение к

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

1.2.2 Метод множителей Лагранжа

Как при наличии ограничений вида равенств на независимые переменные, так и при применении стандартных методов используется данный метод для решения подобных задач того же ряда сложности. К требованиям возможности получения аналитических уравнений и неравенств для производных от критерия оптимальности, во время этого добавляется подобное требование относительно вида уравнений аналитических ограничений. [3] В большинстве случаев при применении метода множителей Лагранжа приходится решать те же самые задачи, что и без ограничений. В данном случае некоторое усложнение возникает только лишь от добавления дополнительных неопределенных множителей, и вследствие чего ранг системы уравнений, решаемой для выявления экстремумов критерия оптимальности, в соответствии повышается на число ограничений. Во всем остальном, алгоритм поиска решений и проверки этих решений на оптимальность отвечает процессу решения оптимизационных задач без любых ограничений. [3] Множители Лагранжа можно использовать для применения для решения оптимизационных задач объекта на основе задач динамической оптимизации и уравнений с частными производными. При этом нужно интегрировать систему дифференциальных уравнений вместо отыскания оптимума с помощью решения системы из конечных уравнений. Следует также отметить, что множители Лагранжа применяют также при решении узкими методами задач разных классов с ограничениями вида равенств, например, в динамическом программировании и вариационном исчислении в качестве вспомогательного средства. Особенно продуктивно применение множителей Лагранжа в методе динамического программирования, в котором c их помощью редко удается снизить размерность задачи.

1.2.3 Методы вариационного исчисления

Данные методы, как правило, используются для решения таких задач, в которых критерии оптимальности представляют собой функционалы и решениями этих функционалов являются неизвестные функции. Чаще всего такие задачи получаются при статической оптимизации процессов, где параметры распределены или в задачах динамической оптимизации. В таком случае вариационные методы помогают свести решение задачи оптимизации к интегрированию системы из дифференциальных уравнений Эйлера, в котором каждое из них является дифференциальным нелинейным уравнением n-порядка (n=2) с граничными условиями, указанными на обоих концах интервала, на котором берется интеграл. Количество уравнений указанной системы в этом случае равно количеству неизвестных функций, определяемых во время решения оптимизационной задачи. Под действием интегрирования получившейся системы находят все функции. Необходимые условия функционального экстремума дают нам уравнения Эйлера. Поэтому системы из дифференциальных уравнений функции, полученные интегрированием следует обязательно проверить на экстремум функционала. [5] При присутствии ограничений типа равенств, которые имеют вид функционалов, используют множители Лагранжа, это позволяет перейти к безусловной задаче от условной. Самые большие значительные трудности при использовании вариационных методов возникают, когда появляются ограничения, выражения неравенствами. Заслуживают внимания прямые методы решения задач оптимизации функционалов, обычно позволяющие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую иногда проще, чем краевую задачу для уравнений Эйлера.

1.2.4 Линейное программирование

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

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

1.2.5 Геометрическое программирование

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

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

нелинейного программирования) является то, что до некоторого этапа оптимальную задачу решают аналитическим способом, то есть находят конкретные аналитические выражения, к примеру, системы дифференциальных или конечных уравнений, из чего в дальнейшем отыскивают наилучшее решение. [10] Как уже отмечалось, при использовании методов нелинейного программирования, а их можно отнести к прямым, используют получаемую при вычислении критерия оптимальности, с изменением которого меняется оценка эффективности того или иного действия, что отличается от решения задач с помощью других вышеперечисленных методов. Несомненно важной характеристикой любой задачи оптимизации является ее размерность n, которая равна числу переменных, а задание их значений, в свою очередь, необходимо для возможности однозначного определения состояния объекта, подвергнутого оптимизации. Обычно решение задач с большим числом неизвестных, то есть с высокой размерности связано с вынужденной необходимостью выполнения большого объема вычислений. Ряд методов (например, дискретный принцип максимума и динамическое программирование) специально приспособлен для решения оптимизационных задач и процессов с высокой размерностью, которые можно представить в виде многостадийных процессов с относительно маленькой размерностью каждого этапа. [7]

2. Задача линейного программирования

Одним из самых широко используемых методов является метод линейной оптимизации. Метод линейной оптимизации применяют для решения задач, в основе которых лежит цель составления оптимальных планов. Здесь можно рассматривать оптимальные планы производства, продаж, закупок, перевозок, оптимальное финансовое планирование, оптимальную организацию рекламной кампании или оптимальный план инвестиционного пакета фирмы.[10] Планирование – это одна из основных функций производства. Во время постановки любой оптимизационной задачи необходимо, в первую очередь, определит и указать количественную целевую характеристику, которую мы хотим достичь в процессе оптимизации – целевую функцию. Это может быть минимум издержек или максимум прибыли (во временном, денежном или каком-либо другом выражении). Целевая функция определяет, почему какое о определенное рассматриваемое решение лучше или хуже, чем другое. От переменных задачи зависит и сама целевая функция. Решая задачу, то есть находя оптимальное решение, эти переменные должны изменяться. В основе оптимизации лежит цель найти такие значения переменных в решении, при которых целевая функция минимальна или максимальна. Любая оптимизация всегда производится при наложении на целевую функцию некоторых ограничений – условий, ограничивающих изменения переменных в решении при поиске минимальной или максимальной целевой функции. Эти ограничения могут диктоваться:

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

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

3. установленными условиями задачи (рыночные ограничения, нормативные акты, накладывающие ограничения на ту или иную характеристику или любые

требования субъекта, принимающего решения). [7] Линейная оптимизация имеет дело с такими моделями, где целевая функция является линейно зависимой от переменных в решении, и ограничения представляют собой линейные уравнения или неравенства относительно переменных решения. Фактически, это означает, что целевая функция и ограничения могут представлять собой только суммы произведений постоянных коэффициентов на переменные решения в первой степени. Почему методы линейной оптимизации так важны? Это связано с тем фактом, что очень много важных для практики проблем, относящихся к самым разным сферам деятельности, могут быть проанализированы с помощью моделей линейного программирования; существуют эффективные и универсальные алгоритмы решения задач линейной оптимизации, реализованные в общедоступном программном обеспечении; методы анализа моделей линейной оптимизации позволяют не просто получить оптимальное решение, но и дают информацию о том, как может изменяться это решение при изменении параметров модели. [5] Именно эта информация, позволяющая получить ответы на вопросы типа “что - если”, представляет особую ценность для лица, принимающего решение. Однако в отличие от моделей линейной оптимизации, не существует универсального алгоритма, который бы во всех случаях гарантированно приводил к искомому оптимуму. Потому для совершения нелинейной оптимизации нужно уделить больше внимания деталям алгоритма и его реализации, чем обычно может уделить менеджер. С другой стороны, собственно концепция условной оптимизации, наглядно может быть проиллюстрирована на примерах линейной (и целочисленной) оптимизации. [4]

2.1 Решение ЗЛП графическим методом

Геометрически задача линейного программирования (ЗЛП) представляет собой отыскание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений, как показано на рисунке 1.

Рисунок – 1

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

2.1.1. Краткая теория

Положим n=2, т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение). Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми х₁ =0, х₂ =0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называется многоугольник решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью. [7]

Решение каждого неравенства системы ограничений ЗЛП – это полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Важно помнить, что область допустимых решений удовлетворяет условиям неотрицательности. [7] Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

Чтобы найти экстремальное значение целевой функции при графическом решении задач ЛП используют вектор-градиент, координаты которого являются частными производными целевой функции, т.е. Этот вектор указывает направление наискорейшего изменения целевой функции. Прямая , перпендикулярная вектору-градиенту, называется линией уровня целевой функции. В каждой точке линии уровня целевая функция имеет одно и то же значение. Приравняем целевую функцию постоянной величине “a”. Изменяя показатель “a”, получим семейство параллельных прямых, любая из которых является линией уровня. Важно знать, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону – убывает. Рассмотрим графическое решение задач линейного программирования на примере.

2.1.2.Три этапа решения ЗЛП

1. Постановка задачи.

Xимический завод выпускает соляную и серную кислоту. Производство одной тонны соляной кислоты приносит предприятию прибыль в размере 25 денежных единиц, производство одной тонны серной кислоты – 40 денежных единиц. Для выполнения заказа нужно выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Так же, необходимо учитывать, что выпуск кислот связан с образованием ядовитых отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество ядовитых отходов не должно быть больше 600 т, так как превышение этого ограничения приведет к крупным штрафам.

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

2. Построение математической модели.

2.1 Определим неизвестные:

это количество соляной и серной кислот, которое должен произвести завод.

2.2Целевая функция.

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

,

2.3 Ограничения

ограничение по опасным ресурсам

неотрицательность

план

100 план

3. Решение ЗЛП в среде ЭТ MSEхcel

Построим таблицу аргумента x, целевой функции и всех накладываемых на нее ограничений, как показано на рисунке 2, а также на рисунке 3 вместе с формулами:

Рисунок 2 – Значения аргумента, целевой функции и ограничений, Excel-документ

Рисунок 3 – Формулы для нахождения целевых функций и ограничений в Excel

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

Рисунок 4 – Графическое решение ЗЛП в Excel

3. Оптимизационная задача распределения неоднородных ресурсов.

3.1 Постановка задач.

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

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

Таблица 1 – Исходные данные

Используемые ресурсы	Изготавливаемые изделия					Наличие ресурсов
Трудовые	3	5	2	7	15
Материальные	4	3	3	5	9
Финансовые	5	6	4	8	30
Прибыль	40	50	30	20

Постановка задачи В.

Пусть у завода железобетонных изделий (ЖБИ) имеется видов сырья (песок, щебень, цемент) в объемах , Нужно произвести продукцию видов. Дана технологическая норма . потребления отдельного -го вида сырья для изготовления единицы продукции каждого -го вида. Известна прибыль , получаемая от производства единицы продукции -го вида. Определить, какую продукцию и в каком количестве должен производить завод ЖБИ, чтобы получить максимальную прибыль. Исходные данные представлены в таблице 2.

Таблица 2 – Данные для задачи B

Используемые ресурсы	Изготавливаемые изделия					Наличие Ресурсов
Песок	3	5	2	7	15
Щебень	4	3	3	5	9
Цемент	5	6	4	8	30
Прибыль	40	50	30	20

Постановка задачи С.

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

3.2. Решение задачи с помощью стандартных средств Exсel

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

Постановка задачи: Пусть у нас есть три виды сырья s₁, s₂, s₃ и их запасы:

S₁=350, s₂= 300, s₃=570. Обладая этими ресурсами предприятие выпускает продукцию: И₁, И₂, И₃, И₄, И₅. Также известна прибыль предприятия cj от реализации одного изделия j-го вида. Требуется состаить план выпуска продукции, обеспечивающия максимальную суммарную прибыль. Представление данной задачи с помощью стандартных средств Excel показано на рисунке 5.

Рисунок 5 – Постановка задачи в Excel

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

xj, j=1..m

(1)

Запишем ограничения по ресурсам (2):

(2)

где это количество ресурса.

Ограничения по запасам:

Ограничения понеотрицательности:

Целочисленность:

целые.

Обязательная поставка.

Применим эти ограничения с помощью надстройки поиск решения – рисунки 6, 7,8.

Рисунок 6 – Ограничения по знаку переменных

Рисунок 7 – Ограничение для целевой функции

Запишем наши ограничения в виде формул ждя рассчета:

Рисунок 8 – Формуля для нахождения расхода сырья.

Запишем целевую функцию, смотри рисунок 9:

Рисунок 9 – Формула для нахождения целевой функции

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

представлено на рисунке 10.

Рисунок 10 – Расход сырья

Решение этой жезадачи с ограничением целочисленности целевой функции и неизвестных показано на рисунке 11:

Рисунок 11 – Excel-документ решения задачи с ограничением по целочисленности

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

Рисунок 12 – Excel-документ решения задачи с учетом обязательной поставки

3.3Решение в среде пакета Mathcad

Решение задачи распределения неоднородных ресурсов в среде пакета Mathcad показано на рисунках 13, 14.

Рисунок 13 – Mathcad-документ решения задачи, определение неизвестных и целевой функции

Рисунок 14 – Mathcad-документ решения задачи, получение оптимального решения

Покажем результат решения данной задачи с условием целочисленности на рисунке 15.

Рисунок 15 – Mathcad-документ решения задачи с условием целочисленности

Обязательная поставка показана на рисунках 16, 17.:

Рисунок 16 – Mathcad-документ решения задачи, учет обязательной поставки

Покажем оптимальное решение:

Рисунок 17 – Mathcad-документ решения задачи, оптимальное решение

3.4. Транспортная задача

У классической транспортной задачи цель – минимизировать транспортные издержки при перевозках одинаковых грузов от нескольких поставщиков, расположенных в различных местах, к нескольким потребителям. В этом случае, в транспортной задаче, рассматривают только переменные транспортные издержки, то есть принимают, что суммарные издержки пропорциональны числу перевезенных единиц груза. В постановке транспортной задачи нужно задать таблицу транспортных издержек для перевозки единицы. У этой таблицы m строк (по количеству поставщиков) и n столбцов (по количеству потребителей). У таблицы х_ij те же размеры (mn) и имеет переменные решения. Нужно также обозначить запасы поставщиков, которые готовы к вывозу столбец и величины заказа потребителя. Транспортная задача предполагает, что нужно перевезти запасы каждого i-го поставщика и исполнить заказ каждого j-го клиента. Это возможно, если общие запасы всех поставщиков такие же, как сумма общих заказов всех потребителей. Это самое важное условие применимости эффективных алгоритмов, о которых упомянуто ранее, условие сбалансированности. Ограничения транспортной задачи имеют очень простой вид: сумма переменных решения вдоль каждой i-ой строки должна быть равна запасу поставщика Si, а сумма переменных решения вдоль каждого j-го столбца должна быть равна заказу соответствующего потребителя Dj. Наконец, чтобы получить целевую функцию (суммарные издержки), необходимо рассмотреть суммы произведений каждой строки таблицы транспортных издержек на соответствующую строку таблицы перевозок и сложить их, суммируя по i от 1 до m. Это и даст двойную сумму. Если задача сбалансирована и никаких других ограничений, кроме упомянутых выше нет.

3.4.1 Общий вид постановки транспортных задач

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

как и симплексный метод, помогают найти начальное решение, а позже, улучшая его, прийти к оптимальному решению. Классические транспортные задачи разделяются на два типа: критерий стоимости (достижение наименьших трат на перевозку) или расстояний и критерий времени (затрачивается наименьшее время на перевозку). Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (производства) а₁,а₂,…а_mв n пунктов назначения (потребления) b₁,b₂,…,bn. В таком случае в качестве критерия оптимальности зачастую берется наименьшая стоимость перевозки общего груза или наименьшее время его доставки. Представим количество груза, который есть на каждой из m баз (запасы), соответственно а₁,а₂,…аn, а общее количество имеющегося в наличии груза а:

a=a₁+a₂+a₃+…+an

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

b=b₁+b₂+b₃+…+bn

_a=b

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

открытую модель транспортной задачи.

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

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

Код для цитирования: Скопировать