Математические модели и методы в управлении

 

Рисунок 6                                                     Рисунок 7

 

 

 

 

-	50	-	-
60	10	-	-
-	0ф			60
		50	10

 

-	50	-	-
60	10	-	-
-	0ф	50	10

                 Рисунок 8                                                      Рисунок 9

 

В оставшейся незаполненной  части матрицы перевозок  клетка  а₂₂ имеет меньший тариф.  Заполняем ее: ставим перевозку 10,  закрываем  вторую строку и второй столбец  – рисунок 8.

          Дальше матрица заполняется однозначно  – в незаполненные клетки а₃₃ и а₃₄ ставим требуемые там 50 и 10 единиц груза соответственно.

   План составлен  – рисунок 9 . 

Подсчитаем стоимость  затрат по составленному плану:

L(Х_СЗУ) = 50·2 + 60·2 + 10·4 + 50·7  = 610 (ден.ед.)

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

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

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

Этап 2. Проверка оптимальности полученного плана перевозок. Введем специальные показатели u_i для каждой строки    матрицы    перевозок    (каждого    поставщика),    где i - 1, m , и показатели v_j для каждого столбца (каждого потребителя), где j = 1, n. Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство

                                                          v_j + u_i = c_ij.

Чтобы оценить  оптимальность распределения, для  пустых клеток (i;j) матрицы перевозок определяются их оценки, которые обозначим через d_ij, по формуле:

                                        d_^ij =(u_ⁱ + v_^j )- c_^ij

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

Таблица 3

Мощности поставщиков	Мощности  потребителей				ui
	60	60	50	10
50	2              70	2	3	100	0
70	2           30	4	5                     50	100	2
60	6	5             10	7                     40	100	3
vj	0	2	4	97

 

d₁₁ = (0 + 0) – 2 < 0     d₁₃ = (4 + 0) – 3 > 0  

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

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

Для выбранной  клетки строится замкнутая линия (контур), начальная вершина которой   лежит в выбранной   клетке, а все  остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть только горизонтальными  и  вертикальными.   Вершиной   контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой  угол (нельзя рассматривать как вершины клетки, где горизонтальные и  вертикальные отрезки контура пересекаются). Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура расставляются поочередно знаки « + » и «-», начиная со знака «+» в выбранной свободной клетке. Пример простого контура показан пунктиром в таблице 4, хотя вид контура может быть самым разнообразным. Величина перераспределяемой поставки определяется как наименьшая  из величин поставок в вершинах контура со знаком «-», и на эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «—». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка занятой, в то время как одна из занятых клеток при обязательно освободится.

Таблица 4

Мощности поставщиков	Мощности  потребителей				ui
	60	60	50	10
50	2              70	2 -	3       +	100
70	2           30	4	5                     50	100
60	6	5   +             10	7      -                     40	100
vj

Получим новый план

-	-	50	-
60	10	-	-
-	50	0	10

 

 

 

Подсчитаем стоимость  затрат по составленному плану

L(Х_СЗУ) = 50·3 + 60·2 + 10·4 + 50·5  = 560 (ден.ед.)

Проверим  на оптимальность полученного плана перевозок.

Таблица 5

Мощности поставщиков	Мощности  потребителей				ui
	60	60	50	10
50	2              70	2	3	100	0
70	2           30	4	5                     50	100	3
60	6	5               10	7                          40	100	4
vj	-1	1	3	96

                                     d_ij =(u_i + v_j )- c_ij

d₁₁ = (0 - 1) – 2 <0     d₁₂ = (0 + 1) – 2 < 0  d₁₄ = (0 + 96) – 100 < 0    

d₂₃ = (3 + 3) – 5 > 0   

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

Улучшение неоптимального плана перевозок 

Таблица 6

Мощности поставщиков	Мощности  потребителей				ui
	60	60	50	10
50	2              70	2	3	100	0
70	2           30	4     -	5        +                       50	100	3
60	6	5   +             10	7       -                     40	100	4
vj	-1	1	3	96

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

Оптимальная стоимость  перевозок равна 560 (ден.ед.)

-	-	50	-
60	10	-	-
-	50	0	10

 

 

 

 

Задача 4

Управление  проектами и сетевые диаграммы

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

1. Построить  сетевую диаграмму проекта.

2. Определить  минимальный срок проекта.

3. Указать  критические стадии проекта.

 

Стадия	Предшественник	Продолжительность, недели
A	-	6
B	А	3
C	В	3
D	А	2
E	D	7
F	В, D	8
G	Е	8
H	D	3

 

Решение:

Сетевая диаграмма  будет выглядеть следующим образом

 

 

 

 

 

Определим минимальный  срок проекта

Стадия	Продолжительность, недели	Предшественник	ЕS	EF	LS	LF	Врем. резерв
A	6	-	0	6	0	6	0
B	3	А	6	9	6	9	0
C	3	В	9	12	9	12	0
D	2	А	6	8	6	8	0
E	7	D	8	15	8	15	0
F	8	В, D	9	17	9	17	0
G	8	Е	15	23	15	23	0
H	3	D	8	11	8	11	0