Все вопросы к тесту (html) Моделирование систем

В таблицу 1 листа <Опорный план> введем исходные данные.

В таблице 2 получим смоделированный опорный план транспортной задачи.

В ячейке G17 получены затраты на всю грузоперевозку по данному опорному плану-12700 ед.

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

Введем в ячейки таблицы 2 формулы, указанные в таблице 3.

Таблица 3

Формулы для ввода в ячейки при построении модели расчета опорного плана перевозок

Формулы 17-й строки таблицы 2 ячеек (В17:F17) и столбца «Н» ячеек (Н11:Н16) проверяют выполнение условий 1 и 2. Если результаты вычислений в этих ячейках будут равны «0», то, значит, каждый пункт назначения получил груз согласно своей заявке и составленный план перевозок удовлетворяет балансовым условиям. Полученное решение является не только допустимым, но и опорным решением транспортной задачи.

При построении плана перевозок не учитывались стоимости перевозок, поэтому план может оказаться не оптимальным.

Определим сумму затрат на все перевозки. Для определения суммы затрат на все перевозки дополним таблицу 2 ещё одной строкой (ячейки B18:G18) и введем формулы:

После ввода формул в ячейке G19 получим сумму затрат на все грузоперевозки по найденному плану.

Таким образом, построена модель нахождения опорного плана методом «северо-западного угла» для транспортной задачи с правильным балансом размерностью 5х5. Вводя в таблицу 1 новые исходные данные, в таблице 2 мы получим опорный план перевозок.

Для построения модели определения опорного плана перевозок транспортной задачи с помощью табличного процессора OpenOffice.org Calk переименуем Лист1 на <Опорный план> и на этом листе, начиная с ячейки А1, заполним таблицу 1 (диапазон ячеек А1:G7) и таблицу 2, (диапазон А10:H16). Для простоты изложения положим m = 5 и n=5.

Таблица 1.

Рисунок 4 . Транспортная таблица на листе 1

Таблица 2

Рисунок 5. Таблица для моделирования опорного плана методом «северо-западного угла» на листе1

Для построения модели улучшения плана перевозок методом потенциалов поступим следующим образом.

Создадим копию листа 1 и переименуем: «Метод потенциалов». На этом листе таблицу 2 дополним ещё одной строкой («Платежи βj ») и одним столбцом («Платежи αi»):

Таблица 2

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

Один из платежей выбираем равным нулю, например, платежи пункта С1: α1=0, исходя из того, что клетка (1,1) базисная, имеем равенство: 0+ β1+ 4=0 , находим β1=-4. Зная платежи пункта П1 и учитывая, что клетка (2,1) базисная находим платежи пункта С2: α2+ β1+с2,1 =0, т.е. α2+(-4)+2=0, отсюда α2=2. Учитывая условие базисности клетки (2,2) и определенное на предыдущем шаге значение α2=2, запишем условие для определения платежа потребителя П2: 2+β1+6=0, отсюда β1=-8. Платеж потребителя П3 можно определить из условия базисности клетки (2,3) и платежа пункта С2: α2=2. Таким образом, 2+ β3+1=0, т.е., β3=-3. Рассуждая подобным образом, анализируя все занятые клетки, можно заполнить строку и столбец платежей таблицы 2.

Построим таблицу 3 для анализа распределения перевозок на диапазоне ячеек (K10:P15) как показано на рисунке 7.

Таблица 3

Рисунок 7. Таблица анализа распределения перевозок

В ячейку К9 введем название таблицы «Анализ распределения перевозок». Объединим диапазон (К9:Р9). Оформим диапазоны ячеек (L10:P10) и (К11:К15) как показано на таблице 3. Введем в диапазон ячеек (L11:P15) формулы. Формулы будем вводить следующим образом. В ячейки (L11: P11) введем формулы:

L11: =$I11+B$18+B2; M11: =$I11+C$18+C2; N11: =$I11+D$18+D2; O11: =$I11+E$18+E2; P11: =$I11+F$18+F2.

Мы ввели формулы в первую строку указанного диапазона. Выделим диапазон (L11:P11) и, используя маркер автозаполнения «+» ( нижняя правая вершина выделенного диапазона), заполним формулами весь диапазон ячеек (L12:P15).

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

Таблица В

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

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

Если в таблице 3 все значения окажутся положительными, то это значит, что полученный опорный план является оптимальным. В ячейке G19 получим стоимость всей перевозки.

Задана транспортная таблица.

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

Смоделировать оптимальный план, если известна транспортная таблица

Данная задача является задачей ___ типа.

Выберите из ниже приведенного списка пропущенное название типа.

a) Закрытого.

b) Открытого.

c) Вырожденного.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Для перехода к задаче с правильным балансом надо

a) уменьшить запасы.

b) ввести фиктивный пункт отправления - Сф.

c) ввести фиктивный пункт назначения - Пф.

d) увеличить запасы.

Затраты на все перевозки по опорному плану равны

a) 8750 ед.

b) 3790 ед.

c) 9520 ед.

d) 2300 ед.

e) 7890 ед.

Вводить только числа, без ед.

Затраты на все перевозки по оптимальному плану равны

a) 8750 ед.

b) 4350 ед.

c) 6020 ед.

d) 2680ед.

e) 7890 ед.

Вводить только числа, без ед.

Все условия задачи отобразим в таблице (рисунок 1):

- пункты отправления и назначения,

- запасы, имеющиеся в пунктах отправления,

- заявки, поданные пунктами назначения,

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

Таблица 1

Рисунок 1. Транспортная таблица

В этой таблице пункты назначения обозначены - A1,…, Aj, …,An, a B1, …, Bi,…,Bm – это пункты отправления, т.е. m пунктов отправления и n пунктов назначения.

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

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного плана. Проведем нахождение опорного плана методом «северо-западного угла».

Для чего создадим таблицу, показанную на рисунке 2.

Рисунок 2. Таблица для определения опорного плана перевозок

Шаг 1. Если b1 < a1 , то из В1 вывозится полностью весь груз в А1, а недостающие (a1 - b1 ) единиц груза попытаемся довезти из следующего пункта отправки, т.е. В2. Если (a1 - b1 ) больше, чем имеющийся груз в В2, то переходим к Шагу 1( но уже рассматриваем пункт отправки В2 вместо В1) и т.д. После того как заявка А1 будет удовлетворена полностью, переходят к удовлетворению заявки следующего пункта назначения, т.е. А2. Причем эту заявку начинают удовлетворять грузом из первого по порядку пункта отправления с ненулевым грузом. Если (a1 - b1 ) < b2 , то переходим к шагу 2

Шаг 2. Если b1 > a1 , то из В1 вывозится a1 единиц груза в А1, и в В1 останется (b1 -a1) единиц груза. После этого заявка А1 будет удовлетворена полностью, а в В1 останется (b1 - a1) единиц груза. Этим остаточным грузом необходимо удовлетворить следующую заявку, т.е. заявку А2. Если этот остаточный груз в В1 меньше, чем заявка А2, то переходим к шагу 1, иначе переходим к шагу 2.

Шаг 3. Если b1 = a1, то груз из В1 полностью перевозится в пункт А1, удовлетворяя заявку А1. Затем начинают удовлетворять заявку А2 из пункта отправления В2 и выполняют либо шаг 1, либо шаг 2.

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

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

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок.

2. Сумма поданных заявок превышает наличные запасы.

В данных случаях введение соответственно фиктивного пункта назначения или фиктивного пункта отправления приводит к задаче с правильным балансом:

Фиктивному пункту назначения приписывают фиктивную заявку, равную избытку запасов над заявками, и стоимости перевозок из всех пунктов отправления в фиктивный пункт назначения приравнивают нулю. Таким образом, отправление какого-то количества груза xiф из пункта Аi в пункт Вф попросту будет означать, что в пункте Аi остались неотправленными xiф единиц груза. С введением фиктивного пункта назначения Вф с его заявкой bф сравнивается баланс задачи и теперь её можно моделировать как обычную транспортную задачу с правильным балансом.

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

Для наглядности рассмотрим этот метод на конкретном примере. Пусть мы имеем транспортную таблицу, для которой уже найден опорный план методом «северо-западного угла».

Транспортная таблица

Опорный план перевозок

При определении опорного плана методом «северо-западного угла» мы не брали во внимание стоимости перевозок.

Суммарные затраты на все перевозки по опорному плану составят: 4*680+2*20+6*580+1*200+2*350+6*50+4*250 +7*150+8*340=12210 (у.е.)

Заметим, что стоимость перевозки в клетке (1,2), т.е. из пункта отправления С1 в пункт назначения П2 обходится дешевле, чем перевозка в П2 из С2. Попробуем улучшить этот план, например, перенеся 580 единиц из клетки (2,2) в клетку (1,2) и, чтобы не нарушить баланса, перенесем те же 580 единиц из клетки (1,1) в клетку (2,1).

Получим новый план, показанный на рисунке 6.

Таблица 2-1

Рисунок 6. Примеры циклов пересчета

Не трудно убедиться, что стоимость нового плана равна: 4*100+2*600+3*580+1*200+2*350+6*50+4*250+7*150+8*340=9310 (у.е.), т.е. стоимость плана перевозок уменьшилась на 2900 единиц.

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

Введем понятия. Циклом в транспортной таблице назовем несколько клеток, соединенных замкнутой линией, которая в каждой клетке совершает поворот на 900.

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

Ценой цикла называется увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в положительных вершинах берутся со знаком «+», а в отрицательных вершинах – со знаком «-». Поэтому цена первого означенного цикла равна: -4+2-6+3=-5. Очевидно, что для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Так как перевозки неотрицательны, необходимо пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки.

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

- для свободной клетки с меньшими стоимостями необходимо определить цикл пересчета, т.е., «означить» цикл;

- определить цену цикла;

- если цена цикла отрицательна, то принимается решение перемещать перевозки по этому циклу;

- определить количество перемещаемого груза. Величина перемещаемого груза равна минимальной перевозке в отрицательных клетках.

- определить величину уменьшения стоимости всех перевозок путем умножения цены цикла на количество перемещенного груза;

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

Классическая транспортная задача линейного программирования формулируется следующим образом.

Имеется m пунктов отправления: А1, А2, …, Аm, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно а1, а2, …, аm (столбец «Запасы») единиц. Кроме того, имеется n пунктов назначения: B1, B2, …, Bn, подавших заявки соответственно на b1, b2, …, bn (строка «Заявки») единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов.

Известна стоимость cij перевозки единицы товара от каждого пункта отправления Ai до каждого пункта назначения Bj

Требуется составить такой план перевозок, при котором все заявки были бы выполнены, и при этом общая стоимость всех перевозок была бы минимальной.

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

Обозначим xij - количества единиц груза, направляемых из пункта Аi в пункт Bj и назовем перевозками. Все неотрицательные переменные x11, x12, …, xmn (число которых, очевидно, равно m x n) должны удовлетворять следующим условиям:

Условие 1. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте.

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

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

Любую совокупность (xij) (i=1,2, …, m; j=1,2, …,n) будем называть планом перевозок, или просто планом. План считается допустимым, если он удовлетворяет условиям 1 и 2. План называется опорным, если в нем отличны от нуля не более r = m+n-1 отличных от нуля перевозок xij. Отличные от нуля перевозки будем называть базисными, а остальные перевозки равны нулю. План называется оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

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

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

Назовем «псевдостоимостью суммарную величину выплат при перевозке единицы груза из Аi в Вj. При чем платежи αi и βj не обязательно должны быть положительными: не исключено, что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку. Можно доказать, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (αi , βj) одна и та же и от плана к плану не меняется.

Определим платежи так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям: αi + βj = сij при хij>0;

Что касается свободных клеток, то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

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

Алгоритм решения транспортной задачи методом потенциалов:

Взять любой опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки – свободные).

Определить для этого плана платежи (αi , βj), исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям: αi + βj = сij Один из платежей можно назначить произвольно, например, положить равным нулю.

Определить псевдостоимости: сij = αi + βj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

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

План

1.Теоретическая часть

-Транспортная задача линейного программирования. Основные понятия

-Транспортная задача с неправильным балансом

-Алгоритм определения опорного плана транспортной задачи методом «северо-западного угла»

-Алгоритм нахождения оптимального плана методом наименьших затрат

-Алгоритм нахождения оптимального плана методом потенциалов

2.Моделирование решений транспортной задачи

-Моделирование опорного плана транспортной задачи методом «северо-западного угла»

-Моделирование оптимального плана транспортной задачи методом потенциалов

3.Контрольный пример

Цель: изучить на практическом примере процесс моделирования транспортной задачи линейного программирования.

Результат обучения:

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

Список рекомендуемой литературы:

• Бережная В., Бережной В.И. Математические методы моделирования экономических систем. 2-е изд., перераб. И доп. – М.: Финансы и статистика, 2006.
• Васильев Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. Изд-во КноРус, 2011.
• Поршнев С.В. Компьютерное моделирование физических процессов с использованием пакета MathCad. –М.:, 2004.
• Советов Б.Я., Яковлев С.А. Моделирование систем. Изд-во Высшая школа, 2009.

Используемые программы:

OpenOffice.org Calс

Табличный процессор OpenOffice.org Calс– программа, предназначенная для ввода и обработки данных.

Смоделировать оптимальный план для заданной транспортной таблицы

Данная задача является задачей ___ типа.

Выберите из ниже приведенного списка пропущенное название типа.

a) Открытого.

b) Закрытого.

c) Вырожденного.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Затраты на все перевозки по опорному плану равны

a) 18750 ед.

b) 17850 ед.

c) 16850 ед.

d) 27880 ед.

e) 27890 ед.

Вводить только числа, без ед.

Опорный план задачи должен содержать не более ___ неотрицательных перевозок

a) 5.

b) 10.

c) 9.

d) 8.

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

a) 3780 ед.

b) 6120 ед.

c) 4510 ед.

d) 5110 ед.

e) 5710 ед.

Вводить только числа, без ед.

Цена цикла пересчета с вершинами (1,4) – (1,1) – (2,1) – (2,3) – (3,3) – (3,4) равна

a) 4 ед.

b) 8 ед.

c) 200 ед.

d) 3 ед.

e) 290 ед.

Вводить только числа, без ед.

Смоделировать оптимальный план для заданной транспортной таблицы

Данная задача является задачей ___ типа.

Выберите из ниже приведенного списка пропущенное название типа.

a. Открытого.

b. Закрытого.

c. Вырожденного.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Для перехода к задаче с правильным балансом надо

a) уменьшить запасы.

b) ввести фиктивный пункт отправления - Сф.

c) ввести фиктивный пункт назначения - Пф.

d) увеличить запасы.

Затраты на все перевозки по опорному плану равны

a) 18750 ед.

b) 17850 ед.

c) 26250 ед.

d) 27880 ед.

e) 27890 ед.

Вводить только числа, без ед.

Опорный план задачи должен содержать не более ___ неотрицательных перевозок

a) 5.

b) 4.

c) 9.

d) 8.

e) 10.

Цена цикла пересчета (4,2) – (2,2) – (2,3) – (3,3) – (3,4) – (4,4), после определения опорного плана методом «северо-западного угла», равна

a) 73 ед.

b) 17 ед.

c) 1700 ед.

d) 11 ед.

e) 5710 ед.

Вводить только числа, без ед.

Смоделировать оптимальный план для заданной транспортной таблицы

Данная задача является задачей ___ типа.

Выберите из ниже приведенного списка пропущенное название типа.

a) Открытого.

b) Закрытого.

c) Вырожденного.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Для перехода к задаче с правильным балансом надо

a) уменьшить запасы.

b) ввести фиктивный пункт отправления - Сф.

c) ввести фиктивный пункт назначения - Пф.

d) увеличить запасы.

Затраты на все перевозки по опорному плану равны

a) 18750 ед.

b) 17850 ед.

c) 26250 ед.

d) 22300 ед.

e) 27890 ед.

Вводить только числа, без ед.

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

a) 18030 ед.

b) 16700 ед.

c) 12460 ед.

d) 15110 ед.

e) 15710 ед.

Вводить только числа, без ед.

Цена цикла пересчета (1,3) – (1,2) – (2,2) – (2,3) после определения опорного плана методом «северо-западного угла» равна

a) 13 ед.

b) 1700 ед.

c) 8 ед.

d) 5110 ед.

e) 5710 ед.

Вводить только числа, без ед.

Смоделировать оптимальный план, если известна транспортная таблица

Данная задача является задачей ___ типа.

Выберите из ниже приведенного списка пропущенное название типа.

a) Открытого.

b) Закрытого.

c) Вырожденного.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Для перехода к задаче с правильным балансом надо

a) уменьшить запасы.

b) ввести фиктивный пункт отправления - Сф.

c) ввести фиктивный пункт назначения - Пф.

d) увеличить запасы.

Затраты на все перевозки по опорному плану равны

a) 8750 ед.

b) 3790 ед.

c) 6250 ед.

d) 2300 ед.

e) 7890 ед.

Вводить только числа, без ед.

Затраты на все перевозки по оптимальному плану равны

a) 8750 ед.

b) 4350 ед.

c) 6250 ед.

d) 2680ед.

e) 7890 ед.

Вводить только числа, без ед.

Выполнить расчет сетевого графика и ответить на вопросы

Позднее начало работы а5 равно

A) 0

B) 69

C) 51

D) 61

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Раннее начало работы а7 равно

A) 0

B) 69

C) 51

D) 61

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Резерв времени работы а5 равен

A) 0

B) 69

C) 51

D) 61

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Выполнить расчет сетевого графика и ответить на вопросы

Позднее начало работы а5 равно

a) 43

b) 53

c) 51

d) 61

e) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Раннее начало работы а5 равно

a) 43

b) 53

c) 51

d) 61

e) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Резерв времени работы а5 равен

A) 53

B) 51

C) 61

D) 8

E) 43

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Выполнить расчет сетевого графика и ответить на вопросы

Позднее начало работы а2 равно

A) 0

B) 12

C) 3

D) 15

E) 11

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Раннее начало работы а2 равно

A) 0

B) 12

C) 3

D) 15

E) 11

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Резерв времени работы а2 равен

A) 0

B) 12

C) 4

D) 3

E) 11

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Выполнить расчет сетевого графика и ответить на вопросы

Позднее начало работы а6 равно

A) 51

B) 75

C) 62

D) 86

E) 11

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Раннее начало работы а6 равно

A) 51

B) 75

C) 62

D) 86

E) 11

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Резерв времени работы а5 равен

A) 12

B) 8

C) 11

D) 61

E) 51

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Выполнить расчет сетевого графика и ответить на вопросы

Позднее окончание работы а8 равно

A) 0

B) 96

C) 89

D) 61

E) 77

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Раннее окончание работы а8 равно

A) 0

B) 77

C) 51

D) 89

E) 96

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Резерв времени работы а2 равен

A) 0

B) 6

C) 51

D) 61

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Для построения модели расчета сетевого графика заданного комплекса работ в OpenOffice.org Calс переименуем лист1 на <Сетевой график> и на этом листе, начиная с ячейки А1, заполним таблицу 1

Таблица 1.

Рисунок 3 . Таблица комплекса работ

Таблица 2

Рисунок 4. Упорядочение таблицы комплекса работ

Таблица 3

Рисунок 5. Упорядоченная таблица комплекса работ

Построим таблицу 4 для расчета параметров сетевого графика работ в диапазоне О2:АС12. Введем моделирующие формулы в ячейки таблицы 4, начиная с ячейки U3. Формулы приведены в таблице 5

Таблица 3

Таблица 4 Расчет сетевого графика работ

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

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

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

- предшествующий путь, соединяющий исходное событие с данным событием;

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

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

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

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

- Ранний срок начала работы tр.н(i,j) – это самый ранний из возможных сроков начала работы, который обуславливается выполнением предшествующих работ.

- Ранний срок окончания работы tр.о(i,j) – это срок окончания работы при условии её начала в самый ранний из возможных сроков. Ранний срок начала работы равен продолжительности максимального пути от исходного события графика до начального события данной работы. Значения ранних начал работ, имеющих общее начальное событие, равны.

- Позднее начало работы tп.н(i,j) – это самый поздний срок, в который может быть начата данная работа без увеличения продолжительности критического пути.

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

Величина раннего начала работы соответствует раннему сроку свершения её начального события tр(i).

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

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

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

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

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

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

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

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

Ранний tp(i) и поздний tп(i) сроки свершения события определяют по максимальному пути, проходящему через событие i, причем tp(i) равно продолжительности максимального L1(i) из предшествующих событию путей L, а tп(i) равно разности между Ткр и продолжительностью максимального из последующих за событием i путей L2(i):

tp(i)=t[L1(i)];

tп(i)=Tкр – t[L2(i)];

Для событий и работ, принадлежащих критическому пути,

tp(i)= tп(i);

tр.н(i,j)= tp(i);

tп.н(i,j)= tп(j )- t(i,j).

Для всех работ критического пути

tр.н(i,j)= tп.н(i,j);

tр.о(i,j)= tп.о(i,j),

Так как для всех событий этого пути

tр(i)= tп(j).

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

tр.н(i,j)= max tр.о(n, i)= tр(i).

Раннее окончание данной работы равно сумме её раннего начала и продолжительности

tр.о(i,j)= tр.н(i,j)+ t(i,j).

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

tр.н(i,j)=0,

а раннее окончание численно равно продолжительности работы

tр.о(i,j)=0+ t(1,j) = t(1,j).

Продолжительность критического пути равна наибольшему из ранних окончаний завершающих работ

Ткр=max th.o(i,z).

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

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

tп..о(i,j)= min tп..н(j,k)= tп(j).

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

tп..н(i,j)= tп..о(i,j)- t(i,j).

Для завершающих работ сетевого графика позднее окончание равно величине продолжительности критического пути

tп..о(i,z)= Ткр= max tп.о(i,z).

Позднее начало завершающей работы равно разности между продолжительностью критического пути и продолжительностью данной работы

tп..н(i,z)= Ткр -t(i,z).

Полный резерв времени работы Rп(i,j) равен

Rп(i,j)=tп(j)-tр(i)-t(i,j).

Свободный резерв времени работы Rc(i,j) равен разности между ранними сроками наступления событий j и i за вычетом продолжительности работы t(i,j).

Rc(i,j)=tp(j)-tр(i)-t(i,j).

Предположим, что известна упорядоченная структурная таблица комплекса работ, в которой проставлены времена выполнения каждой работы t1, t2, … Эти значения времен выполнения отдельных работ предполагаем не случайными, а заранее известными. Получится таблица 4, в которой указаны структурные связи и времена выполнения отдельных работ, выраженные в любых единицах времени. Такая таблица называется структурно-временной.

Таблица 4

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

График ориентируется вдоль оси времени 0t , на которой в каком-то масштабе откладываются времена выполнения работ. Стрелками изображаются работы, но длина каждой стрелки не произвольна, а такова, что её проекция на ось абсцисс 0t равна времени выполнения данной работы. Логические связи между работами по-прежнему обозначаются пунктирными стрелками, не означающими никакой реальной работы (иногда их называют «фиктивными» работами). Начальное событие А0 помещается в начале координат. Из этого узла исходят три стрелки: а1, а2, а3,проекции которых на ось 0t равны времени выполнения соответствующих работ: t1=10, t2=5, t3=15.

Работа а4 опирается на работы а1 и а2 ; из них работа а2 кончается в момент времени t2=5, а работа а1 – в момент t1=10; значит работа а4 может начаться не раньше, чем в момент t1=10, когда окончена работа а1.. Поэтому стрелку работы а4 начнем из узла А1, а узел А2 соединим с А1 пунктирной стрелкой. Проекция а4 равна t4=18, следовательно абсцисса узла А4 , в котором эта стрелка кончается, должна быть Т4= t1+ t4=10+18=28.

Стрелка а5, опирающаяся на а2 и а3 должна начаться в узле А3 , имеющем наибольшую абсциссу из t2=5 и t3=15, а узел А2 соединяем с А3 пунктирной стрелкой. Тогда узел А5 имеет абсциссу Т5= t3+ t5 = 15+19=34.

Стрелка а6 начинается в узле А4 и кончается в узле А6 с абсциссой Т6=Т4+ t6=28+18=46.

Аналогично, стрелка а7, опирающаяся на а5 и а6, начинается от узла А6 и кончается в узле А7 с абсциссой Т7=46+8=54. Стрелка а8 начинается в том же узле А6 и кончается в узле А8 с абсциссой Т8=46+25=71. Так как работа а8 завершается последней, то узел А8=А означает окончание всего комплекса работ; отметим этот узел кружком и соединим с ним пунктирной стрелкой узел А7 – окончание предыдущей работы а7, на которую кроме конца работ ничего не опирается. Время Т= 71 от начального узла А0 до завершающего А=А8 представляет собой минимальное время, за которое может быть завершен комплекс работ. Необходимо отметить, что Т=71 представляет собой сумму времен исполнения не всех работ, а только некоторых из них: Т =t1+ t4+ t6+ t8= 10+18+18+25 = 71.

Работы а1, а4, а6, а8, из длительностей которых составлено время Т, называются критическими работами, а цепочка соответствующих им стрелок на сетевом графике – критическим путем

Рисунок 2. Временной сетевой график

План

1. Теоретическая часть

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

- Упорядочение структурной таблицы

-Сетевой график комплекса работ

• Построение и расчет сетевого графика комплекса работ

- Временной сетевой график комплекса работ

- Алгоритм расчета сетевого графика

• Контрольный пример

Цель: изучить на практическом примере процесс моделирования задачи управления комплексом работ

Результат обучения:

получить навыки расчета сетевого графика

Список рекомендуемой литературы:

• Бережная В., Бережной В.И. Математические методы моделирования экономических систем. 2-е изд., перераб. И доп. – М.: Финансы и статистика, 2006.
• Васильев Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. Изд-во КноРус, 2011.
• Поршнев С.В. Компьютерное моделирование физических процессов с использованием пакета MathCad. –М.:, 2004.
• Советов Б.Я., Яковлев С.А. Моделирование систем. Изд-во Высшая школа, 2009.

Используемые программы:

OpenOffice.org Calс

Табличный процессор OpenOffice.org Calс– программа, предназначенная для ввода и обработки данных.

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

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

- действительная работа – трудовой процесс, требующий затрат времени и ресурсов;

- ожидание – процесс, не требующий затрат труда, но занимающий время;

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

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

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

Названия обычно записываются в «Перечне работ»

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

Можно установить следующие шесть основных правил построения сети:

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

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

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

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

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

- В сети не может быть тупиков, т.е. промежуточных событий, из которых не выходит ни одной работы и в которые не входит ни одна работа.

На рисунке показан сетевой график, где события обозначены А0, А1, А2, …, работы а1, а2, … .

Исходное событие А0 означает «начало работ» или «принятие решения о начале работ». Совместное выполнение работ а1 и а2 изображено дополнительным событием А1,2 в которое ведут пунктирные стрелки, не изображающие никаких работ, а означающие только логическую связь. Из события А1,2 исходит стрелка а4, изображающая работу а4, опирающуюся на работы а1 и а2 и в конце стрелки стоит событие А4, означающий выполнение работы а4.Завершающее событие А означает конец всего комплекса работ.

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

Рассмотрим пример структурной таблицы.

Таблица 1

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

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

Для упорядочения все работы необходимо подразделить на ранги по следующему принципу:

- Работа называется работой первого ранга, если для её начала не требуется выполнения никаких других работ. В нашем примере имеются четыре работы первого ранга: а1, а3, а5, а6.

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

- Работа называется работой k-го ранга, если она опирается на одну или несколько работ не выше (k-1)-го ранга.

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

Таблица 2

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

Таблица 3

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

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

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

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

- времени, необходимого на выполнение всего комплекса работ и его отдельных звеньев;

- стоимости всего комплекса работ и его отдельных звеньев;

- сырьевых, энергетических и людских ресурсов.

Рациональное планирование комплекса работ требует, в частности, ответа на следующие вопросы:

- Как распределить имеющиеся материальные ресурсы между звеньями комплекса?

- В какие моменты начинать и когда заканчивать отдельные звенья?

- Какие могут возникнуть препятствия к своевременному завершению комплекса работ и как их устранять? и т.д.

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

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

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

Таблица 5

Формулы для ввода в ячейки при построении модели расчета параметров сетевого графика работ

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

После ввода формул мы получим рассчитанные параметры сетевого графика работ заданного комплекса.

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

Если Вы находитесь в точке F12, то, чтобы добраться до конечного пункта за минимальное время, необходимо поехать по направлению к точке:

A) Н10

B) F8

C) H8

D) H12

E) F6

За какое минимальное время можно добраться до конечного пункта от точки J10:

A) 43

B) 53

C) 33

D) 61

E) 36

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Минимальное время в пути равно

A) 63

B) 65

C) 95

D) 83

E) 67

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

A) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

B) B16 – D16 – D14 – D12 – F12 – H12 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

C) B16 – D14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

D) B16 – B14 – D14 – F14 – Y14 – H12 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

E) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – N6 – P6 – R6.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Если Вы находитесь в точке L12, то, чтобы добраться до конечного пункта за минимальное время, необходимо поехать по направлению к точке:

A) L10

B) F8

C) H8

D) N12

E) N10

За какое минимальное время можно добраться до конечного пункта от точки H12:

A) 43

B) 53

C) 33

D) 61

E) 48

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Минимальное время в пути равно

A) 63

B) 65

C) 95

D) 83

E) 115

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

A) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

B) B16 – D16 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

C) B16 – D14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

D) B16 – B14 – D14 – F14 – F12 – F10 – H10 – J10 – J8 – L8 – L6 – N6 – P6 – R6.

E) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – N6 – P6 – R6.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Если Вы находитесь в точке H10, то, чтобы добраться до конечного пункта за минимальное время, необходимо поехать по направлению к точке:

A) Н10

B) J108

C) H8

D) H6

E) F6

За какое минимальное время можно добраться до конечного пункта от точки J12:

A) 43

B) 53

C) 41

D) 61

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Минимальное время в пути равно

A) 63

B) 65

C) 68

D) 83

E) 115

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

A) B16 – B14 – D14 – F14 – F12 – F10– H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

B) B16 – D16 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

C) B16 – D14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

D) B16 – B14 – D14 – F14 – Y14 – H12 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

E) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – N6 – P6 – R6.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Если Вы находитесь в точке F10, то, чтобы добраться до конечного пункта за минимальное время, необходимо поехать по направлению к точке:

A - Н10

B - F8

C - H8

D - H6

E - F6

За какое минимальное время можно добраться до конечного пункта от точки J12:

A - 43

B - 53

C - 33

D - 61

E - 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Минимальное время в пути равно

A - 63

B - 65

C - 95

D - 83

E - 115

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

A) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

B) B16 – D16 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

C) B16 – D14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

D) B16 – B14 – D14 – F14 – Y14 – H12 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

E) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – N6 – P6 – R6.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Если Вы находитесь в точке D12, то, чтобы добраться до конечного пункта за минимальное время, необходимо поехать по направлению к точке:

A) D10

B) D8

C) F8

D) F12

E) F10

За какое минимальное время можно добраться до конечного пункта от точки N12:

A) 43

B) 53

C) 33

D) 27

E) 8

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

Минимальное время в пути равно

A) 63

B) 65

C) 94

D) 83

E) 115

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

A) B16 – B14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

B) B16 – D16 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

C) B16 – D14 – D14 – F14 – Y14 – H12 – J12 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

D) B16 – B14 – D14 – F14 – Y14 – H12 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

E) B16 – B14 – B12 – D12 – F12 – F10 – H10 – J10 – J8 – L8 – N8 – P8 – P6 – R6.

Введите заглавную букву в латинской раскладке, соответствующую правильному ответу.

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

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

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

Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

- Задача оптимизации интерпретируется как n-шаговый процесс управления.

- Целевая функция равна сумме целевых функций каждого шага.

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

- Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk (отсутствие последействия).

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

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

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

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

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

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

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

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

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

Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется результат, зависящий от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

Общее условие применимости метода Р. Бэллмана выражается в требовании отсутствия влияния «предыстории». Установить возможность применения метода Р. Бэллмана – значить доказать отсутствие «предыстории».

Задача об инвестициях. Пусть имеется n инвестиционных проектов П1, П2, …,Пn и капитал К, который можно вложить в эти проекты. Для каждого проекта ожидаемый доход Di (i=1,2, …,n) зависит от вложения в него капитала хi. Предположим, что все функции дохода заданы. Требуется найти такое распределение капитала по проектам, при котором суммарный доход максимален.

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

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

2. Начальное состояние (нулевой этап) задается числом нуль.

3. На первом этапе система может быть переведена в одно из состояний, которые определяются числом дискретов, содержащихся в К. На этом этапе решается судьба проекта П1, в который может быть вложено 0, 1, 2, …, m единиц капитала. Это и будут состояния, в которые может быть переведена система после первого этапа. Каждому из них соответствует значение целевой функции, то есть доход, полученный от первого проекта D1(х1). Состояние m означает, что весь капитал вложен в первый проект. Состояние 0 после первого этапа означает, что в первый проект капитал не вкладывается и из этого состояния можно перейти в любое из 0, 1, 2, …, m состояний следующего этапа. Состояние p<m после первого этапа означает, что осталось m-p единиц капитала и, следовательно, из него можно перейти в любое из p, p+1, …,m состояние на следующий этап. Начиная со второго этапа, в каждое из состояний можно попасть разными путями и возможности дальнейшего распределения не зависят от того, как система попала в данное состояние. Поэтому можно сравнивать варианты и в каждом из промежуточных состояний оставлять только один.

Задача о наборе высоты и скорости летательным аппаратом

Пусть самолет(или другой летательный аппарат), находящийся на высоте Н0 и имеющий скорость V0 должен быть поднят на заданную высоту Hω, а скорость его доведена до заданного значения Vω. Известен расход горючего, потребный для подъема аппарата с любой высоты Н на любую другую Н’>H при неизменной скорости V; известен также расход горючего, потребный для увеличения скорости от любого значения V до V’>V при неизменной высоте H.

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

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

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

Задача об оптимальном планировании поставок

Рассмотрим задачу планирования поставок (закупок) какого-либо оборудования для развития производства в течение ряда лет. Период планирования и его этапы заданы.Принципиального значения не имеют количество этапов и их длительность. Для определенности можно принять, что период составляет Т лет. Не имеет принципиального значения и вид поставок. Обозначим как rt его минимально необходимое количество в начале каждого года t(t=1,2,… , Т) . Реальное количество оборудования в начале года t обозначим it it rt). В начальный момент времени имеющееся количество оборудования известно i1=A≥ rt. Количество поставляемого оборудования в год t обозначим хt≥0. Затраты на приобретение оборудования сt(xt) зависят от его количества, причем в различные годы эти зависимости (или их параметры) могут быть разными. Количество оборудования на начало t+1-го года it+1=it+xt≥rt+1. Будем считать, что поставки относятся к концу года. Затраты на эксплуатацию (хранение) оборудования также зависят от его количества, и в различные годы эти зависимости (или их параметры) могут быть разными, так что в году t, эти затраты есть функция mt(it). Требуется разработать такой план поставок, то есть последовательность xt≥0 (t=1, 2, …,Т-1), при котором суммарные затраты на поставки и эксплуатацию (хранение за все годы минимальны.

Планирование выработки электроэнергии.

Известны прогнозные значения потребления электроэнергии на ближайшие Т лет , а именно rt – прогнозируемая мощность потребления электроэнергии в год t. Каждый год необходимо принимать решение, на сколько нужно увеличить (или уменьшить) мощность выработки электроэнергии. Пусть с(х) стоимость увеличения мощности на х кВт·ч в году t. Так как мощность может сокращаться, х может быть отрицательной величиной. В течении года 10% ранее выработанной, но использованной электрической мощности теряется(в первый год потери не происходят). Себестоимость выработки i единиц электрической мощности в год составляет mt(i). В начале первого года уровень вырабатываемой электрической мощности составляет 100000 кВт·ч. Необходимо найти решение, удовлетворяющее потребностям в электроэнергии на ближайшие Т лет с минимальными затратами.

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

1. Выбрать способ описания процесса, т.е. параметры, характеризующие состояние системы, фазовое пространство и способ членения операции на «шаги».

2. Записать выигрыш на i-ом шаге в зависимости от состояния системы S в начале этого шага и управления Ui:

ωi = ωi(S,Ui).

3. Записать для i-го шага функцию, выражающую изменение состояния системы от S к S’ под влиянием управления Ui:

S’=φi(S,Ui).

4. Записать основное функциональное уравнение, выражающее функцию выигрыша Wi(S) на i-ом шаге через функцию выигрыша на (i+1)-ом шаге Wi+1(S):

Wi(S) = max { ωi(S,Ui) + Wi+1(φi(S,Ui))}.

Ui

5. Найти функцию Wm(S) (условный оптимальный выигрыш) для последнего шага:

Wm(S) = max { ωm(S,Um) }.

Um

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

6. Зная Wm(S) и пользуясь уравнением пункта 4 при конкретном виде функций ωi(S,Ui), φi(S,Ui), найти одну за другой функции Wm-1(S), Wm-2(S),…, W1(S) и соответствующие им условные оптимальные управления: um-1(S), um-2(S),…, u1(S).

7. Если начальное состояние S0 задано, найти оптимальный выигрыш Wm(S) = W1(S0) и далее безусловные оптимальные управления (и, если надо, конечное состояние Sm*) по цепочке:

Если начальное состояние S0 не задано, а лишь ограничено условием

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

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

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

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

Таблица 1

Тестовые исходные данные

Число 999 означает, что на данной улице проезд невозможен.

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

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

Таблица 2

Таблица 2 с обозначенными клетками