Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Методы оптимальных решений
Методические указания по выполнению контрольной работы
Оглавление
Решение задач ЛП геометрическим методом
Задача 1. Фабрика может изготавливать 2 вида красок: для внутренних работ E и для внешних работ I. Для их производства используются 2 вида исходных материалов: А и В. Максимальные суточные запасы этих материалов равны соответственно 6 т. и 8 т. Расход материалов А и В в расчете на 1 ед. продукции А и В задается следующей таблицей 1.
Таблица 1.
|
Материалы |
Продукция |
Запас |
|
|
E |
I |
материалов |
|
|
А |
1 |
2 |
6 |
|
В |
2 |
1 |
8 |
Изучение рынка сбыта подсказало следующие закономерности:
Требуется определить величины суточных объемов производства красок E и I, исходя из имеющихся запасов материалов, ограничений спроса и известных цен реализации с целью получения максимальной прибыли от реализации.
Решение. Пусть и предполагаемые объемы производства красок Е и I соответственно, - соответствующую прибыль.
Тогда математическая модель задачи представляется в виде функции:
(1)
и дополнительных условий:
конечности запасов исходных материалов:
(2)
ограничений на спрос на краски:
(3)
и неотрицательности объёмов производства (чтобы задача имела экономический смысл):
, . (4)
Выражение (1) называется целевой функцией, неравенства (2), (3) - ограничениями задачи, а (4) - условиями неотрицательности переменных
1) Заменяем в ограничении знак неравенства на «=» и строим граничную прямую. Для определения искомой полуплоскости, выбираем пробную точку (любую точку, не принадлежащую граничной прямой) и подставляем её координаты в ограничение. Если получаем верное неравенство, то пробная точка принадлежит полуплоскости, иначе – не принадлежит.
а) . Это ограничение определяет полуплоскость с граничной прямой : . Для ее построения найдем две ее точки пересечения с осями координат:
Пусть О(0,0) – пробная точка (О(0,0) : (в), следовательно, пробная точка принадлежит искомой полуплоскости.
Аналогично определяем полуплоскости для остальных ограничений.
б) . : .
О(0,0) – пробная точка: (в).
в) . : .
О(0,0) – пробная точка: (в).
г) . : .
О(0,0) – пробная точка: (в).
д) . : (ось OX2).
О(0,0) в качестве пробной точки брать нельзя, т.к. . Пусть Q(1,2)-пробная точка: (в).
е) . : (ось OX1).
Q(1,2)-пробная точка: (в).
2) Пересекаясь полуплоскости, образуют многоугольник решений (смотрите рисунок 1). Каждая точка многоугольника решений определяет некоторый план производства, который удовлетворяет всем экономическим и техническим ограничениям. Мы должны из этого множества планов выбрать оптимальный, т.е. план, дающий наибольшую прибыль.
Если многоугольника решений нет, то задача несовместна.
Рис. 1. Многоугольник решений при решении задачи ЛПгеометрическим методом
:
Рис. 2. Решение задачи о лакокрасочной фабрике геометрическим методом
Определим координаты точки С: .
: , .
Тогда .
Таким образом, максимальная прибыль в размере тыс. руб. будет получена, если в сутки будет производиться т. краски Е и т. краски I.
Возможные случаи при решении задач ЛП
1) Многоугольник решений ограниченная область:
Рис. 3. Задача имеет единственное решение:
Рис. 4. Задача имеет бесконечное число решений:
Из рис. 4 видно, что Z0 параллельно отрезку CD, поэтому при нахождении Zmax каждая точка этого отрезка является решением (разные планы производства, дающие одинаковую максимальную прибыль).
2) Многоугольник представляет собой неограниченную многоугольную область:
Рис. 5. Целевая функция не ограничена ни сверху, ни снизу:
Zmax=, Zmin=.
Рис. 6. Целевая функция ограничена сверху, но не ограничена снизу: .
Рис. 7. Целевая функция не ограничена сверху, но ограничена снизу:
Рис.8. Целевая функция ограничена и сверху и снизу:
Полуплоскости, ограниченные прямыми образуют многоугольник решений.
Из рис.9 видно, что при добавлении ограничения полуплоскости не имеют ни одной общей точки, следовательно, наложенные ограничения несовместны.
Рис 9. Решение геометрическим методом несовместной задачи
Симплекс-метод решения задач ЛП, обладающих очевидным начальным базисом
Задача 2. Решить задачу о лакокрасочной фабрике симплекс-методом.
Математическая модель задачи (смотрите пример1):
(1)
Приведём задачу к каноническому виду, приводя ограничения типа ˝˝ к ограничениям типа ˝=˝, вводя неотрицательные остаточные переменные S1, S2, S3, S4, причём, , если знак в ограничении , и , если знак .
(2)
Выпишем расширенную матрицу ограничений (коэффициенты при неизвестных в ограничениях):
.
В матрице имеется единичная подматрица, число строк в которой равно количеству ограничений. Поэтому задача имеет очевидный начальный базис , т.к. столбцы единичной подматрицы соответствуют этим переменным.
Замечание 1. Единичная подматрица может получаться и путём перестановки столбцов.
Подставляем эти выражения в целевую функцию для получения Z-строки начальной симплекс-таблицы.
Замечание 2. В данной задаче базисные переменные можно было бы не выражать, т.к. Z не содержит базисных переменных.
Переносим в Z неизвестные в левую часть:
- Z-строка начальной симплекс-таблицы.
Строим начальную симплекс-таблицу (смотрите таблицу 1) и доводим её до оптимальной.
Таблица1
|
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
Ком. |
|
|
Z |
1 |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
- |
Не опт. |
|
S1 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
6 |
6 |
x1→Б |
|
S2 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
8 |
4 |
Б→S2 |
|
S3 |
0 |
-1 |
1 |
0 |
0 |
1 |
0 |
1 |
- |
|
|
S4 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
- |
Данная симплекс-таблица не оптимальна, т.к. в Z-строке у переменных есть отрицательные коэффициенты (относительные оценки). Выбираем наименьшую отрицательную относительную оценку и эта переменная входит в базис: x1→Б (ведущий столбец). Делим элементы столбца ˝Решение˝ на положительные элементы ведущего столбца x1 и результаты записываем в столбец . Выбираем в столбце наименьшее число и эта переменная выходит из базиса: Б→S2 (ведущая строка). Обнуляем элементы ведущего столбца методом Гаусса (на пересечении ведущей строки и ведущего столбца получаем 1, а остальные 0). Следующую симплекс-таблицу (таблица 2) получаем следующим образом: ; ; ; ; .
Таблица 2
|
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
Ком. |
|
|
Z |
1 |
0 |
-1/2 |
0 |
3/2 |
0 |
0 |
12 |
- |
Не опт. |
|
S1 |
0 |
0 |
3/2 |
1 |
-1/2 |
0 |
0 |
2 |
4/3 |
x2→Б |
|
x1 |
0 |
1 |
1/2 |
0 |
1/2 |
0 |
0 |
4 |
8 |
Б→S1 |
|
S3 |
0 |
0 |
3/2 |
0 |
1/2 |
1 |
0 |
5 |
- |
|
|
S4 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
- |
Замечание 3. При обнулении ведущего столбца можно прибавлять или вычитать либо ведущую строку или строку, полученную из ведущей.
Таблица 2 не оптимальна. Для получения следующей таблицы 3 обнуляем элементы столбца x2.
Таблица 3
|
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
Ком. |
|
|
Z |
1 |
0 |
0 |
1/3 |
4/3 |
0 |
0 |
12 |
- |
опт. |
|
x2 |
0 |
0 |
1 |
2/3 |
-1/3 |
0 |
0 |
4/3 |
- |
|
|
x1 |
0 |
1 |
0 |
-1/3 |
2/3 |
0 |
0 |
10/3 |
- |
|
|
S3 |
0 |
0 |
0 |
-1 |
1 |
1 |
0 |
3 |
- |
|
|
S4 |
0 |
0 |
0 |
-2/3 |
1/3 |
0 |
1 |
2/3 |
- |
Получена оптимальная симплекс-таблица. Значения базисных переменных и находятся в столбце ˝Решение˝, а значения небазисных переменных равны нулю.
- максимальная прибыль.
- объёмы производства.
, т.к. .
.
Проверка (подставляем значения базисных переменных в канонический вид):
Симплекс-метод решения задач ЛП, обладающих очевидным начальным базисом и заданных в каноническом виде
Задача 3. Решить задачу линейного программирования, заданную в каноническом виде и имеющую очевидный начальный базис:
Выпишем матрицу ограничений :
.
Очевидный начальный базис , т.к. путем перестановки столбцов при этих переменных получается единичная подматрица.
Выражаем из ограничений базисные переменные через небазисные: и подставляем в :
.
Переносим неизвестные влево:
- Z-строка начальной симплекс-таблицы.
Строим начальную симплекс-таблицу (смотрите таблицу 4).
Таблица4
|
Б |
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
Реш. |
Ком. |
|
|
Z |
1 |
0 |
0 |
70 |
80 |
0 |
30 |
- |
Опт. |
|
x1 |
0 |
1 |
0 |
1 |
2 |
0 |
1 |
- |
|
|
x2 |
0 |
0 |
1 |
2 |
1 |
0 |
6 |
- |
|
|
x5 |
0 |
0 |
0 |
2 |
3 |
1 |
3 |
- |
Данная симплекс-таблиц оптимальна,. Получаем
- максимальное значение при значениях переменных:
.
Проверка:
Решение задач ЛП не обладающих очевидным начальным базисом двухэтапным симплекс-методом
Задача 4. Предприятие может производить 3 вида продукции . Для их производства используются 2 вида ресурсов А и В, запасы которых . Прибыль от реализации единицы продукции .
Технологическая матрица имеет вид:
.
Рынок показывает, что продукт должен производиться в объеме не менее 5 единиц.
Требуется найти оптимальный план производства , при котором выполняются все ограничения и прибыль максимальна.
Получаем задачу ЛП:
(1)
Приведем (1) к каноническому виду, вводя остаточные переменные:
(2)
Выписывает расширенную матрицу ограничений для (2):
Т.к. в матрице нет столбца вида матрице нет, поэтому в 3-ем ограничении отсутствует очевидная базисная переменная и данная задача не имеет очевидного базиса.
Первый этап. На первом этапе решается вспомогательная - задача, целью решения которой является нахождение начального базиса основной - задачи.
Вводим ряд искусственных переменных , количество которых равно количеству недостающих базисных переменных и рассматриваем новую целевую функцию:
Математическая модель задачи:
(3),
где – вектор искусственных переменных.
Вводим в 3-е ограничение вводим искусственную переменную и решаем задачу вида:
при ограничениях:
(4)
Выписываем расширенную матрицу ограничений для (4):
Так как в матрице есть единичная подматрица, образованная столбцами при переменных , следовательно - очевидный начальный базис для - задачи.
Выражаем базисную переменную из ограничения и исключаем из целевой функции:
Переносим неизвестные влево:
- - строка начальной симплекс-таблицы.
Строим начальную симплекс-таблицу (таблица 5) - задачи и доводим ее до оптимальной.
Таблица 5
|
Б |
ω |
x1 |
x2 |
x3 |
S1 |
S2 |
S3 |
r |
Реш. |
bi/ai |
Комм. |
|
ω |
1 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
-5 |
- |
не опт. |
|
S1 |
0 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
10 |
5 |
х1→Б |
|
S2 |
0 |
1 |
3 |
2 |
0 |
1 |
0 |
0 |
15 |
15 |
Б→r |
|
r |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
1 |
5 |
5 |
|
|
w |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
- |
опт. |
|
S1 |
0 |
0 |
2 |
1 |
1 |
0 |
2 |
-2 |
0 |
- |
|
|
S2 |
0 |
0 |
3 |
2 |
2 |
1 |
1 |
-1 |
10 |
- |
|
|
X1 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
1 |
5 |
- |
Т.к. , значит, I этап завершен успешно, и искусственная переменная выведена из базиса.
Второй этап .На II этапе в качестве начального базиса основной задачи принимаем оптимальный базис вспомогательной задачи, т.е. .Возвращаемся к целевой функции исходной задачи, и столбцы искусственных переменных удаляем из симплекс-таблицы.
Выражаем базисную переменную из оптимальной симплекс- таблицы и исключаем из целевой функции :
Переносим неизвестные влево: – - строка начальной симплекс-таблицы основной задачи.
Строим начальную симплекс-таблицу основной задачи и доводим ее до оптимальной (таблица 6).
Таблица 6
|
Б |
Z |
x1 |
x2 |
x3 |
S1 |
S2 |
S3 |
Реш. |
bi/ai |
Ком. |
|
Z |
1 |
0 |
-2 |
-2 |
0 |
0 |
-1 |
5 |
- |
Не опт. |
|
S1 |
0 |
0 |
2 |
1 |
1 |
0 |
2 |
0 |
0 |
x3→Б |
|
S2 |
0 |
0 |
3 |
2 |
0 |
1 |
1 |
10 |
5 |
Б→S1 |
|
x1 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
5 |
- |
|
|
Z |
1 |
0 |
2 |
0 |
2 |
0 |
3 |
5 |
- |
Опт. |
|
x3 |
0 |
0 |
2 |
1 |
1 |
0 |
2 |
0 |
- |
|
|
S2 |
0 |
0 |
-1 |
0 |
-2 |
1 |
-3 |
10 |
- |
|
|
x1 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
5 |
- |
Имеем:
– объем производства I – го продукта.
– II продукт не производится.
– III продукт не производится.
S1 = 0 – ресурс А используется полностью.
S2 = 10 – остаток ресурса В.
S3 = 0 – превышение производства продукта 1 над плановым заданием.
Замечание 4. Если , тогда исходная задача несовместима; переход ко 2-му этапу не осуществляется;
Экономическая интерпретация алгоритма симплекс-метода и оптимальной симплекс-таблицы
Задача 5. Предприятие может выпускать 3 различных вида продукции, цены реализации которых равны соответственно При производстве используются два вида ресурсов запасы, которых , а цены закупки единицы ресурса .
Технологическая матрица имеет вид:
.
Определить оптимальный план работы предприятия, дать экономический анализ для каждой итераций поиска решения с помощью симплекс-метода.
Решение.
Пусть искомые объемы производства продуктов 1,2,3.
Найдем по формуле (1) ценовые коэффициенты переменных в функции прибыли.
Имеем:
таким образом, производство продуктов 1,2 рентабельно, производство продукта 3 нерентабельно.
Задача ЛП о нахождении оптимального плана имеет вид:
Приведем задачу (10) к каноническому виду:
Начальный базис задачи: .
Z – строка начальной симплекс-таблицы 7:
.
Таблица 7
|
Б |
Z |
x1 |
x2 |
x3 |
S1 |
S2 |
Реш. |
bi/aij |
Ком. |
|
Z |
1 |
-2 |
-3 |
1 |
0 |
0 |
0 |
- |
Не опт. |
|
S1 |
0 |
2 |
1 |
2 |
1 |
0 |
15 |
15 |
x2→Б |
|
S2 |
0 |
1 |
2 |
3 |
0 |
1 |
10 |
5 |
Б→S2 |
Экономический анализ:
Производства нет: .
Прибыль равна 0: .
Остатки ресурсов их запасам: .
=> план не оптимален, целесообразно включить в производство продукт 2, при этом прибыль составит 3руб. на 1 ед. дополнительного производства продукта 2 т.е. .
При увеличении остатки ресурсов уменьшаются:
Максимально возможный объём производства продукта. 2:
→ → → .
Следовательно, производство продукта 2 можно увеличить до 5 ед. При этом ресурс 2 расходуется полностью: , а остаток ресурса составит: ед. Новый план производства представлен в таблице 8.
Таблица 8
|
Б |
Z |
x1 |
x2 |
x3 |
S1 |
S2 |
Реш. |
bi/aij |
Ком. |
|
Z |
1 |
-1/2 |
0 |
11/2 |
0 |
3/2 |
15 |
- |
Не опт. |
|
S1 |
0 |
3/2 |
0 |
1/2 |
1 |
-1/2 |
10 |
20/3 |
x2→Б |
|
x2 |
0 |
1/2 |
1 |
3/2 |
0 |
1/2 |
5 |
10 |
Б→S2 |
Экономический анализ:
- продукты 1 и 3 не производятся,
- объём производства продукта 2;
- размер получаемой прибыли.
=> план не оптимален; целесообразно увеличивать производство продукта 1, при этом прибыль увеличивается на 0.5 руб. на 1 ед. увеличения производства продукта 1, т.е. .
, остаток ресурса 1 идет на производство продукта 1.
- производство продукта 2 уменьшается, т.к. необходимо освободить часть ресурса 2 для производства продукта 1.
Максимально возможный объём производства продукта. 2:
→ → → .
Следовательно, производство продукта 1 можно увеличить до ед. При этом ресурс 1 расходуется полностью: , а объём производства товара 2 уменьшится до: ед.
Оптимальный план производства представлен в таблице 9.
Таблица 9
|
Б |
Z |
x1 |
x2 |
x3 |
S1 |
S2 |
Реш. |
bi/aij |
Ком. |
|
Z |
1 |
0 |
0 |
17/3 |
1/3 |
4/3 |
55/3 |
- |
опт. |
|
x1 |
0 |
1 |
0 |
1/3 |
2/3 |
-1/2 |
20/3 |
- |
|
|
x2 |
0 |
0 |
1 |
4/3 |
-1/3 |
2/3 |
5/3 |
- |
Экономический анализ:
- производство продукта 1;
- производство продукта 2;
- продукт 3 не производится.
- максимальная прибыль.
- ресурсы используются полностью.
Экономический анализ ресурсов:
Таблица 10
|
Ресурс |
Отаток |
Статус |
Ценность |
Комментарий |
|
1 |
0 |
дефицит |
Цена на ресурс может возрасти не более чем на руб., но его выгодно будет использовать Закупка 1 ед. ресурса по текущей цене и включение в производство дает дополнительную прибыль руб. |
|
|
2 |
0 |
дефицит |
Цена на ресурс может возрасти не, более чем на руб., но его выгодно будет использовать. Закупки 1 ед. ресурса по текущей цене и включение в производство дает дополнительную прибыль руб. |
Вывод: В первую очередь стоит приобретать ресурс 2 как более ценный.
Экономический анализ продуктов:
Таблица 11
|
Продукт |
Статус |
Относительная оценка в опт плане |
Комментарий |
|
1 |
базисный |
0 |
Выгодный, производится в объеме и дает вклад в прибыль руб. |
|
2 |
базисный |
0 |
Выгодный, производится в объеме и дает вклад в прибыль руб. |
|
3 |
не базисный |
Не производится. Убыток от производства 1 ед. продукта по сравнению с опт. планом составит руб. Производство станет выгодным, если цена реализации увеличивается, по крайней мере, на руб. |
Транспортная задача линейного программирования
Задача 6. На двух складах хранится однородный товар в объёмах , . Его необходимо доставить в четыре магазина, потребности которых b1=30, b2=30, b3=20, b4=20. Удельные транспортные затраты на перевозки: . Для данной задачи составить оптимальный план перевозок.
Определим тип задачи:
- суммарные запасы;
- суммарные потребности.
Т.к. , то задача закрытая.
Если выполняется неравенство - транспортная задача называется открытой транспортной задачей с избыточным спросом. Она может быть приведена к закрытой задаче, если ввести в рассмотрение условного поставщика , величина запасов у которого: , а удельные транспортные затраты по перевозке груза от условного поставщика ко всем потребителям принимаются равными 0: . Компоненты найденного плана поставок означают количество товара, которое недополучит потребитель .При этом матрица планирования транспортной задачи дополняется одной строкой.
Если выполняется неравенство - транспортная задача называется открытой транспортной задачей с избыточным предложением. Она может быть приведена к закрытой задаче, если ввести в рассмотрение условного потребителя , величина запасов у которого: , а удельные транспортные затраты по перевозке груза от условного поставщика ко всем потребителям принимаются равными 0: . Компоненты , найденного плана поставок означают количество товара, которое останется у поставщика после того как потребности всех потребителей будут удовлетворены. При этом матрица планирования транспортной задачи дополняется одним столбцом
Определим тип задачи:
- суммарные запасы;
- суммарные потребности.
Т.к. , то задача закрытая.
Не учитывая удельные транспортные затраты на перевозку груза, начинаем удовлетворять потребности 1-го потребителя B1 за счёт 1-го поставщика A1. Потребности потребителя B1 удовлетворены, а у поставщика A1 осталось 20 ед. товара, поэтому за счёт A1 пытаемся удовлетворить потребности B2 (переходим на клетку вправо). На складе A1 товара не осталось, а потребности B2 не удовлетворены, поэтому удовлетворяем его потребности за счёт склада А2 (перемещаемся на клетку вниз). Потребности В2 удовлетворены, а на складе А2 осталось 40 ед. товара, поэтому удовлетворяем за счёт его потребности В3 (переходим на клетку вправо). Потребности В3 удовлетворены, а на складе А2 осталось 20 ед. товара, поэтому удовлетворяем за счёт его потребности В4 (переходим на клетку вправо). Всего базисных клеток.
Начальный план перевозок, полученный методом северо-западного угла, представлен в таблице 12:
Таблица 12
|
|
2 20 |
1 |
3 |
50 |
|
2 |
3 10 |
4 20 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Клетка называется занятой, если в ней находится какой-либо объём перевозок. Базисом транспортной задачи называется набор занятых клеток, обладающих следующим свойством: в каждой строке и в каждом столбце должна быть хотя бы одна базисная клетка. Потенциалами строк и столбцов относительно базиса Б называется набор чисел , , удовлетворяющие уравнению:
, если (1)
где - потенциал -ой строки; - потенциал -ого столбца.
После того как найдены потенциалы строк и столбцов определяем относительные оценки небазисных клеток по формуле:
, если (2)
Если нет то текущий план оптимален.
Проверим на оптимальность начальный план перевозок, представленный в таблице 12.
По базисным клеткам по формуле (1) составим систему уравнений для определения потенциалов строк и столбцов:
Эта система содержит уравнений с неизвестными. Т.к. уравнений на 1 меньше чем неизвестных, система является неопределённой и одному неизвестному (которое чаще всего встречается) присваивают нулевое значение. После этого остальные потенциалы определяются однозначно.
Пусть , тогда
Вычисляем по формуле (2) относительные оценки небазисных клеток:
Т.к. есть , текущий план не оптимален.
В таблице 13 представлен начальный план перевозок, проверенный на оптимальность:
Таблица 13
|
4 30 |
2 20 |
1 -2 |
3 1 |
50 |
|
2 -3 |
3 10 |
4 20 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Примечание: в правом нижнем угле указаны относительные оценки небазисных клеток.
Если план не оптимален, то выбираем клетку с наименьшей отрицательной относительной оценкой и включаем эту клетку в базис, т.е. . (3)
Чтобы найти клетку, исключаемую из базиса, строим цикл пересчёта, который начинается с клетки и в дальнейшем проходит по базисным клеткам. Циклом называется замкнутая ломаная линия, вершины которой расположены в базисных клетках, а звенья – вдоль строк и столбцов, причём в каждой строке и каждом столбце соединяются либо две клетки, либо не одной. Если ломаная цикла пересекается, то точки пересечения вершинами не являются.
В клетках, расположенных в вершинах цикла перераспределяем объёмы перевозок. К клетке вводимой в базис добавляем некоторую величину Θ (промежуточная рента), из следующей клетки Θ вычитаем, далее прибавляем и т.д. Промежуточная рента Θ равна минимальному объёму перевозок в тех клетках, где Θ вычитаем. Базисная клетка, в которой объём перевозок равен Θ выходит из базиса (если таких клеток несколько, то выходит одна, а в других объёмы перевозок равны 0). Следующий план будет дешевле предыдущего на величину
. (4)
Произведем перераспределение перевозок и доведем до оптимального план из таблицы 13.
Выбираем наименьшую отрицательную относительную оценку () и эту клетку включаем в базис ().
В таблице 14 построен цикл пересчёта и перераспределены перевозки:
Таблица 14
|
4 30 -Θ |
2 20 +Θ |
1 |
3 |
50 |
|
2 +Θ |
3 10 -Θ |
4 20 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Определим промежуточную ренту Θ:
.
Уменьшение транспортных затрат:.
Новый план перевозок записан в таблице 15(изменяем объёмы перевозок только в клетках, находящихся в вершинах цикла):
Таблица 15
|
4 20 |
2 30 |
1 |
3 |
50 |
|
2 10 |
3 |
4 20 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Проверим новый план на оптимальность.
Потенциалы строк и столбцов:
Пусть , тогда
Относительные оценки:
В таблице 16 представлен начальный план перевозок, проверенный на оптимальность:
Таблица 16
|
4 20 |
2 30 |
1 -5 |
3 0 |
50 |
|
2 10 |
3 3 |
4 20 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Т.к. есть , текущий план не оптимален. Вводим клетку в базис и строим цикл пересчёта.
Новый план перевозок представлен в таблице 17.
Таблица 17
|
4 20 -Θ |
2 30 |
1 +Θ |
3 |
50 |
|
2 10 +Θ |
3 |
4 20 -Θ |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Определим промежуточную ренту:
.
Уменьшение транспортных затрат:.
Новый план перевозок (смотри таблицу 18):
Таблица 18
|
4 |
2 30 |
1 20 |
3 |
50 |
|
2 30 |
3 |
4 0 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Проверим новый план на оптимальность.
Потенциалы строк и столбцов:
Пусть , тогда
Относительные оценки:
План перевозок имеет вид (смотри таблицу 19):
Таблица 19
|
4 5 |
2 30 |
1 20 |
3 5 |
50 |
|
2 30 |
3 -2 |
4 0 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Т.к. есть , текущий план не оптимален. Вводим клетку в базис и строим цикл пересчёта (смотри таблицу20).
Таблица 20
|
|
2 30 -Θ |
1 20 +Θ |
3 |
50 |
|
2 30 |
3 +Θ |
4 0 -Θ |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Определим промежуточную ренту:
.
Уменьшение транспортных затрат: .
Новый план перевозок (смотри таблицу 21):
Таблица 21
|
4 |
2 30 |
1 20 |
3 |
50 |
|
2 30 |
3 0 |
4 |
1 20 |
50 |
|
30 |
30 |
20 |
20 |
100 |
Проверим новый план на оптимальность.
Потенциалы строк и столбцов:
Пусть , тогда
Относительные оценки:
Т.к. нет , текущий план оптимален.
Стоимость перевозок по этому плану:
.
Минимальная стоимость перевозок в размере 160 руб. достигается, если перевезти с 1-го склада во 2-ой магазин 30 ед. товара и в 3-ий магазин 20 ед., а со 2-го склада – 30 ед. в 1-ый магазин и 20 ед. в 4-ый магазин.
Модели сетевого планирования и управления
Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ, заданный в форме сети.
Работа в сетевом планировании и управлении (СПУ):
Событие – отдельный этап выполнения проекта, не имеющий продолжительности. На сетевом графике (графе) события изображаются вершинами, работы – ориентированными дугами.
Задача 7. Для сетевого графика изображенного на рисунке 10 определить временные параметры работы (2-4).
Рис.10. План выполнения некоторого комплекса взаимосвязанных работ
Определим критический путь (самый продолжительный из V1 в V6). Его длина определяет продолжительность выполнения всего комплекса работ. Продолжительности полных путей для сетевого графика представлены в таблице 22.
Таблица 22
|
Полный путь |
Продолжительность |
|
0-3-5-6 0-1-2-4-6 0-1-2-4-5-6 0-1-4-5-6 0-1-4-6 0-2-4-6 0-2-4-5-6 |
6+20+3=29 10+5+8+10=33 10+5+8+5+3=31 10+15+5+3=33 10+15+10=35 3+8+10=21 3+8+5+3=19 |
Путь 0-1-4-6 имеет наибольшую продолжительность 35 сут. Следовательно, выполнение всех работ закончится через 35 сут. События 0, 1, 4, 6 –критические, а (0,1), (1,4), (4,6) – критические работы.
Временные параметры событий
Ранний (ожидаемый) срок свершения -го события определяется продолжительностью максимального пути, предшествующего этому событию, т.е.
, (1)
где - любой путь, предшествующий -му событию.
Поздний (предельный) срок свершения -го события определяется как разность между длиной критического пути и длиной максимального пути, последующего за этим событием, т.е.
, (2)
где - любой путь, следующий за -м событием.
Резерв времени -го события определяется как разность между поздним и ранним сроками его свершения, т.е
. (3)
Он показывает, на какое время можно задержать наступление этого события, не увеличивая времени выполнения всего комплекса работ. Критические события резервов времени не имеют.
Временные параметры событий для сетевого графика из рисунка 10 представлены в таблице 23.
Таблица 23
|
№собы- тия |
Сроки свершения события, сут |
Резерв времени , сут. |
|
|
ранний |
поздний |
||
|
0 1 2 3 4 5 6 |
0 10 15 6 25 30 35 |
0 10 17 12 25 32 35 |
0 0 2 6 0 2 0 |
Для вершины 2 существует два предшествующих пути:
и .
При определении поздних сроков свершения событий движемся по сети в обратном направлении.
Для вершины 4 существует два последующих пути:
и
.
Временные параметры работ
Ранний срок начала работы совпадает с ранним сроком наступления предшествующего события, т.е.
. (3)
Ранний срок окончания равен сумме раннего срока начала и времени продолжительности работы, т.е.
. (4)
Поздний срок окончания равен позднему сроку наступления следующего события, т.е. . (5)
Поздний срок начала работы равен разности между поздним сроком окончания и временем выполнения работы, т.е.
. (6)
Резервы времени работ
а) Полный резерв времени показывает, на сколько можно увеличить время выполнения данной работы, не увеличивая времени выполнения всего комплекса работ:
. (7)
б) Частный резерв времени I-го вида - часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока её начального события:
. (8)
в) Частный резерв времени II-го вида (свободный резерв) - часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока её конечного события:
. (9)
г) Независимый резерв времени - часть полного резерва времени, на которую можно увеличить продолжительность работы, при условии, что все предшествующие события заканчиваются в поздние сроки, а все последующие начинаются в ранние:
. (10)
Он используется для увеличения продолжительности только данной работы.
Если на критическом пути лежит начальное событие, то , если конечное - , если начальное и конечное события лежат на критическом пути, сама работа не принадлежит этому пути, то все резервы времени равны .
Вычислим временные параметры работы (2,4) для сетевого графика из сетевого графика из рисунка 10..
Ранний срок начала работы .
Ранний срок окончания работы .
Поздний срок окончания работы .
Поздний срок начала работы
Полный резерв времени , т.е. при увеличении продолжительности работы (2,4) на 2 сут. резервы времени путей, содержащих эту работу, уменьшатся на 2 сут., а продолжительность выполнения всего комплекса работ не изменится.
Частный резерв времени I-го вида .
Свободный резерв времени .
Независимый резерв времени
, т.е. продолжительность работы (2,4) не может быть увеличена без изменения резервов времени остальных работ.
Действительно для работы (2,4)
Замечание 5. Если , то ставится прочерк.
Библиографический список