Модель (4.20) — (4.22), (4.25) является статической энтропийной моделью ЗОК. Она представляет собой (ввиду выпуклости каждого слагаемого и в связи с известной теоремой [56] о выпуклости функции, равной сумме выпуклых функций) задачу выпуклого программирования с ограничениями транспортного типа. [c.119]
Легко заметить, что эта задача отличается от транспортной задачи лишь наличием величин Кц в ограничениях одного из типов (отсюда и одно из названий такой задачи — -задача). Для обобщенной транспортной задачи также разработаны алгоритмы решения, более эффективные, чем алгоритмы решения общей задачи линейного программирования. Транспортная задача проще обобщенной транспортной задачи с точки зрения алгоритма ее решения с помощью ЭВМ, а обобщенная транспортная задача проще общей задачи линейного программирования. При построении моделей их стараются сформулировать так, чтобы свести проблему к возможно более простой задаче. Конечно, такое сведение не должно осуществляться за счет искажения существенных черт изучаемой экономической системы. [c.152]
Еще одно усложнение связано с ограничением сверху на величину некоторой перевозки. Пусть, скажем, для перевозки из пункта i0 в пункт / требуется выполнение условия xi,i, dt,f,. Такое ограничение, скорее всего, может быть связано с ограниченностью пропускной способности пути, по которому перевозят грузы. Этот случай при помощи некоторых искусственных приемов также можно свести к транспортной задаче. [c.156]
Ограничение на мощность сверху может быть связано, например, с ограниченностью свободных трудовых ресурсов или ресурсов другого вида в этом населенном пункте. Затраты на производство единицы продукции меняются от пункта к пункту величину удельных затрат в i-м пункте обозначим через at (i = 1,. .., я). Тогда полные затраты на производство в i-м пункте при предположении о полном использовании мощностей (это предположение будем считать выполненным в нашей модели) равны произведению а . Пункты, где может быть осуществлено строительство новых мощностей, вообще говоря, не совпадают с пунктами потребления. Перевозка грузов требует затраты средств, величину которых мы будем оценивать таким же образом, как и в транспортной задаче, описанной во втором параграфе настоящей главы. Пусть кц — объем перевозки продукта из (-го пункта производства в /-и пункт потребления. Удельные затраты на такую перевозку будем считать заданными и равными Сц. Тогда полные затраты на перевозку между всеми пунктами производства и потребления равны сумме [c.170]
Венгерский метод в классическом варианте применим только для замкнутой модели транспортной задачи. Поэтому при разработке алгоритмов решения транспортной задачи с открытой или полуоткрытой системой ограничений исследовались и были определены эффективные методы предварительного построения замыкания исходной модели с последующим применением венгерского метода. В общем случае схема решения такой задачи представляет собой двухэтапную процедуру, где на первом этапе определяется замыкание модели, а на втором по замыканию модели отыскивается оптимум задачи. [c.135]
Интересно отметить, что в случае задач с транспортными ограничениями (5.5) может быть реализовано с помощью алгоритма балансировки [81]. [c.146]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
Транспортная задача и задача о назначениях - это частные задачи линейного программирования. Для них в принципе могут быть использованы общие методы решения ЛП-задач (например, симплекс-метод). Однако даже для относительно простых транспортных задач и задач о назначениях характерно большое число переменных решения. Для транспортных задач, имеющих практическое значение, применение таких общих методов может стать неэффективным. Вместе с тем особенности структуры данных и ограничений транспортной задачи обусловливают возможность применения специальных высокоэффективных алгоритмов ее решения. [c.118]
Сбалансированность и специальная структура ограничений транспортной задачи обусловливают важное свойство оптимального плана перевозок его следует искать только среди множества опорных планов. Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. В связи с этим алгоритм решения транспортной задачи разбивается на две стадии [c.145]
Машина Оптимум-2 (рис. 3.5) предназначена для решения транспортной задачи линейного программирования в общей постановке транспортной задачи с дополнительными ограничениями на время перевозок транспортной задачи с частично заменяемыми продуктами и неоднородной транспортной задачи позволяет определить [c.133]
Рассмотренные задачи линейного программирования формулировались и решались в предположении наличия полной информации. Их можно отнести к совокупности задач принятия решений в условиях определенности. Например, в транспортной задаче издержки Су, связанные с доставкой груза от /-го поставщика ку-му потребителю, считались фиксированной величиной. Если Ху — оптимальное значение переменной, определяющей объем перевозок груза от /-го поставщика ку -му потребителю, то общий вклад в издержки от транспортировки грузов равен произведению Су, которое также является фиксированной величиной, при заданном значении Ху. В реальных экономических условиях приходится решать отдельные задачи при ограниченности, неточности исходной информации о самом объекте и внешней среде, в которой он функционирует и развивается. [c.308]
Если в разобранной выше транспортной задаче одним из условий, па которых построены ограничения, является равенство единице всех коэффициентов при переменных в обоих видах ограничений (по потребностям и по объемам выпускаемой продукции), то в распределительной задаче такое ограничение наблюдается только в одном классе [213], а в другом эти коэффициенты могут быть любыми положительными числами. Подходя к распределительным задачам с этой точки зрения, можно сказать, что эти задачи могут рассматриваться как обобщенные транспортные задачи. [c.266]
Наиболее распространенным методом решения важных практических задач планирования и управления является линейное программирование. С помощью симплекс-метода решаются задачи планирования производственной программы предприятия, объединения, способствующие получению максимального эффекта при ограниченных материальных и трудовых ресурсах. Распределительный метод линейного программирования позволяет выбрать оптимальные варианты планов транспортных перевозок решать задачи по оптимизации планов загрузки оборудования и др. [c.78]
Одним из направлений совершенствования строительства является повышение заводской готовности изделий и конструкций, поступающих с заводов на строительную площадку. Эффект от этого прогрессивного процесса должен проявляться в сокращении трудоемкости и продолжительности работ на строительной площадке, а в ряде случаев и в некотором снижении стоимости строительства. Для завода изготовление продукции повышенной законченности всегда влечет увеличение затрат. Часто будут увеличиваться и затраты на перевозку и хранение изделий повышенной заводской готовности. Компенсацию этих дополнительных затрат заводу и транспортным организациям следует производить за счет экономии, образующейся в строительной организации, например, путем дифференциации цен на заводскую продукцию в зависимости от готовности изделий. Таким образом, возникает задача определения целесообразного уровня заводской готовности изделий. Повышение этого уровня будет целесообразным до тех пор, пока не нарушается одно из двух ограничений [c.303]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальный вид. Интересно, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи, и эти усилия увенчались успехом. В настоящее время умеют решать задачи транспортного типа значительно быстрее и с большим числом неизвестных, чем обычные задачи [c.151]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальную форму. Важно отметить, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи и эти усилия увенчались успехом. В настоящее время задачи транспортного типа удается решить значительно быстрее и с большим числом неизвестных, чем обычные задачи линейного программирования. Само название этой задачи связано с ее происхождением она возникла из задачи оптимальной перевозки грузов. [c.57]
С помощью методов потенциалов решим транспортную задачу, условия которой приведены на рис. 3.2, а. При этом будем считать, что ограничения на пропускные способности коммуникаций отсутствуют п коммуникации не имеют направления. [c.189]
Для решения задачи оптимального использования резервов в системе предприятий сборного железобетона разработан алгоритм с применением схемы транспортной задачи (рис. 4.17). Он построен с рядом логических ограничений, в частности, отыскания в резервных запасах необходимых изделий на складах нескольких заводов решение задачи идет по пути минимизации целевой функции не сразу, а лишь после того, как проверяется, не включены ли эти изделия в план поставок следующего оперативного периода. [c.236]
Транспортные задачи обычно связаны с анализом доставки товаров от разных источников по различным направлениям. Так, у предприятия может иметься несколько складов, предназначенных для отправки товаров в различные точки страны. В этом случае необходимо принять решение относительно оптимального способа передвижения этих товаров, с тем чтобы минимизировать затраты, время на перевозку и задействованные при этом ресурсы. Такого рода задача относится к отдельному типу задач линейного программирования. Мы имеем ряд ограничений, скажем, потребности точек назначения и наличие возможностей, и хотим минимизировать затраты. Поэтому мы можем сформулировать транспортную задачу как задачу линейного программирования и далее применить для получения решения симплексный метод. Однако в том, что касается перевозок, ограничения даются в особой форме, и целесообразен упрощенный метод решения. [c.288]
Тысячам предприятий, больших и малых, приходится ежедневно решать проблему, как наилучшим способом доставить товар потребителям, находящимся на разных расстояниях и в разных направлениях от предприятия, да еще с учетом объема заказанной партии товара. Постановку транспортной задачи можно описать как минимизацию затрат на эксплуатацию транспортных средств при существующих ограничениях на имеющееся их количество, грузоподъемность, продолжительность рабочего дня при необходимости обслужить как можно большее количество заказов. [c.110]
В статье [12] рассмотрена еще более общая модель, применение которой не ограничивается рамками задач транспортировки светлых нефтепродуктов. В этой модели по сравнению с предыдущей снимаются условия специфического прохождения отдельных видов транспорта (трубопроводов) и равенства удельных затрат транспортировки по этим трубопроводам различных продуктов. Это позволяет использовать модель для решения различных задач оптимизации перевозок многих продуктов несколькими видами транспорта. Каждый из этих видов транспорта может иметь как ограниченную, так и неограниченную пропускную способность на отдельных коммуникациях транспортной сети. Как и в предыдущей модели, предполагается необязательным баланс между наличием и спросом по продуктам, а сопоставляемые по отдельным коммуникациям показатели целевой функции (критерий оптимальности — минимум издержек) могут включать затраты собственно транспортировки, начально-ко- [c.70]
АССОЦИАЦИЯ -добровольное объединение (союз) предприятий, организаций или лиц для достижения общей хозяйственной, научной или какой либо другой цели. В хозяйственную АССОЦИАЦИЮ на добровольных началах могут входить научные, конструкторские, проектные организации,экспериментальные, производственные и транспортные предприятия, снабженческие и сбытовые организации. Участие в АССОЦИАЦИИ накладывает на предприятие менее жесткие ограничения, нежели в концерне. Любой участник АССОЦИАЦИИ без согласования с другими ее участниками может входить в другие договорные объединения предприятий. В отличие от других объединений в рамках АССОЦИАЦИИ не обязательно должен завершиться процесс создания и реализации конечного продукта. В их задачу в большей мере входит деятельность по [c.13]
Введение в транспортную задачу или в задачу о назначениях не свойственных им дополнительных ограничений приводит к тому, что эффективные "транспортные" методы решения таких задач (метод "северо-западного угла", циклические перестановки и т.п.) перестают быть применимыми. В этом случае задача будет решаться с помощью общих алгоритмов решения ЛП-задач (например, симплекс-методом). Помимо того что эти методы менее эффективны, они не могут гарантировать целочисленного решения, которое обычно предполагается в транспортной задаче и абсолютно необходимо в задаче о назначениях. Прямо е требование [c.143]
Транспортная задача, в которой имеет место равенство (25.32), называется закрытой и в качестве ЗЛП может быть решена с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. [c.525]
Система технического зрения может обеспечивать автономную систему управления транспортного средства информацией для определения ориентации, положения и скорости транспортного средства, кроме того, не только для транспортного средства непосредственно, но также для препятствий вокруг — статических или динамических. С развитием технологий и методов технического зрения такие системы становятся более доступными в терминах стоимости, размеров и веса. В настоящее время система технического зрения может быть выполнена как портативная система для автономного транспортного средства типа подвижного робота, автомобиля, самолета или вертолета. Портативные системы, как правило, имеют ограниченную вычислительную мощность и требуют дополнительной надежности. Таким образом, для системы технического зрения требуется надежный и простой алгоритм. Для упрощения задачи необходимо некоторое априорное знание. Это может быть гипотеза относительно текущего вида камеры. В этой работе мы только рассматриваем алгоритм извлечения особенностей и их прослеживания как первый шаг к созданию системы навигации самолета. Фактически, разработанная система может быть применена для выполнения некоторых воздушных операций типа автоматического полета вдоль автомобильных или железных дорог или береговой линии. [c.103]
При этом для каждого СП формируются и решаются сетевые транспортные задачи линейного программирования, подобные этапным задачам в детерминированном методе. Такая задача для каждого СП может решаться дважды — до и после проверки на реалистичность полученного при этом условно-оптимального плана. Если эта проверка показала плохое использование в этом плане некоторых существующих ГП, то в условия данной задачи вводятся дополнительные ограничения на величину соответствующих потоков. В результате нового решения задачи определяется реальный условно-оптимальный план, который и учитывается в дальнейшем при формировании зоны неопределенности . Все эти планы могут дополнительно группироваться с целью получения набора альтернативных вариантов развития ГСС, образующих зону неопределенности . Такая группировка может [c.152]
В математическую модель данной задачи вводят ряд ограничений по объемам поставок, лимитам капитальных вложений, общему расходу сырья. Результаты решения задачи, описанной этой математической моделью, должны быть подвергнуты анализу с учетом таких факторов (не учитываемых в условиях задачи), как обеспеченность рассматриваемых пунктов размещения трудовыми и водными ресурсами, строительной базой, загруженность транспортных путей и т. п. Предпочтительным считается вариант, обеспечивающий не только наименьшие совокупные приведенные затраты, но и наиболее полное использование природных ресурсов, рациональное использование трудовых ресурсов, специализацию и комплексное развитие экономического района. [c.202]
Vo T- e о о Vo Тогда задача сводится к исходной, если уменьшить di0 и -0 на величину Zi0j0 (естественно, что Xi0jg а п Xi0j0 .bj0 и решать задачу относительно поставок, которые заранее не фиксированы. При этом полезно определить, к каким потерям привело решение заранее зафиксировать некоторую поставку для этого надо решить транспортную задачу, не фиксируя эту поставку, и сравнить затраты в обоих случаях. Еще одно усложнение связано с ограничением сверху на величину некоторой перевозки пусть, скажем, для перевозки из пункта U в пункт /о выполняется v o oV Такое ограничение скорее всего может быть связано с ограниченностью пропускной способности пути, по которому перевозят грузы. Эту постановку при помощи некоторых искусственных приемов также можно свести к транспортной задаче. [c.183]
Известно, что если расширенная матрица условий (5.1) имеет линейно зависимые строки, то задача ЛП, как правило, некорректна. Напомним, что такой задачей ЛП является транспортная задача с замкнутой системой ограничений [93 j. Для задач ЛП общего вида в связи с этим заметим, что ввиду приближенного задания исходных данных условие независимости строк матрицы А практически непроверяемо. [c.144]
При решении транспортной задачи с помощью MS-Ex el "Поиск решения" автоматически выберет специальные эффективные алгоритмы решения и обеспечит целочисленность решения (без специального требования целочисленности ), если организация данных и введенные ограничения соответствуют транспортной задаче. [c.146]
ТЕОРИЯ РАСПИСАНИЙ — раздел оптимального планирования, относящийся к решению календарных задач, т. е. таких, в к-рых требуется оптимальным образом распределить во времени к.-л. планируемые процессы или действия. Т. р. — один из наиболее трудных и наименее разработанных разделов оптимального планирования. Практически осуществимый расчетный алгоритм разработан лишь для отдельных задач с небольшим числом переменных. Так, напр., разработан алгоритм для оптимального сезонного регулирования занятости и объема выпуска продукции при резких сезонных колебаниях спроса. Сущность задачи сводится к следующему. Заданы определенные размеры возможного сбыта изделия с распределением их по месяцам года. Приспособление размеров месячного выпуска к размерам сезонного спроса в условиях пром. произ-ва затруднительно и может быть осуществлено в относительно ограниченных размерах. Это приспособление достигается или сверхурочными работами, или работой на склад с накоплением сезонных запасов. И тот и другой способы требуют дополнительных расходов (в первом случае — на оплату сверхурочных работ, во втором — на хранение запасов и на оплату процентов за кредиты под сезонные запасы). Требуется разработать оптимальный график выпуска продукции по месяцам, к-рый, при заданном распределении сбыта по месяцам, потребует наименьших суммарных издержек на хранение продукции и на оплату сверхурочных работ. Алгоритм для решения этой задачи основывается на приведении ее к модели транспортной задачи линейного программирования (см. Перевозок план оптимальный). В этой модели месяц пройз-ва изделия и вид произ-ва (в нормированное или сверхурочное время) рассматриваются как пункт отправления , а месяц сбыта — как пункт назначения , роль оценочного элемента ( перевозочного тарифа ) здесь играют доплаты за часы сверхурочной работы и затраты на хранение продукции, изготовленной в запас. След, пример (см. табл. в тыс. шт.) иллюстрирует такой оптимальный график произ-ва, построенный исходя из заданного календарного графика спроса, наличной производств, мощности (без использования часов сверхурочной работы) и при условии, что стоимость хранения 1 тыс. шт. готовых изделий в течение одного месяца составляет 361 руб., а доплата за изготовление 1 тыс. шт. изделий в сверхурочное время составляет 1500 руб. [c.156]
Оптимизационные модели основаны на выборе критерия оптимальности, на основе которго путем сравнения различных вариантов выбирается лучший (оптимальный) вариант. Оптимизационная экономико-математическая модель состоит из целевой функции и системы ограничений. Целевая функция описывает цель оптимизации и отражает зависимость показателя, по которому ведется оптимизация, от независимых переменных (ограничений). Система ограничений отражает объективные экономические связи и зависимости и представляет собой систему равенств и неравенств, например, между потреблением ресурсов или величинами технико-экономических показателей и установленными лимитами, а также пределами выпуска продукции. Влияние каждой из переменных на величину целевой функции выражается коэффициентом-показателем, экстремум которого выступает критерием оптимальности. Примеры оптимизационных моделей в планировании и прогнозировании модели оптимизации развития и размещения производств, модели оптимизации структуры производства продукции отраслей промышленности, модели АПК, модели транспортных задач, с помощью которых осуществляется рациональное прикрепление поставщиков к потребителям и определяются минимальные транспортные затраты, и другие. [c.165]
В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда можегг быть выбрано целочисленным) будет оптимальным решением исходной целочисленной задачи линейного программирования. [c.219]
Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ, [c.160]
При получении решений оптимизации с помощью симплексного метода или методов решения транспортных задач их необходимо интерпретировать с точки зрения реальности и практического смысла. Так, возьмем задачу, которую мы уже рассматривали в этой главе относительно соотношения объемов выпуска различных моделей холодильников в компании Стенлюкс . На первом этапе мы определили количество каждой из моделей, которое необходимо производить, чтобы максимизировать прибыль при наличии ограничений по сырью и рабочему времени. Полученное решение дало оптимальное количество по производству каждой из моделей. В этом примере мы установили, что ежедневно необходимо производить 375 холодильников модели А470 и 937 холодильников модели А370, чтобы получить в итоге валовую прибыль в 82 470 долл. США. Полученные результаты необходимо проанализировать в свете ряда дополнительных факторов, и не всегда принимать их за данность. Так, прежде чем принять окончательное решение по оптимальному соотношению объемов выпуска, руководителю может потребоваться оценить эти результаты с учетом дополнительной информации. При этом необходимо учесть следующие факторы [c.302]
Общая математическая модель такой задачи может быть представлена в виде сетевой транспортной задачи линейного1 программирования с дополнительными ограничениями. Поставленные задачи были решены на ЭЦВМ БЭСМ-4 по программе,, реализующей алгоритмы К. И. Кима. Проведенное сравнение расчетных вариантов перевозок светлых нефтепродуктов, полученных при решении задач по разным показателям критерия оптимальности, с фактическими- перевозками, имевшими место-в базисном году, показали высокую экономическую эффективность использования предлагаемой экономико-математической модели. Как видно из табл. 2, экономические показатели работы транспорта по расчетным вариантам перевозок не имеют существенных различий. По величине затрат разница между ними колеблется в пределах 0,2—1,1%. Зато разница между расчетными вариантами и фактическим значительная по отдельным периодам года расчетные варианты обеспечивают снижение затрат против фактических в среднем на 7—13%. [c.31]
Предлагаемый порядок оперативного планирования рассчитан на широкое применение электронно-вычислительной техники. Разработанные экономико-математические модели могут быть реализованы на ЭВМ по стандартным программам. На первом этапе планирования в Главном вычислительном центре АСУнефтеснаб РСФСР предлагается решать сетевую транспортную задачу линейного программирования с дополнительными ограничениями, на втором этапе в кустовых вычислительных центрах этой организации — многопродуктовую транспортную задачу линейного программирования в матричной постановке. [c.33]
Почему так получилось Дело в том, что введенное дополнительное ограничение превратило нашу задачу о назначениях (по существу транспортную задачу) в обычную задачу линейного программирования. Для такой задачи специализированные "транспортные" методы решения неприменимы. А как указывалось раньше, только они обеспечивают целочисленные решения без введения явных требований целочисленности. Получившуюся общую ЛП-задачу MS-Ex el решают с помощью обычного симплекс-метода, а он отнюдь не гарантирует целочисленности переменных решения. [c.141]