Е
В Д
А Б Г Ж
Рисунок 6.2 – График построения оптимального плана некоторого объекта
На рисунке приведен сетевой график задачи моделирования и построения оптимального плана некоторого объекта.
Чтобы решить эту задачу, необходимо провести следующие задачи:
А – сформулировать проблему исследования,
Б – построить математическую модель изучаемого объекта,
В – собрать информацию,
Г – выбрать метод решения задачи,
Д – построить и отладить программу на ЭВМ,
Е – рассчитать оптимальный план,
Ж – передать результаты расчета заказчику.
Цифрами на графике обозначены номера событий, к которым приводит выполнение соответствующих работ.
Из графика следует, что работы В и Г можно начать выполнять независимо одна от другой только после свершения события 3, т.е. когда выполнены работы А и Б; работу Д – после свершения события 4, когда выполнены работы А, Б и Г; а работу Е можно выполнить только после наступления события 5, т.е. при выполнении всех предшествующих ему работ А, Б, В, Г и Д.
Замечания: в рассмотренных примерах сетевые графики состояли из работ и событий. Однако может быть и иной принцип построения сетей – без событий. В такой сети вершины графа (например, изображенные прямоугольниками) означают определенные работы, а стрелки – зависимости между этими работами, определяющие порядок их выполнения.
Сетевой график обладает следующими основными свойствами:
а) ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы;
б) ни одна работа, выходящая из данного события, не может начаться до тех пор, пока не произойдет данное событие;
в) ни одна последующая работа не может начаться раньше, чем будут закончены все предшествующие ей работы.
4. Сетевые графики составляются на начальном этапе планирования. Вначале: - планируемый процесс разбивается на отдельные работы;
- составляется перечень работ и событий;
- продумываются их логические связи и последовательность выполнения;
- работы закрепляются за ответственными исполнителями. С их помощью оценивается длительность каждой работы.
- составляется (сшивается) сетевой график;
- после упорядочения сетевого графика рассчитываются параметры событий и работ, определяются резервы времени и критический путь.
- проводятся анализ и оптимизация сетевого графика, который при необходимости вычерчивается заново с пересчетом параметров событий и работ.
При построении сетевого графика необходимо соблюдать ряд правил:
В сетевой модели не должно быть «тупиковых» событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события (рисунок 6.3).
Рисунок 6.3 – Сетевая модель с «тупиковым» событием
Здесь либо работа (2,3) не нужна и ее необходимо аннулировать, либо не замечена необходимость определенной работы, следующей за событием 3 для свершения какого-либо последующего события.
В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения.
В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа (рисунок 6.4).
Рисунок 6.4 – Сетевая модель с «хвостовым» событием
Здесь работы, предшествующие событию 3, не предусмотрены. Поэтому событие 3 не может свершиться, а следовательно, не может быть выполнена и следующая за ним работа (3,5).
Обнаружив в сети такие события, необходимо определить исполнителей предшествующих им работ и включить эти работы в сеть.
В сети не должно быть замкнутых контуров (в) и петель (рисунок 6.5), т.е. путей, соединяющих некоторые события с ними же самими (г).
При такой ситуации необходимо вернуться к исходным данным и путем пересмотра состава работ добиться его устранения.
Рисунок 6.5 – Сетевая модель с замкнутым контуром (в) и петлей (г)
Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой (рисунок 6.6).
Рисунок 6.6 – Пример решения ситуации
Нарушение этого условия происходит при изображении параллельно выполняемых работ (д). Если эти работы так и оставить, то произойдет путаница из-за того, что две различные работы будут иметь одно и то же обозначение (1,2).
В этом случае рекомендуется ввести фиктивное событие (событие 2*) и фиктивную работу (работа 2*, 2), при этом одна из параллельных работ (1, 2*) замыкается на это фиктивное событие. Фиктивные работы изображаются на графике пунктирными линиями.
В сети рекомендуется иметь одно исходное и одно завершающее событие (рисунок 6.7).
Рисунок 6.7 – Пример решения ситуации
Если в составленной сети это не так (ж), то добиться желаемого можно путем введения фиктивных событий и работ (з).
Фиктивные работы и события необходимо вводить и в ряде других случаев. Один из них – отражение зависимости событий, не связанных с реальными работами. Например, работы А и Б (рисунок 6.7, и) могут выполняться независимо друг от друга, но по условиям производства работа Б не может начаться раньше, чем окончится работа А. Это обстоятельство требует введения фиктивной работы С.
Другой случай – неполная зависимость работ. Например, работа С требует для своего начала завершения работ А и Б, но работа Д связана только с работой Б, а от работы А не зависит. Тогда требуется введение фиктивной работы Ф и фиктивного события 3 (рисунок 6.7, к).
Рассмотрим пример. Задача замены автомобильного парка
Фирма по прокату автомобилей планирует замену авт.парка на очередные 5 лет. Автомобиль должен проработать не менее 1 года, прежде чем фирма поставит вопрос о его замене. На рисунке 6.8 приведены стоимости замены автомобилей (усл. ед.), зависящие от времени замены и количества лет, в течение которых автомобиль находился в эксплуатации.
Определить план замены автомобилей, обеспечивающий при этом минимальные расходы.
Решение:
Найдем минимальные расстояния:
U1= 0
U2=U1+d12=0+4=4,
U3=min (U1+d13; U2+d23)=min (0+5,4; 4+4,3)=5,4
U4=min (U1+d14; U2+d24; U3+d34)=min(0+9,8; 4+6,2; 5,4+4,8)=9,8
Рисунок 6.8 – Стоимость замены автомобилей (у.е.)
U5=min (U1+d15; U2+d25; U3+d35; U4+d45)= min (0+13,7; 4+8,1; 5,4+7,1; 9,8+4,9)= 12,1.
Кратчайший путь 1-2-5 со стоимостью 12,1 усл.ед. Это означает, что каждый автомобиль заменяется через 2 года, а через 5 лет – списывается.
Построить сетевой график ремонта трактора при следующем (упрощенном) перечне работ (таблица 6.1). Первым этапом в составлении сетевого графика является расчленение проекта на отдельные операции, составление полного перечня подлежащих выполнению работ. В данном примере (очень сильно упрощенном) этот этап кажется легким, но если нет полного перечня работ, если упущена какая-то, пусть даже незначительная на первый взгляд работа, все преимущества сетевого графика теряются. Любая работа связана с затратами времени, следовательно, имеет начало и конец, которые легко поэтому определяются и наносятся на график.
Но прежде чем строить график, необходимо установить очередность работ. Перечень операций (работ) обычно составляется в зависимости от последовательности, в которой они совершаются, и поэтому служит отправным пунктом в установлении их очередности. Очередность устанавливается в ходе получения ответа на два вопроса: что должно предшествовать данной работе? Что должно следовать за данной работой (зачем эта работа)?
Очень важно строго обосновывать очередность работисходя из целей проекта, а не на основе сложившихся традиций и обычаев. Но нужно помнить, что очередность очень сильно зависит от местных условий предприятия и пренебречь этим нельзя. Это хорошо видно в рассматриваемом примере: на отдельных предприятиях ремонт ходовой части и заднего моста объединен, а на большинстве предприятий имеем, наоборот, гораздо большую специализацию при ремонте отдельных узлов трактора. После составления перечня работ и очередности, которая задается показателем — какие работы предшествуют данной работе, т. е. на какие работы опирается (столб. 5, таблица 6.1), строят сетевой график, на который наносятся события в установленной последовательности и работы — без масштабные стрелки, на которых указывается продолжительность выполнения работ.
Таблица 6.1 – Данные для построения сетевого графика ремонта трактора
| № | Виды работ | Условное обозначение работы | Номер работы | Опирается на работу, № | Продол- Житель-ность, час | |||
| Подготовка трактора к ремонту | а1 | |||||||
| Разборка трактора на основные узлы | а2 | |||||||
| Разборка и дефектовка деталей двигателя | а3 | |||||||
| Разборка и дефектовка деталей трансмиссии и ходовой части | а4 | |||||||
| Разборка и дефектовка деталей заднего моста | а5 | |||||||
| Комплектовка деталей двигателя | а6 | |||||||
| Комплектовка деталей трансмиссии и ходовой части | а7 | |||||||
| Комплектовка деталей заднего моста | а8 | |||||||
| Сборка и испытание двигателя | а9 | |||||||
| Сборка и испытание трансмиссии и ходовой части | а10 | |||||||
| Сборка и испытание заднего моста | а11 | |||||||
| Сборка трактора из узлов и обкатка | а12 | 9,10,11 | ||||||
| Покраска | а13 | |||||||
| Приемка трактора из ремонта | а14 | 0,5 | ||||||
Техника вычерчивания сетевых графиков весьма разнообразна. Можно назвать следующие эффективные приемы вычерчивания сетевых графиков: для выделения общего потока на диаграмме несколько видов работ иногда отображаются с помощью одной стрелки. Расчленение последней на отдельные операции проводится после проверки общей последовательности выполнения работ; очень крупные проекты целесообразнее составлять по частям (сегментам общего сетевого графика), а затем объединять их в единый график. Подобный подход обычно применяется в отношении тех частей проекта, которые многократно повторяются, например, при строительстве многоэтажного дома, на этажах перечень работ одинаков, поэтому вычерчивают лишь один сетевой график по общему перечню работ (рисунок 6.9).
Рисунок 6.9 - Сетевой график ремонта тракторов
4. Сведение задач сетевого планирования к оптимизационным. Области применения сетевых моделей для решения агроинженерных задач.
Одна из основных задач сетевого планирования состоит в определении критического пути. Критическим путем в сетевом планировании называют последовательность технологических взаимосвязанных работ от начального до конечного события, имеющую максимальную продолжительность. Т. е. критическим путем называют самый большой путь из всех полных путей (путей, начинающихся с исходного и кончающихся завершающим событием). Работам, лежащим на критическом пути, уделяется особое внимание, поскольку всякая задержка в выполнении любой из работ, лежащих на критическом пути, приводит к срыву срока окончания всего комплекса работ. Поэтому такой метод планирования называют иногда методом критического пути. Для рассматриваемого примера найдем критический путь, определив время выполнения работ по каждому из трех полных путей (ветвей):
верхний (а1 –а2 –а3 –а6 –а9 –а12 –а13 –а14) — Т1 =76,5 ч;
средний (а1 –а2 –а4 –а7 –а10 –а12 –а13 –а14) — Т2 =78,5 ч;
нижний (а1 –а2 –а5 –а8 –а11 –а12 –а13 –а14) — Т3=68,5 ч,
где индексы: 1—верхней, 2—средней, 3—нижней ветвей.
Наибольшее время выполнения работ получим на средней (2-й) ветви графика, этот путь и является критическим: Ткр=Т2 = =78,5 ч. В нашем примере особое внимание нужно уделять работам а4, а7 и а10 (ремонту ходовой части и трансмиссии), которые определяют общую длительность ремонта трактора. Знание Ткр позволяет найти резерв времени по каждой ветви: 1-й (верхняя) Т1=2 ч, 3-й (нижняя) Тз=10 ч.
Наибольший резерв времени имеется на нижней ветви: Тз=10 ч. За счет этого резерва можно, перераспределив рабочие ресурсы, сократить время выполнения работ на критическом пути и на верхней ветви.
В сетевом планировании обычно устанавливаются три оценки времени, необходимого для выполнения работ: оптимистическая (продолжительность работы при самых благоприятных условиях) tmin, пессимистическая (продолжительность работы при самых неблагоприятном стечении обстоятельств) — tmax и наиболее вероятная (продолжительность работы при условии, что не возникает никаких неожиданных трудностей) — tнв. Существование данных оценок обусловлено вероятностным характером работ. В сетевых графиках обычно используется так называемая ожидаемая продолжительность работ — toж, определяемая по формуле
Сетевой график может быть использован для улучшения (оптимизации) плана. Однако цели оптимизации могут быть разные. Одной из задач является сокращение сроков выполнения проекта. Очевидно, для этого имеет смысл фиксировать именно работы критического пути, снижение длительности которых непосредственно влияет на сроки выполнения проектов. Однако при этом может оказаться, что критическим путем станет другая ветвь графика. Кроме того, форсирование работы требует вложения определенных средств. В результате возникает задача исследования операций: какие дополнительные средства необходимы и в какие работы требуется их вложить, чтобы общий срок выполнения работ по плану был бы не больше заданий величины, а расход дополнительных средств был бы минимальным.
Другая задача—перераспределение имеющихся ресурсов с целью сокращения общего времени выполнения плана работ. На рассмотренном примере установили, что все работы, кроме работ критического пути, имеют какие-то резервы времени. В некоторых случаях оказывается возможным, перебросив материальные и трудовые ресурсы с некритических участков работ на критические, добиться уменьшения суммарного времени выполнения плана. Вновь приходим к задаче оптимального управления: какие ресурсы надо перебросить с каких работ и на какие, чтобы время выполнения всего плана было бы минимальным.
Контрольные вопросы:
1. Дайте классификацию систем массового обслуживания.
2. Перечислите элементы систем массового обслуживания.
3. Что такое сетевой график, работа, событие?
4. Дайте определение критического пути.
5. Перечислите три оценки времени при сетевом планировании.
Лекция № 7
МОДЕЛИРОВАНИЕ ТРАНСПОРТНЫХ ПРОЦЕССОВ В АГРОИНЖЕНЕРНОЙ СИСТЕМЕ
1. Экономическая и математическая постановки транспортной задачи.
2. Методы решения транспортной задачи.
3. Методы построения опорного плана. Расчет плана с нарушенным балансом. Задача оперативного планирования перевозок.
4. Производственно-транспортная задача. Выбор методов оптимизации планов перевозок.
1. Экономическая и математическая постановки транспортной задачи. С уществуют такие классы задач, которые могут быть решены простыми методами, представляющими частные случаи симплексного метода. К таким задачам линейного программирования относится транспортная задача.
Название данного класса задач обусловлено тем, что этот метод вначале был разработан применительно к организации перевозок грузов.
Общая постановка транспортной задачи такова.
Имеются m пунктов отправления A1, А2...., Am, на которых сосредоточено определенное количество однородного продукта а1, а2,… am. Имеются n пунктов потребления B1, В2,..., Вn, потребность которых в этом продукте b1, b2,..., bn. Если общая сумма продукта в пунктах отправления равна общей потребности в нем всех пунктов потребления:
a1+a2 +... + am=b1+b2+...+bn,
то такая модель называется закрытой, а если не равна, то модель называется открытой. При решении задачи открытая модель всегда приводится к закрытой путем введения фиктивного пункта отправления или потребления.
Из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления, причем стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт потребления Cij известна.
Итак, транспортная задача ставится следующим образом.
Найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:
- мощности всех поставщиков были реализованы,
- спросы всех потребителей были удовлетворены,
- суммарные затраты на перевозку были бы минимальными.
Требуется составить такой план перевозок, при котором общие транспортные расходы были бы минимальными. При этом весь продукт из пунктов отправления должен быть вывезен, а потребности каждого потребителя удовлетворены полностью.
За неизвестные здесь принимаются перевозимые объемы грузов. Обозначим через x11 количество продукта, отправляемого из пункта А1 в пункт B1, x12 из пункта А1 в пункт В2 и т. д. Вообще через xij обозначим количество продукта, отправляемого из i-го пункта отправления в j-й пункт потребления. Тогда неизвестными в задаче будут mхn неотрицательных переменных величин: xij(i=1,2,...,m; j=1,2,...,n).
Если запасы в пунктах отправления равны a1, a2,..., am, потребности в пунктах потребления — b1, b2,... bn, то все условия задачи математически запишутся следующим образом:
Ограничения по запасам:
x11+x12+…+x1n=a1
x21+x22+…+x2n=a2
………………….
xm1+xm2+…+xmn=am
Данная запись означает, что суммарное количество груза, направленного из каждого пункта отправления во все точки назначения, должно быть равно запасу груза в данном пункте отправления.
Ограничения по потребностям:
x11+x21+…+xm1=b1
x12+x22+…+xm2=b2
…………………
x1n+x2n+…+xmn=bn
Данная запись означает, что суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом.
Особенности математической модели транспортной задачи:
- система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме),
- коэффициенты при переменных системы ограничений равны 1 или 0,
- каждая переменная входит в систему ограничений два раза.
Требуется найти такое неотрицательное решение системы m+n уравнений, при котором линейная форма достигает минимума:
Zmin=c11x11+ c12x12+…+ c1nx1n+ c21x21+ c22x22+…+ cm1xm1+ cm2xm2+…+ cmnxmn
Все условия задачи можно свести в табличную форму.
Получили математическую модель транспортной задачи. Ограничения по наличию ресурсов записываются по строкам, а ограничения по потреблению их - по столбцам.
По данной схеме составляют математические модели для всех транспортных задач. Иногда в модель вводятся дополнительные ограничения, в частности ограничения на отдельные величины xij.
Для решения конкретных транспортных задач, во-первых, все ограничения по строкам и по столбцам и значения неизвестных величин должны иметь одинаковую размерность—тонны, тонно-километры, гектары и т. д.; во-вторых, оценки целевой строки по всем неизвестным должны соизмеряться с неизвестными величинами. Например, если XIJ выражены в тоннах, то при решении задачи на минимизацию транспортных издержек Cij должны выражаться в тенге за перевозку одной тонны.
Модель транспортной задачи можно записать в структурном виде.
Найти минимум функции
Следовательно, математические модели транспортных задач имеют также три составные части: цель задачи, ограничения и условие неотрицательности.
2. Методы решения транспортных задач. Для транспортной задачи разработано множество алгоритмов решения наиболее применяемыми из них являются распределительный метод, модифицированный распределительный метод (МОДИ), метод потенциалов, метод дифференциальных рент, дельта-метод и др. Отличаются они по программе вычислений и показателям оценки плана.
Разберем алгоритм решения на примере простой задачи.
В хозяйстве имеются 3 склада, где хранится 600 т минеральных удобрений, в том числе на первом складе - 200 т, на втором—150т, на третьем-250 т. На 4 полях, удаленных на различные расстояния от этих складов, ведется посев пшеницы с одновременным внесением минеральных удобрений. Потребность в минеральных удобрениях для первого поля составила 100 т, для второго 150 т, для третьего— 150 т и для четвертого - 75 т. Общая потребность в минеральных удобрениях составила 475 т, т. е. на 125 т меньше, чем имеется их в наличии. Следовательно, это открытая модель транспортной задачи.
Транспортные издержки перевозки удобрений со складов на поля приведены в табл2.
Решение сводится к нахождению неотрицательных значений неизвестных хij, выражающих объемы перевозок, которые бы минимизировали общую сумму транспортных затрат.
Таблица 7.1 - Транспортные издержки, тенге за 1 тонну (для учебных целей)
| Склад | Поле | |||
Составим развернутую математическую модель данной задачи. Модель задачи открытая. Чтобы привести ее к закрытому виду, вводим фиктивное поле с номер 5 с потребностью в минеральных удобрениях: 600—475=125 т. Себестоимость перевозок для фиктивного поля принимается равной нулю.
В результате получена следующая задача линейного программирования.
Найти минимум функции:
Zmin=4x11+2x12+3x13+x14+0x15+3x21+6x22+2x23+5x24+0x25+
+6x31+3x32+4x33+2x34+0x35
при условиях:
а) ограничения по запасам:
x11+ x12+ x13+ x14+ x15=200
x21+ x22+ x3+ x24+ x25=150
x31+ x32+ x33+ x34+ x35=250
б) ограничения по потребностям:
x11+ x21+ x31=100
x12+ x22+ x32=150
x13+ x23+ x33=150
x14+ x24+ x34=75
x15+ x25+ x35=125
в) условие неотрицательности:
x11, x11,…, x35>0.
3. Методы построения опорного плана. Расчет плана с нарушенным балансом. Задача оперативного планирования перевозок. Первый опорный план для решения транспортной задачи можно составить несколькими способами. Наиболее распространенным для машинного счета является диагональный метод, или метод северо-западного угла (таблица 7.2).
Особенность этого метода заключается в том, что распределение начинается с левой верхней, т. е. северо-западной, клетки (1-1) независимо от величины удельных издержек по маршрутам. В этой задаче в первую клетку записывают 100 т. Это тот объем минеральных удобрений, который требуется для пшеницы первого поля.
Таблица 7.2 – 1-ый опорный план
На первом складе после этого осталось, еще 100 т, которые планируется вывезти на второе поля (записывают в клетку 1-2). Запасы первого склада использованы полностью и в то же время потребность второго поля не удовлетворена. Поэтому недостающие 50 т можно перевезти со второго склада (записывают в клетку 2-2). Теперь потребности второго поля удовлетворены полностью, но на втором складе осталось в наличии еще 100 т удобрений, которые передаются третьему полю и записываются в клетку (2—3). Запасы второго склада исчерпаны, а третьему полю требуется еще 50 т удобрений, которые планируется доставить с третьего склада. За счет запасов этого же склада удовлетворяются потребности четвертого поля в количестве 75 т, после чего там остается в избытке еще 125 т, которые и записываются в фиктивное поле в клетку (3—5).
Таким образом, все запасы распределены и все потребности удовлетворены. Получен первый допустимый план при следующих значениях неизвестных:
x11=100, x12=100, x22=50, x23=100, x33=50, x34=75, x35=125. Значения остальных неизвестных равны нулю. Значение целевой функции при этом равно:
Z1 =4*100+2*100+6*50+2*100+4*50+2*75+0*125=1450 тенге
Для проверки правильности распределения ресурсов и удовлетворения потребностей необходимо суммировать объем перевозок как по строкам, так и по столбцам. После этого план проверяется на оптимальность. Для этого необходимо количество клеток иметь равным m+n-1. В случае, когда их оказывается меньше, план является вырожденным.
Для преодоления вырожденности одну из свободных клеток условно считают занятой и проставляют в ней перевозки xij=0. При этом надо следить за тем, чтобы условно занятая клетка не образовывала с другими занятыми клетками замкнутых контуров.
В данной задаче число занятых клеток равно: 3+5-1=7.
Для определения оптимального плана транспортной задачи целесообразно использовать модифицированный распределительный метод (МОДИ) или метод потенциалов, которые почти не отличаются друг от друга. Для решения задач этими методами рассчитывают потенциалы клеток Ui и Vj, которые для занятых клеток определяются по формуле Vj+Ui=cij и записываются в специальные столбец и строку таблицы (табл.7.3).
Таблица 7.3 – 2-й опорный план
Задав одной из неизвестных Ui или VJ произвольное значение (например, Ui=0), находим все Ui и Vj. Так, U1+V1=c11, откуда V1=C1-U1=4—0=4 и т. д.
После определения потенциалов план исследуется на оптимальность.
Для этого по свободным клеткам рассчитывают величину lij = cij -(Vj+Ui), которая указывает экономию или перерасход по сравнению с предыдущим планом при перемещении единицы груза в данную клетку. Если все величины lij будут положительными или равными нулю, то план оптимален, если же имеются и отрицательные величины, то план не оптимален и его надо улучшать.
Рассчитаем lij для нашей задачи:
121=с21-(V1+U2)=3-(4+4)=-5;
131=с31-(V1+U3)=6-(4+6)=-4;
132=с32-(V2+U3)=3-(2+6) =-5;
113=с13-(V3+U1)=3-(-2+0)=5;