Основные свойства математических моделей

Ø Множественность и единство моделей.

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

Множественность объясняется, необходимостью исследования различных свойств системы (необходимостью решения различных задач исследования).

В качестве примера из квантовой физики. Нильс Бор в 1913 году построил графическую модель ядра водорода, которая предполагает наличие стационарных орбит движения электрона, и достаточно хорошо описывает свойства его поведения как частицы. Модель Шредингера (уравнение Шредингера) определяет вид волновой функции, то есть фактически описывает поведение электрона как волны. Это пример множественности моделей одного объекта для описания различных свойств (корпускулярные и волновые свойства элементарных частиц).

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

Например, рассмотрим самую простую линейную зависимость

Это простейший вид функциональной зависимости – прямая пропорциональная зависимость переменной Y от переменной Х, к – коэффициент пропорциональности.

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

Рис. 4. Пропорциональная зависимость

 

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

 

 

Рис. 5 Схема трансформатора

 

Отношение абсолютных значений напряжений U2 и U1 на концах вторичной и первичной обмоток при холостом ходе называется коэффициентом трансформации - k. Формула для трансформатора такова

, или

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

Эта та же формула может служить моделью и другой системы. Например, моделью рычага

Рис.6. Схема рычага

Рычаг описывается следующим соотношением

или

Если различные объекты имеют одинаковую модель, то возможно моделировать один объект другим.

Ø Свойство конечности (приблизительности) моделей.

Модель отображает оригинал лишь в конечном числе его отношений. Любая модель имеет ограничения. Эти ограничения устанавливает разработчик в зависимости от целей исследования.

Формула не может описывать всех свойств системы. Формула (модель) должна быть адекватна только исследуемым свойствам объекта.

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

Рис. 7. Эффекта гистерезиса.

Действительность отображается моделью всегда грубо или приблизительно, поскольку модель – это абстракция. Она по определению всегда является лишь относительным, приближенным подобием системы-оригинала и в информационном отношении принципиально беднее последней. Это ее фундаментальное свойство.

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

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

Ø Адекватность и эффективность моделей.

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

Под эффективностью понимают практическую полезность - имеется ли совпадение результатов моделирования с наблюдаемыми фактами (с заданной степенью точности), или не имеется.

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

Нельзя построить модель, которая бы отражала все свойства объекта. Это может сделать только сам объект. Поэтому, любая модель имеет рамки применимости. Модель должна быть адекватна только относительно выбранных (моделируемых) свойств объекта. Эффективность можно определить только проверкой.

Проверка эффективности модели называется верификацией.

Иногда верификация представляет достаточно сложную процедуру. Например, верификация моделей долгосрочного прогнозирования и планирования экономических процессов. Долгосрочное планирование осуществляется на 10-15 лет. Ведь нельзя же столько лет ожидать наступления событий, чтобы проверить правильность предпосылок модели. В таких ситуациях используется метод моделирования по «предпрошлым» данным.

Ø Свойство достаточной простоты

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

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

Чрезмерная точность модели на практике не менее вредна, чем её неполнота и грубость.

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

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

 

Ø Устойчивость моделей.

Это свойство системы сохранять значения параметров в допустимых пределах при незначительном воздействии возмущающих факторов.

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

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

Поясним это на конкретном примере.

Нельзя вычислить массу очков, взвесив человека в очках и без них, а затем взяв разность результатов. Масса очков составляет 0, 1% от веса человека. В то время, как погрешность весов – 1%. Поэтому, погрешность измерения веса очков превышает измеряемую величину в 10 раз.

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

 

Востребованность моделей.

Модели появляются не просто так, а когда они нужны.

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

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

И только 230 лет спустя, в 1903 году Циолковский опубликовал первое математическое исследование ракетного движения.

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

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

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

, или .

Решение этого дифференциального уравнения имеет вид:

,

где m₀ – начальная масса ракеты, определяемая из начального условия при старте v=0.

Таким образом, скорость ракеты выражается формулой:

.

Это формула Циолковского. Данная модель объясняет, как нарастает скорость ракеты по мере сжигания топлива. Характер процесса нагляднее всего уяснить с помощью графика (Рис6), показывающего изменение скорости с уменьшением массы ракеты.

Рис.8. Изменение скорости ракеты

Приведенная модель достаточно проста, поскольку не учитывает сопротивление воздуха, земное тяготение. Учет их резко усложняет модель и анализ результатов решения. Решение лежит на поверхности, но оно возникло только тогда, когда появилась проблема. Точно так при решении практических задач возникают открытия. А решение может оказаться очень простым.

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

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

Люди начали пользоваться, например, математическими моделями еще до осознания математики как самостоятельной науки – достаточно вспомнить исчисление площадей в Древнем Египте. Как только начала развиваться цивилизация, так человек решая практические задачи начал использовать модели объектов (планировка городов, строительство зданий, и т.п.).

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

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

 

 

ТЕМА 4

МОДЕЛИ ЗАДАЧ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

Основные положения.

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

Операция – любое управляемое мероприятие, направленное на достижение цели.

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

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

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

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

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

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

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

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

 

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

Цель исследования операций — предварительное количественное обоснование оптимальных решений.

Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности. Его называют целевой функцией, обозначать будем так - W.

Если показатель эффективности желательно максимизировать (минимизировать), то будем записывать это так:

Например, задача операции обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности W — суммарные расходы на перевозки сырья за единицу времени. .

Показатель эффективности зависит только от двух групп параметров: от множества заданных условий – Аи множества элементов решения – Х, то есть

В числе условий А фигурируют и ограничения, налагаемые на элементы решения. Пусть решение Х представляет собой совокупность n элементов решения х,, х₂, ..., х_п:

Требуется найти такие значения х₁, х₂, ..., х_n, которые обращают величину W в максимум или в минимум (то есть найти «экстремум»). Это и есть математическая интерпретация задач ИСО.

 

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

Самыми простыми среди задач ИСО являются так называемые задачи линейного программирования. Для них характерно:

· целевая функция W линейно зависит от элементов решения х₁, х₂, ..., х_n

· ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно элементов решения.

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

Для примера, задача о пищевом рационе.

Ферма производит откорм скота. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно с₁, с₂, с₃, с₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков - не менее b₁ единиц; углеводов — не менее b₂ единиц; жиров — не менее b₃ единиц.

Таблица 2.

Про-	Элементы
дукты	белки	углеводы	жиры
П1	а11	а12	а13
П2	а21	а22	а23
П3	а31	а32	а33
П4	а41	а42	а43

 

Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров a_ij(в единицах на единицу продукта) известно и задано в таблице.

Требуется составить такой пищевой рацион (т. е. назначить количества продуктов П₁, П₂, П₃, П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Составим математическую модель. Обозначим х₁, х₂, х₃, х₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Целевую функцию требуется минимизировать. Она линейно зависит от элементов решения.

, или

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

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения х₁, х₂, х₃, х₄.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х₁, х₂, х₃, х₄, чтобы они удовлетворяли ограничениям — неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

Это и есть математическая модель нашей задачи о рационе.

Классически, такие задачи решают симплексным методом.

 

Графическое решения задачи линейного программирования.Кооператив выпускает два вида продукции – стекло и пенопласт. Трудозатраты на производство стекла – 20ч., пенопласта – 10ч. В кооперативе работают 10 рабочих по 40 ч. в неделю. Оборудование позволяет производить не более 15 т стекла и 30 т пенопласта в неделю. Прибыль от реализации 1 т стекла – 50 руб.; 1т пенопласта – 40 руб. Сколько материалов необходимо выпустить для получения максимальной прибыли?

Математическая модель представляется следующей системой уравнений:

 

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

 

х₂

 

 

5 х₁

5 10 15 20 25

Рис.9. Множество допустимых решений.

 

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

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

В нашем примере оптимальным решением является вершина с координатами (5; 30). W(5, 30)=1450.

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

 

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

Транспортная задача (ТЗ) – частный случай задачи линейного программирования. В ТЗ существуют поставщики и потребители грузов. У каждого поставщика имеется определенное количество груза – мощность поставщика, а каждому потребителю нужно определенное количество груза – спрос потребителя. Известны затраты на перевозку единицы груза. Нужно составить такой план перевозок, при котором суммарные затраты на перевозку груза будут минимальными, по возможности будут задействованы все мощности поставщика и удовлетворен весь спрос потребителей.

Модель задачи.

Введем следующие переменные.

a_i – мощность поставщика (предложения продукта в пункте i=1, …, n), n – количество поставщиков.

b_j – спрос потребителя (в пункте j=1, …, m), m – количество потребителей.

c_ij - затраты на перевозку единицы продукции из пункта i в пункт j.

x_ij - количество груза, перевозимого из пункта i в пункт j.

В этих обозначениях транспортную задачу можно записать следующим образом.

Закрытая модель ТЗ (сбалансированная модель) – модель, в которой суммарная мощность поставщиков равна суммарному спросу потребителей.

Общий спрос равен общему предложению (мощности всех поставщиков).

Открытая модель ТЗ (не сбалансированная модель) – модель, в которой суммарная мощность поставщиков не равна суммарному спросу потребителей.

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

Алгоритм решения закрытой модели ТЗ:

Составляется специальная таблица поставщиков и потребителей с указанием их мощностей и спросов;

Находим первоначальный план поставок. Существует несколько методов построения плана:

- метод северо-западного угла;

- метод минимальной стоимости;

- метод потенциалов.

Оптимизируем план распределительным методом.

Алгоритм рассмотрим на конкретном примере.

Имеется 4 поставщика А и 5 потребителей В. Мощности поставщиков и спрос потребителей, а также затраты на перевозку единицы груза для каждой пары поставщик-потребитель сведены в таблицу поставок:

 

Таблица3

Потр   Пост	В1	В2	В3	В4	В5	Мощ- ноть ai
А1
А2
А3
А4
Спрос bj

 

– искомый объем поставок i-го поставщика j-ому потребителю ( ).

Запишем ограничения (уравнения баланса для каждой строки таблицы поставок):

 

Уравнения баланса для каждого столбца таблицы поставок:

 

Целевая функция - суммарные затраты W на перевозку выражается через коэффициенты затрат

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

План (х_ij)будем называть оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок W = min.

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

По мере заполнения этой таблицы в ее клетках проставляются сами перевозки х_ij Транспортная таблица состоит из т строк и п столбцов. В каждой клетке мы будем ставить стоимость перевозки единицы груза из Ав В (правый верхний угол), а центр клетки оставим свободным, чтобы помещать в нее саму перевозку х _{i, j}. Клетку таблицы, соответствующую пунктам А и Вбудем кратко обозначать (i, j).

Прежде всего займемся составлением допустимого плана. Это в транспортной задаче очень просто: можно, например, применить так называемый «метод северо-западного угла».

 

 

Таблица 4

ПОТ ПОСТ	В1	В2	В3	В4	В5	Мощность ai
А1	1813	12 7
А2		15 8	33 12		8
А3			910	118
А4				410	2615
Спрос bj

 

Начнем заполнение транспортной таблицы с левого верхнего угла. Пункт В₁ подал заявку на 18 единиц груза; удовлетворим ее из запасов пункта А₁. После этого в нем остается еще 30 — 18 = 12 единиц груза; отдадим их пункту В₂. Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта А₂ и т. д. Рассуждая точно таким же образом, заполним до конца перевозками х_ij транспортную таблицу (таблица 5).

Проверим, является ли этот план допустимым. Да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения (все заявки удовлетворены, все запасы израсходованы). Сумма запасов равна сумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы.

Проверим, является ли этот план допустимым. Да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения (все заявки удовлетворены, все запасы израсходованы). Сумма запасов равна сумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы.

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

Проверим, можно ли таким планом пользоваться? Является ли система уравнений (ограничений – условий) совместной. Число свободных клеток с нулевыми перевозками в таблице должно быть равно (т — 1)(п — 1) = 3х4 = 12. Если не так, то меняют угол, или меняют метод. При выполнении этого условия план называют опорным.

Теперь проверим план на оптимальность, т. е. минимальна ли для него общая стоимость перевозок? Скорее всего, нет (ведь составляя план, мы совсем не думали о стоимостях). Так и есть — план не оптимальный. Например, сразу видно, что можно его улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12, но зато увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6.

Например, перенесем 11 единиц груза по циклу (2.3) —(2.4) — (3.4) — (2.3) —(2, 3). Чтобы план оставался опорным, мы должны заполнить одну из свободных клеток, а одну из занятых освободить. Сколько единиц груза можем мы перенести по циклу? Очевидно, не больше чем 11 единиц (иначе перевозки в клетке (3.4) стали бы отрица­тельными). В результате циклического переноса допустимый план остается допустимым — баланс запасов и заявок не нарушается.

 

Таблица 5

22 12	116
2010	8

 

Посмотрим, чего мы добились, сколько сэкономили.

Была стоимость: 33х12+11х8+9х10=574.

Стала стоимость: 22х12+11х6+20х10=530.

Мы уменьшили стоимость перевозок на 44 единицы. Это значение называется отрицательной ценой цикла. Общая стоимость плана составила W=1398

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

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

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

 

Задача управления запасами.

Чтобы процесс производства протекал непрерывно и независимо от поставок сырья необходимо, чтобы на месте производства был создан некоторый запас этого сырья. Тогда ставится вопрос: каков должен быть объем этих запасов?

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

Постановка задачи.Однопродуктовая задача, с удорожанием продукции.

Имеется склад готовой продукции. Будем считать, что на складе хранится запас однотипной продукции, например, мешки с цементом. Спрос на этупродукцию - равномерный и постоянный. Известен годовой спрос на эту продукцию (потребность на год). Однако хранить годовой запас не выгодно – стоимость хранения велика. В связи с этим, на складе изначально хранится запас меньше годового спроса и он пополняется по мере расходования.

 

Рис. 10 График годового спроса

 

Пополняется склад при снижении запасов до некоторого уровня путем организации нового заказа. Объем заказа— это количество заказываемой продукции. Время выполнения этого заказа на пополнение склада (время поставки) будем считать постоянным. Каждый раз заказывается постоянное количествомешков. Известна стоимость подачи заказа (издержки на доставку – накладные расходы) и стоимость хранения одной единицы продукции.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. I. Основные решения по рекламе
2. I.2. Структура педагогической науки и её основные отрасли
3. II Основные общие и обзорные представления, понятия, положения психологии
4. II. ЭКЗАМЕН ПО ОБЩЕСТВОЗНАНИЮ: ОСНОВНЫЕ ЭЛЕМЕНТЫ ПРОВЕРКИ
5. А. Основные клинические формы
6. Авторское право: понятие, объекты, признаки и основные разновидности
7. Артериальные гипертензии, ее виды, основные патогенетические механизмы нейрогенной гипертензии.
8. Архитектура XX века. Основные проблемы
9. Базы данных. Виды БД по характеру хранимой информации, по способу хранения, по структуре организации. Основные типы данных.
10. Борьба за власть в руководстве страны в 20-х гг.: основные этапы, итоги.
11. ВЕКТОРЫ И МАТРИЦЫ. ОСНОВНЫЕ ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ
12. Векторы и матрицы. Основные числовые характеристики.