- •1 Методы и модели линейного программирования
- •1.1. Основные положения
- •1.2. Симплексный метод
- •1.3. Метод Гомори. Целочисленное решение
- •1.4. Двойственная задача
- •1.4.1. Анализ устойчивости двойственных оценок
- •1.5. Решение задачи линейного программирования средствами Microsoft Excel
- •1.6. Задачи с булевыми переменными
- •1.7. Варианты заданий линейного программирования
- •2.Динамическое программирование
- •2.1. Суть метода динамического программирования
- •2.2. Задача о рюкзаке. Уравнение Беллмана для задачи о рюкзаке.
- •2.3. Реализации метода динамического программирования для задачи о рюкзаке.
- •2. Двухиндексные задачи линейного программирования. Стандартная транспортная задача (тз).
- •Исходные параметры модели тз
- •1.4. Варианты заданий линейного программирования
- •3. Сетевое моделирование
- •3.1. Основные положения
- •3.2. Сетевой график и правила его построения
- •3.3 Расчет параметров сетевых графиков
- •3.4. Оптимизация сети методом время-стоимость
- •3.5 Варианты заданий сетевого планирования
- •4. Правила оформления курсового проекта
- •Библиографический список
- •Приложение 1
- •Курсовой проект
3.4. Оптимизация сети методом время-стоимость
Оптимизация сети по стоимости относительно просто осуществляется с помощью так называемого метода время-стоимость, который предполагает сокращение общей продолжительности работ. Оптимизация сети по стоимости практически проводится на полностью уже сформированном сетевом графике.
Вычислительная процедура метода время — стоимость заключается в последовательном выполнении ряда правил и характеризуется многошаговым процессом, каждая итерация k которого сокращает планируемую продолжительность выполнения комплекса на единицу времени и одновременно увеличивает стоимость его проведения на величину , и включает следующие этапы:
Нулевая итерация включает:
расчет критерия оптимальности - показателя наклона , называемого также коэффициентом дополнительных затрат: ,
где , - продолжительность, соответственно, нормального и экстренного (физически минимального) срока выполнения работы (i,j); , - затраты, соответственно, на нормальную и экстренную продолжительность ведения работ.
Построение сети с нормальной продолжительностью выполнения работ.
Расчет сроков наступления и свершения событий, начала и окончания работ резервов для сети с нормальной продолжительностью выполнения работ. Момент начала выполнения комплекса работ обычно приравнивается нулю, т.е. Т0=0.
Результаты расчетов заносятся в таблицу 3.1:
Таблица 1.4
Код (i,j) |
|
|
|
|
|
|
|
|
|
|
|
|
0-1 |
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
Дополнительно строится таблица, которая заполняется исходными данными и временными параметрами для исходной сети с нормальной продолжительностью (для итерации k=0). Для наглядности, при следующих итерациях в таблице в соответствующем столбце сокращаемые работы подчеркиваются, а при достижении экстренной продолжительности – заключаются в квадрат (или прямоугольник). Квадратами также отмечаются те работы которые нельзя сокращать, т.е. фиктивные работы. Пример занесения подобных значений приведен в таблице 1.4:
Таблица 1.4
Код (i,j) |
|
|
|
|
|
Сокращение единиц времени |
||||||
Итерации k |
Итерации k |
|||||||||||
0 |
1 |
… |
n |
0 |
1 |
… |
n |
|||||
0-1 |
|
|
|
|
0 |
|
|
|
|
|
|
|
0-2 |
|
|
- |
|
|
|
|
|
|
|
|
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Итерация k включает следующие операции:
Находят полные резервы времени работ и по ним критический путь (пути) и его (их) продолжительность.
Если на данном шаге сеть имеет один критический путь, то находят на нем работу (i,j) с наименьшей величиной показателя наклона . Если сеть имеет несколько критических путей, то на каждом пути находят критическую работу (i,j) с наименьшей величиной показателя наклона .
Проверяют выполнение условий и , где Р – величина эффекта, получаемая при сокращении продолжительности работы на единицу времени, С – имеющийся ресурс. Если они не выполняются, дальнейший расчет прекращают и в качестве оптимальной сети принимают сеть, соответствующую шагу (k-1). Если условие выполняется, расчет продолжают.
Сокращают продолжительность выбранной критической работы (i,j) или одновременно нескольких работ (см. пункт 2.1) на единицу времени. Сокращать можно продолжительность только тех работ, для которых выполняется условие , где - продолжительность работы (i,j) для сети, соответствующей (k-1) шагу оптимизации.
Результаты расчетов заносят в табл.1.4
Переходят к следующей (k+l) итерации и возвращаются к пункту 2.1.