Основы математического программирования (стр. 16 )

Найдем потенциалы поставщиков ui и потребителей vJ,

Примем u1 = 0.

c11 = u1 + v1 c22 = u2 + v2 c24 = u2 + v4 c25 = u2 + v5 c31 = u3 + v1 c33 = u3 + v3 c35 = u3 + v5

v1 = c11 – u1 = 1 – 0 = 1 v2 = c22 – u1 = 1 – 0 = 1 v4 = c24` – u2 = 3 – 3 = 0 u2 = c25 – v5 = 3 – 0 = 3 u3 = c31 – v1 = 4 – 1 = 3 v3 = c33 – u3 = 1 – 3 = – 2 v5 = c35 – u3 = 3 – 3 = 0

Шаг. 2. Проверка оптимальности.

Найдем оценки свободных ячеек следующим образом:

D12 = (u1 + v2) – c12 = (0 – 0) – 0 = 0

D13 = (u1 + v3) – c13 = (0 + 2) – 3 = – 1

D14 = (u1 + v4) – c14 = (0 + 0) – 4 = – 4

D15 = (u1 + v5) – c15 = (0 + 0) – 2 = – 2

D21 = (u2 + v1) – c21 = (3 + 1) – 5 = – 1

D22 = (u2 + v2) – c22 = (3 + 1) – 1 = – 3

D32 = (u3 + v2) – c32 = (3 – 1) – 8 = – 6

D34 = (u3 + v4) – c34 = (3 + 0) – 4 = –1

Нет положительных оценок. Найдено оптимальное решение.

Х11 = 15

Х22 = 12

Х24 = 8

Х25 = 5

Х31 = 5

Х33 = 5

Х35 = 10

Все остальные Хij = 0.

F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121

Задача :

У поставщиков A1 , A2 , A3 , находится соответственно 40 , 150 , 100 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количествах 20 , 80 , 90 , 60 , 40 единиц соответственно.

Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 7 , 3 , 5 , 4 , 2 .

Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 6 , 2 , 3 , 1 , 7 .

Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 3 , 5 , 2 , 6 , 4 .

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

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

1. Согласно условию задачи составим таблицу. Поставщик Потребитель ЗАПАС B1 B2 B3 B4 B5 А1 7 3 5 4 2 40 А2 6 2 3 1 7 150 А3 3 5 2 6 4 100 Потребность 20 80 90 60 40

2. Найдем начальное опорное решение методом наилучших цен..

Минимальный элемент матрицы тарифов находится в ячейке A2B4 и равен 1.

Запасы поставщика A2 составляют 150 единиц продукции. Потребность потребителя B4составляет 60.

Разместим в ячейку A2B4 значение равное min = { 150 , 60 } = 60.

Мы полностью удовлетворили запросы потребителя B4. Вычеркиваем столбец 4 таблицы, т. е исключаем его из дальнейшего рассмотрения.

Поставщик	Потребитель																ЗАПАС
B1	B2	B3	B4	B5
А1	7	3	5	4	2	40
		0						40
А2	6	2	3	1	7	150
10		80				60
А3	3	5	2	6	4	100
10				90
Потребность	20	80	90	60	40

Минимальный элемент матрицы тарифов находится в ячейке A1B5 и равен 2.

Запасы поставщика A1 составляют 40 единиц продукции. Потребность потребителя B5 составляет 40.

Разместим в ячейку A1B5 значение равное min = { 40 , 40 } = 40

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

Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 2.

Запасы поставщика A2 составляют 90 единиц продукции. Потребность потребителя B2 составляет 80.

Разместим в ячейку A2B2 значение равное min = { 90 , 80 } = 80.

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

Минимальный элемент матрицы тарифов находится в ячейке A3B3и равен 2. и т. д

Проверим условие баланса для базисных ячеек. Сумма заполненных нами ячеек должна равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

В нашем случае количество заполненных нами ячеек равно 6. Требуется, чтобы было заполнено 7 ячеек. В свободную ячейку A1B2 запишем ноль, как в ячейку не образующую цикл с ранее занятыми ячейками.

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

Sнач. =2 * 40 + 6 * 10 + 2 * 80 + 1 * 60 + 3 * 10 + 2 * 90 = 570

Шаг 1. Нахождение потенциалов.

Найдем потенциалы поставщиков ui и потребителей vJ,

Примем u1 = 0.

c12 = u1 + v2 c15= u1 + v5 c21 = u2 + v1 c22 = u2 + v2 c24 = u2 + v4 c31 = u3 + v1 c33 = u3 + v3

v2 = c12 – u1 = 3 – 0 = 3 v5 = c15 – u1 = 2 – 0 = 2 v1 = c21 – u2 = 6 + 1 = 7 u2 = c22 – v2 = 2 – 3 = –1 v4 = c24 – u2 = 1 + 1 = 2 u3 = c31 – v1 = 3 – 7 = – 4 v3 = c33 – u3 = 2 + 4 = 6

Шаг. 2. Проверка оптимальности.

Найдем оценки свободных ячеек следующим образом:

D11 = (u1 + v1) – c11 = (0 + 7) – 7 = 0

D13 = (u1 + v3) – c13 = (0 + 6) – 5 = 1

D14 = (u1 + v4) – c14 = (0 + 2) – 4 = – 2

D23 = (u2 + v3) – c23 = (– 1 + 6) – 3 = 2

D25 = (u2 + v5) – c25 = (– 1 + 2) – 2 = – 1

D32 = (u3 + v2) – c32 = (– 4 + 3) – 5 = – 6

D34 = (u3 + v4) – c34 = (– 4 + 2) – 6 = – 8

D35 = (u3 + v5) – c35 = (– 4 + 2) – 4 = – 6

Среди оценок есть положительные, следовательно, решение не оптимальное.

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

Из положительных оценок выбираем максимальную. Это ячейка А3В5. Ее оценка D23 = 2.

Шаг 3. Улучшение плана.

Поставщик	Потребитель																ЗАПАС
B1	B2	B3	B4	B5
А1	7	3	5	4	2	40
	1	0						40
А2	6	2	3	1	7	150
10		80			2	60
А3	3	5	2	6	4	100
10				90
Потребность	20	80	90	60	40

X = min(Xij). = 10,