При решении задачи линейного программирования достаточно часто оптимального решения получить не удается. Это происходит по двум причинам. Назовите их. 4 глава




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

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

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

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

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

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

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

 

Контрольные вопросы:

 

1. Сформулируйте постановку задачи. Какие критерии оптимальности могут быть при этом использованы?

2. Какие есть виды моделей оптимизации состава машинно-тракторного парка и его использования?

3. Какие отличия в системе моделей и ограничений имеются в моделях? Перечислите источники исходной информации для построения моделей.

 

 

Лекция № 5

 

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ АГРОИНЖЕНЕРНЫХ ОБЪЕКТОВ

 

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

2. Система переменных и ограничений, критерий оптимальности. Подготовка входной информации.

3. Математическая формулировка задачи. Построение структурной и числовой экономико-математической модели задачи.

4. Решение задачи по загрузке МТП на компьютере. Анализ результатов решения задачи.

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

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

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

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

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

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

2. Система переменных и ограничений, критерий оптимальности. Подготовка входной информации. Задачу линейного программирования можно решать аналитическими и графическими методами. Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задачи на компьютере. Их единственный недостаток заключается в том, что в отличие от графических методов, они совершенно не наглядны. Графические же методы достаточно наглядны, но они пригодны лишь для решения таких задач, в которых число переменных n = 2, что дает возможность представлять задачу на плоскости. Однако, учитывая наглядность графических методов, идею решения задачи линейного программирования мы рассмотрим с их помощью.

Рассмотрим простой пример. Как известно, уравнение прямой имеет вид

a1x1+a2х2=b (5.1)

 

Построим прямую 2x1+x2=2.

Для этого запишем уравнение в виде:

 

(5.2)

 

При такой форме записи в знаменателе показаны отрезки, которые отсекает прямая (5.3) на осях координат.

Если от уравнения (5.2) перейти к неравенству

 

2x12<2 (5.3)

 

Его можно представить графически, как это показано на рисунке 5.1.

 

Рисунок 5.1 – Графическое решение уравнения

 

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

На рисунке 5.1 часть плоскости, которая не удовлетворяет неравенству и расположена выше прямой, заштрихована. Координаты всех точек, принадлежащих не заштрихованной части плоскости, имеют такие значения х1 и х2, которые удовлетворяют заданному неравенству. Эта полуплоскость является областью допустимых решении (ОДР).

Построим теперь систему неравенств:

 

(5.4)

 

Для удобства построения запишем ее в форме уравнения в отрезках:

 

(5.5)

 

Эта система построена на рисунке 5.2, из которого следует, что решением этой системы являются координаты всех точек, принадлежащих ОДР, т. е. многоугольнику ABCDO.

 

Рисунок 5.2 – Графическое решение системы уравнений

 

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

На основании рассмотренного можно сделать исключительно важный вывод: оптимальным решением являются координаты вершины ОДР.

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

Эти правила, сформулированные на основании графического решения задачи на плоскости, т. е. в двухмерном пространстве, справедливы и для трехмерного. В этом случае ОДР представляет собой многогранник. Координаты каждой его вершины — это допустимые решения. Координаты той вершины, в которой целевая функция имеет максимальное (или минимальное) значение, являются оптимальным решением задачи. Для трехмерного пространства, где число переменных равно трем, это нетрудно себе представить. В практических же задачах число переменных может исчисляться десятками и даже сотнями. В этом случае никакое пространственное воображение не поможет. Что же делать? А выход один — решать задачу аналитически.

3. Математическая формулировка задачи. Построение структурной и числовой экономико-математической модели задачи.

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

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

В геометрии есть такое понятие "симплекс". Симплексом тела в k-мерном пространстве называют совокупность (k+1) его вершин. Так, для плоскости при k = 2 симплексом будут три вершины треугольника, при к=3 — четыре вершины четырехгранника и т. д. С учетом этого понятия аналитический метод решения задачи линейного программирования называют симплекс-методом. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине, называются итерацией.

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

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

Первую причину проиллюстрируем на следующем примере. Систему

 

(5.6)

 

представим графически (рисунок 5.3). На рисунке видно, что нет таких значений x1 и х2, которые удовлетворяли бы системе (5.6). Значит, в данном примере ОДР отсутствует.

Рисунок 5.3 – Графическое решение уравнений

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

Вторую причину рассмотрим на следующем примере. Построим систему

(5.7)

 

Эта система (5.7) показана на рисунке 5.4, из которого видно — ОДР не ограничена сверху.

Рисунок 5.4 – Графическое решение уравнений

 

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

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

F à max F< bi

2. При минимизации целевой функции она, соответственно, должна быть ограничена снизу

F à max F>bi

 

4. Моделирование оптимального использования машинно-тракторного парка. Рассмотрим методику оптимизации использования машинно-тракторного парка на примере.

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

 

Таблица 5.1 - Объемы и агротехнические сроки тракторных работ

Работы Объем га Агросроки Кол. смен
1.Закрытие влаги   с 25 апреля по 5 мая  
2.Предпосевная обработка   с 20 мая по 30 мая   1,5
3.Сев зерновых   с 20 мая по 30 мая   1,5
4.Зябь   с 25 августа по 25 сентября  
5.Перевозка зерна, тонны   с 25 августа по 10 сентября  

 

Таблица 5.2 - Нормативная наработка, га/смену

Работы К-701М Т-4А ДТ-75М
1.Закрытие влаги      
2.Предпосевная обработка      
3.Сев зерновых      
4.Зябь      
5.Перевозка зерна, тонны      

 

Таблица 5.3 - Стоимость тракторов, тенге

  К-701М Т-4А ДТ-75М
Стоимость      

 

Таблица 5.4 - Себестоимость единицы работы, тенге/га

Работы К-701М Т-4А ДТ-75М
1.Закрытие влаги      
2.Предпосевная обработка      
3.Сев зерновых      
4.Зябь      
5.Перевозка зерна, тг/тонны      

 

Решение:

Расчет необходимого количества машин проводится по наиболее напряженному периоду выполнения сельскохозяйственных работ. Для этого определяем периоды работ, которые идут параллельно. В нашем примере можно выделить три периода: первый период – один вид работы (закрытие влаги); второй период – два вида работ (предпосевная обработка и сев); третий период – два вида работ (зябь и перевозка зерна). Возможное число закупаемых тракторов обозначим: Х1 – К-701М; Х2 – Т-4А; Х3 – ДТ-75М.

Объем работ, выполняемых определенными марками обозначим последовательно Х4, Х5 и т.д. Например, объем работы по закрытию влаги, выполняемые тракторами К-701М обозначим Х4, тракторами Т-4А - Х5 и т.д. Для удобства принятые обозначения сведем в таблицу 5.5.

 

Таблица 5.5 - Шифровка переменных

Работы К-701М Т-4А ДТ-75М
1.Закрытие влаги Х4 Х5 Х6
2.Предпосевная обработка Х7 Х8 Х9
3.Сев зерновых Х10 Х11 Х12
4.Зябь Х13 Х14 Х15
5.Перевозка зерна, тг/тонны Х16 - -

 

В результате шифровки получено 16 переменных, значения которых необходимо определить при решении задачи.

Запишем ограничения.

I. Все виды работ должны быть выполнены в полном объеме. Например: закрытие влаги выполняется тремя марками тракторов. Суммарный объем работы должен быть не менее запланированного, т.е. 3680 га (таблица 5.1).

1. Следовательно, ограничение по данной работе будет иметь вид:

Х456 ³ 3680

Аналогично составляем ограничения и по другим видам работ.

2. Предпосевная обработка:

Х789 ³ 3680

3. Сев зерновых:

Х101112 ³ 3680

4. Зябь:

Х131415 ³ 1153

5. Перевозка зерна (планируется перевозить только тракторами К-701М):

Х16 ³ 4416

II. Весь объем работ должен быть выполнен покупаемыми машинами в агросрок.

6. В соответствии с установленными сроками выполнения работ закрытие влаги должно быть выполнено за 11 дней (таблица 5.1, с 25 апреля по 5 мая). Нормативная сменная наработка составила 71 га/смену (таблица 5.2). Количество смен – 2 (таблица 5.1). Данный вид работ не пересекается с другими видами. Следовательно, ограничение для трактора К-701М будет иметь вид:

7. Аналогично по тракторам Т-4А:

8. По трактору ДТ-75М:

9. Предпосевная обработка и посев выполняются в одни и те же агросроки. Поэтому в ограничении должны учесть одновременность их выполнения. По трактору К-701М:

 

10. По трактору Т-4А:

11. По трактору ДТ-75М:

12. Вспашка зяби и перевозка зерна также происходят одновременно. Поэтому ограничения по К-7101М будет выглядеть следующим образом:

13. По трактору Т-4А:

14. По трактору ДТ-75М:

Для того чтобы написать полученную модель в матричной форме необходимо ограничения второго (II) вида привести к общему знаменателю и провести простые математические преобразования.

После чего они примут вид:

6. Х4-1562×Х1 £ 0

7. Х5-968×Х2 £ 0

8. Х6-638×Х3 £ 0

9. Х7+0,871×Х10-1105,5×Х1 £ 0

10. Х8+0,857×Х11-693×Х2 £ 0

11. Х9+0,941×Х12-528×Х3 £ 0

12. Х13+1,118×Х16-930×Х1£ 0

13. Х14-372×Х2 £ 0

14. Х15-372×Х3 £ 0

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

ЦФ=0,1×4420000×Х1+0,1×2980000×Х2+0,1×2560000×Х3+115×Х4+121×Х5+ 121×Х6+129×Х7+138×Х8+165×Х9+235×Х10+241×Х11+269×Х12+257×Х13+ 322× Х14 +330×Х15+100×Х16 ® min.

В результате решения задачи получен план доукомплектования машинно-тракторного парка. На основе плана использования техники строят графики.

 

Контрольные вопросы:

1. Дайте определение целевой функции.

2. Дайте определение ГРУ и ОГР.

3. Что такое область допустимых решений?

При решении задачи линейного программирования достаточно часто оптимального решения получить не удается. Это происходит по двум причинам. Назовите их.

 

 

Лекция № 6

 

МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

 

1. Общие сведения о системах массового обслуживания.

2. Классификация систем массового обслуживания. Простейший поток требований. Время обслуживания. Расчетные формулы ТМО.

3. Сетевые модели. Сетевой график. События и работа. Критический путь.

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

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

Система массового обслуживания (СМО) – система в которую в случайные моменты времени поступают заявки. СМО имеет линии (каналы) обслуживания. Эти линии обслуживают заявку.

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

Исторически системы массового обслуживания и теория таких систем развивались в связи с задачами телефонии. Основоположником теории массового обслуживания считается известный датский ученый А.К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 г. работу "Теория вероятностей и телефонные переговоры", в которой решил ряд задач по теории систем массового обслуживания с отказами. Однако, в качестве предшественника А.К. Эрланга следует упомянуть Иоханнсена, чья статья "Время ожидания и число вызовов" вышла в свет в 1907 г.

Пример 1. Обслуживание абонента, снятие телефонной трубки – заявка на обслуживание линией телефонной сети.

Пример 2. Автозаправочная станция. Прибытие автомобиля – заявка на обслуживание. Бензоколонка – линия (канал) обслуживания заявки.

Пример 3. Посадка самолетов на взлетно-посадочные полосы. Прибытие самолета – заявка на обслуживание. Полосы – линии (каналы) обслуживания заявки.

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

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

В качестве характеристик эффективности функционирования СМО можно выбрать три основные группы (обычно средних) показателей:

Показатели эффективности использования СМО:

- Абсолютная пропускная способность СМО — среднее число заявок, которое сможет обслужить СМО в единицу времени.

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

- Средняя продолжительность периода занятости СМО.

- Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п.

Показатели качества обслуживания заявок.

- Среднее время ожидания заявки в очереди.

- Среднее время пребывания заявки в СМО.

- Вероятность отказа заявке в обслуживании без ожидания.

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

- Закон распределения времени ожидания заявки в очереди.

- Закон распределения времени пребывания заявки в СМО.

- Среднее число заявок, находящихся в очереди.

- Среднее число заявок, находящихся в СМО, и т.п.

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

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

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



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2018-09-18 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: