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

1. Между делениями дробления отсутствует рост клеток.

2. 2n2c.

3. Зависит от количества и характера распределения желтка в цитоплазме.

4. Полное и неполное. Равномерное и неравномерное, поверхностное и дискоидальное, синхронное и асинхронное.

5. Полное неравномерное асинхронное. Тип бластулы – бластоциста.

Основная литература

1. Биология. /Под ред. В.Н. Ярыгина.- М.: Высшая школа, т.1, 2000, 2010.

2. Руководство к лабораторным занятиям по биологии /Чебышев Н.В., Богоявленский Ю.Д., Демченко А.Н.. -М.: Медицина, 1996, 2008.

3. Пехов А.П. Биология. Медицинская биология, генетика и паразитология ГЭОТАР-Медиа, 2010.

4. Уэбстер П. «Клетка», М – Мир, 1980.

5. Никитин С.А. и соавт. Руководство по подготовке к сдаче итоговой аттестации по предмету «Биология» для студентов первого курса. – Учебное пособие. ВолГМУ, 2007.

Дополнительная литература

1. Данилов Р.К., Боровая Р.К.Общая и медицинская эмбриология.– Санкт-Петербург, 2003.

2. Маркина В.В. и соавт. Биология: Руководство в 4-х частях.- М., 2001.

3. Тейлор Д., Грин Н., Стаут У. Биология: В 3-х т. Пер. с англ. / Под ред. Р. Сопера – 3-е

изд. – М.: Мир, 2008.

4. Фаллер М. Молекулярная биология клетки. Бином-пресс, 2004.

5. Фуралев В.А. Цитология, Москва, 2001.

6. Чебышев Н.В. Биологический тематический словарь.- М.: Academia, 2006.

 

 

З а д а н и е № 6

МАРШРУТИЗАЦИЯ перевозок

Мелкопартионных грузов

 

Цель работы

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

 

Методика выполнения работы

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

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

 

Рисунок 6.1 – Улично-дорожная сеть региона

В примере улично-дорожной сети, приведенном на рисунке 6.1, есть один пункт погрузки (Б1) и пять магазинов – пунктов выгрузки (М2…М6). Кроме того, на улицу Рогачевскую от перекрестка с улицей Песина, до перекрестка с улицей Советская запрещен въезд транспортных средств.

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

, (6.1)

где l _{o j} – длина оборота транспортного средства на j -м маршруте, км;

n – общее число маршрутов для освоения заданных объемов перевозок ресурсов.

Для решения такой задачи, прежде всего, необходимо создать транспортную сеть – совокупность узлов (пунктов погрузки и выгрузки, а также перекрестков) и соединяющих их дуг (улиц). Транспортная сеть для улично-дорожной сети, представленной на рисунке 6.1, приведена на рисунке 6.2.

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

1) Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал v_i = 0.

2) Находятся все звенья, для которых начальным пунктам i присвоен потенциал v_i, а конечным пунктам j не присвоен. Если таких звеньев нет, то решение закончено (на п.5), а иначе на п.3.

3) Для найденных звеньев по п.2 рассчитываются значения потенциалов конечных пунктов j по следующей формуле:

u_j(i) = v_i + l_ij, (6.2)

где u_j(i) – потенциал конечного пункта j -го звена i - j;

l_ij – длина звена i -j.

Из всех полученных потенциалов выбирается потенциал с наименьшим значением, т.е. определяется:

, (6.3)

где { u_j(i) } – множество значений потенциалов конечных пунктов j звеньев i - j, i -м начальным пунктам которых ранее присвоены потенциалы;

u_r(s) – потенциал конечного пункта r звена s - r, являющийся наименьшим по значению элементом множества { u_j(i) }.

Потенциал u_r(s) присваивается соответствующему конечному пункту (v_s = u_r(s)), а звено r - s отмечается стрелкой.

В случае если несколько значений потенциалов множества { v_j(i) } окажутся равными и наименьшими, то необходимо установить, относятся они к одному и тому же пункту или нет. Когда наименьшие равные значения потенциалов относятся к различным пунктам (у потенциалов не совпадают цифровые индексы без скобок), эти значения потенциалов присваиваются всем соответствующим конечным пунктам и стрелками отмечаются соответствующие звенья. Если наименьшие равные значения потенциалов относятся к одному и тому же конечному пункту s (у потенциалов совпадают цифровые индексы без скобок), то пункту s присваивается это наименьшее значение потенциала и отмечается стрелкой то звено r-s, которому соответствует потенциал u_r(s) с большим удельным весом в его составе длин звеньев с лучшими условиями перемещения (при одинаковых дорожных условиях кратчайшее расстояние реализуется по любому из звеньев r-s). Следует отметить, что множество выделенных звеньев (r-s) будут составлять матрицу путей следования – таблицу, в которой указаны пути следования между всеми парами узлов.

4) переход на п. 2

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

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

 

Таблица 6.1 – Матрица кратчайших расстояний

Рисунок 6.2 – Транспортная сеть

 

Разработанные транспортная сеть и матрица кратчайших расстояний являются исходными данными для решения задачи коммивояжера. Суть этой задачи заключается в том, что имеется n пунктов (пункты погрузки и выгрузки), в которых должен побывать коммивояжер. Задана матрица стоимостей (матрица кратчайших расстояний) на переход между пунктами c_ij, i =1, 2,..., n и j =1, 2,..., n. Коммивояжер должен выйти из одного из пунктов (пункта погрузки), побывать во всех остальных пунктах по одному разу (пунктах выгрузки) и вернуться в начальный пункт.

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

Введем переменную K_jj

. (6.4)

Необходимо найти множество { K_ij }, i =1, 2,..., n и j =1, 2,..., n, дающее минимум

(6.5)

и выполнение ограничений

, j =1, n. (6.6)

, i =1, n. (6.7)

U_i – U_j + nK _ij £ n –1, i ¹ j, (6.8)

 

где U_i, U_j – целые неотрицательные числа, представляющие собой номер этапа, на котором посещается пункт.

 

Условие (6.6) означает, что коммивояжер выходит из каждого пункта один раз, а условие (6.7) – что он входит в каждый пункт только один раз. Условие (6.8) обеспечивает замкнутость цикла (контура) на n -м этапе решения задачи.

Точное решение задачи коммивояжера дает метод ветвей и границ. Существуют различные версии метода ветвей и границ решения задачи коммивояжера. Рассмотрим стандартный метод Дж. Литла и др.

Вначале для множества R всех гамильтоновых контуров определяется некоторая оценка снизу (нижняя граница) их длины. Затем множество всех гамильтоновых контуров разбивается на два подмножества. Первое подмножество состоит из гамильтоновых контуров, которые включают некоторую дугу (i, j), – обозначим его {(i, j)}, а второе состоит из гамильтоновых контуров, которые не включают эту дугу, – обозначим его { }. Для каждого из подмножеств {(i, j)} и { } определяется нижняя граница длины гамильтоновых контуров и . Каждая новая нижняя граница оказывается не меньше нижней границы всего множества гамильтоновых контуров . Среди двух подмножеств маршрутов {(i, j)} и { }выбирается подмножество с меньшей нижней границей. Это подмножество снова разбивается на два и для вновь образованных подмножеств находятся нижние границы. Процесс разбиения подмножеств аналогичным образом продолжается до тех пор, пока не будет выделено подмножество, содержащее единственный гамильтонов контур. Взаимосвязь подмножеств, полученных в результате разбиения, изображается в виде дерева (графа), вершинам, которого приписываются нижние границы.

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

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

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

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

Таким образом, для определения нижней границы множества всех гамильтоновых контуров необходимо в каждой строке матрицы А найти минимальный элемент , = (i = ), и вычесть его из всех элементов данной строки (такая операция называется приведением матрицы расстояний по строкам). В результате приведения в каждой строке матрицы будет, по крайней мере, один нуль. Затем в матрице, приведенной по строкам, находим минимальный элемент в каждом столбце и приводим ее по столбцам. Матрицу, приведенную по строкам и столбцам, называют полностью приведенной, а величины и (i, j = ) – константами приведения. Полностью приведенная матрица содержит, по крайней мере, один нуль в каждой строке и каждом столбце.

Так как длина L₁ оптимального гамильтонова контура в задаче с полностью приведенной матрицей отличается от длины L оптимального гамильтонова контура в задаче с неприведенной матрицей, на сумму констант приведения:

. (6.9)

то .

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

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

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

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

Наиболее вероятно, что в оптимальный гамильтонов контур войдут дуги, которым в приведенной матрице соответствуют нулевые элементы. Поэтому выбор дуги будем осуществлять следующим образом. В приведенной матрице элемент а_ji =0 условно заменим на . Этим самым дуга (i, j) будет исключена из гамильтонова контура. Чтобы определить сумму констант приведения вновь полученной матрицы, необходимо сложить минимальный элемент i -й строки с минимальным элементом j -го столбца, так как остальные строки и столбцы содержат, по крайней мере, по одному нулю. Обозначим сумму констант приведения матрицы с исключенной дугой (i, j) через . Следовательно, . Аналогичный расчет произведем для всех остальных нулевых элементов матрицы, условно заменяя их на . В первую очередь будем исключать из гамильтонова контура ту дугу, для которой сумма констант приведения является наибольшей, так как в этом случае произойдет наиболее резкое изменение оценки.

Предположим, что для дуги (r, s)сумма констант приведения максимальна, т.е. . Тогда, исключив дугу (r, s) из гамильтонова контура, получим подмножество контуров { } и, включив эту дугу в гамильтонов контур, получим подмножество контуров {(r, s)}.

Нижняя граница подмножества контуров { }

 

.

 

Нижняя граница подмножества контуров {(r, s)}

 

,

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

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

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

1. Приводим матрицу расстояний по строкам и столбцам. Находим нижнюю границу всего множества маршрутов:

.

2. Каждый нуль в приведенной матрице условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями.

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

4. Приводим полученную матрицу расстояний и определяем нижнюю границу подмножества гамильтоновых контуров { }.

5. Априорно включаем дугу (i, j) в гамильтонов контур, что ведет к исключению в матрице, полученной после выполнения п.2, i -й строки и j -го столбца. Заменяем один из элементов матрицы на (в простейшем случае симметричный), чтобы не допустить образования негамильтонова контура.

6. Приводим сокращенную матрицу и находим нижнюю границу подмножества маршрутов { }.

7. Проверяем размерность сокращенной матрицы. Если сокращенная матрица размерности 2х2, то переходим к выполнению п. 9; если же размерность матрицы больше, чем 2х2, то – к п.8.

8. Сравниваем нижние границы подмножеств гамильтоновых контуров и и переходим к выполнению п.2. При этом, если < , то разбиению подлежит подмножество { }(дальнейшему анализу, подвергается матрица, полученная в результате последнего выполнения п.4). Если же < , разбиению подлежит подмножество { } (дальнейшему анализу подвергается матрица, полученная после последнего выполнения п.6).

9. Определяем гамильтонов контур и его длину.

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

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

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