Экономико-математические методы и модели в логистике

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»

Кафедра информатики и компьютерных технологий

Курсовая работа

На тему: «Экономико-математические методы и модели в логистике»

Выполнила: студентка 4-го курса, группы 962

Горбова А.А.

Проверила: Петухова Н.М.

Санкт-Петербург

2012 г.



Введение

Курсовая работа состоит в выполнении двух задач.

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

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

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

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

1. Задача №1 (Вариант 12)

Условие задачи

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

Табл. 1. Цены перевозок

	Завод 1	Завод 2	Завод 3	Завод 4
Поставщик 1	1600	1400	1100	1250
Поставщик 2	1300	1350	1500	1200
Поставщик 3	1000	1250	900	1400

Поставщики готовы отгружать следующее количество сырья:

Табл. 2. Запасы продукции

	Поставщик 1	Поставщик 2	Поставщик 3
Мах отгрузка, маш./нед.	50	55	60

Недельные потребности заводов составляют:

Табл. 3. Заказы клиентов

	Завод 1	Завод 2	Завод 3	Завод 4
Потребность, маш./нед.	50	30	45	40

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

Задания:

1. Составление транспортной таблицы.

2. Построение математической модели задачи.

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

4. Выполнение расчета модели в Excel, используя надстройку Поиск решения. Проверка ручного расчета модели и расчета модели, выполненном в Excel.

5. Нахождение разницы между наилучшим и наихудшим планом перевозок.

Затем необходимо ответить на вопросы, подтверждая ответы расчетами, выполненными с помощью надстройки Поиск решения:

а)Возможны ли альтернативные решения?

б)После составления плана перевозок выяснилось, что, возможно, Поставщик 4 сможет отгружать на 5 машин сырья больше, чем планировал. Каким будет тогда план перевозок?

с) Выяснилось, что Поставщик 4 не сможет отгружать продукции больше, чем планировал, к тому же Поставщик 1 сможет поставлять на 10 машин сырья меньше, чем собирался. Каким будет тогда план перевозок? Какой завод недополучит продукцию?

Построение математической модели

На основании исходных таблиц составим транспортную таблицу (табл. 4).

Табл. 4

Max отгрузка маш/нед.	Недельные потребности завода
	Завод 1	Завод 2	Завод 3	Завод 4
	50	30	45	40
	Стоимости перевозки ед груза
Поставщик 1	50	1600	1400	1100	1250
Поставщик 2	55	1300	1350	1500	1200
Поставщик 3	60	1000	1250	900	1400



Для наглядности и простоты вычислений «вручную», стоимости перевозок, представленные в залитых цветом клетках таблицы, уменьшим в 100 раз, таким образом, они будут иметь единицу измерения, равную 100 у.е. (табл. 4-а).

Табл. 4-а

Max отгрузка маш/нед.	Недельные потребности завода
	Завод 1	Завод 2	Завод 3	Завод 4
	50	30	45	40
	Стоимости перевозки ед груза
Поставщик 1	50	16	14	11	12,5
Поставщик 2	55	13	13,5	15	12
Поставщик 3	60	10	12,5	9	14

Пусть x_ij- количество продукции, отправляемой от поставщика i к клиенту j, i=, j=, а c_ij - стоимость перевозки единицы груза (x_ij?0, c_ij?0),

Тогда общая стоимость перевозки равна

Z=* (1)

Z=16*x₁₁+14*x₁₂+11x₁₃+12,5x₁₄+13x+13x₂₁+13,5x₂₂+15x₂

В силу ограничений на возможность поставок продукции со склада и спрос на него клиентов должны выполняться следующие условия (ограничения) (2):

· на количество продукции, которое нужно вывести с каждого склада:

x₁₁+ x₁₂+ x₁₃+ x₁₄=50

x₂₁+ x₂₂+ x₂₃+ x₂₄=55

x₃₁+ x₃₂+ x₃₃+ x₃₄=60

· на количество продукции, которое надо доставить клиентам (заводам):

x₁₁+ x₂₁+ x₃₁=50

x₁₂+ x₂₂+ x₃₂=30

x₁₃+ x₂₃+ x₃₃=45

x₁₄+ x₂₄+ x₃₄=40

Суммарное количество продукции на складах:

Cуммарное количество продукции, заказанное клиентами (заводами):

Так как имеет место равенство:

Транспортная задача является закрытой (с балансом).

Решим задачу методом наименьшего элемента:

Задача формулируется следующим образом: определить такие неотрицательные значения переменных , i=1,m, j=1,n, которые удовлетворяют ограничениям (2) и обращают в минимум целевую функцию (1).

Решение задачи

Решение транспортной задачи состоит из двух этапов:

1. Определение допустимого решения (базисного решения).

2. Определение оптимального решения путем последовательного улучшения допустимого решения методом потенциалов.



Определение допустимого решения методом наименьшей стоимости

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

Определим клетку таблицы (табл. 5), которой соответствует наименьшая стоимость перевозки. Такая клетка одна: =9, поэтому, выбрав её, запишем:

=min()=min(60,45)=45

Рассуждаем так: в S₃ имеется 60 единиц товара, в К₃ требуется 45. Организуем перевозку из S₃ в К₃, т.е. запишем в клетку значение х₃₃ = 45 (табл. 6). В S₂ осталось 60-45 = 15 ед. товара, спрос К₃ полностью удовлетворен. Остатки по строке и столбцу запишем в соответствующие клетки столбца и строки остатков: в S2 - 35, а в К₂ -- О.Так как в столбце К₂ остаток равен нулю, этот столбец закрывается и далее не рассматривается (табл. 6).

Табл. 5

Остатки	Ki
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
	S3 = 60	10	12,5	9	14

Табл. 6

Остатки	Ki			0
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
15	S3 = 60	10	12,5	9,45	14

В табл. 6 ищем клетку, в которой записана наименьшая стоимость перевозки (за исключением клеток закрытого столбца К₂). Это клетка С₁₁. В нее запишем значение Х₁₁ = min (15, 50) = 15. Определим остатки для строки S₃ и столбца К₁. Остаток по строке S₃ равен 15-15 = 0, остаток по столбцу К₁ 50-15 = 35

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

Табл. 7

Остатки	Ki	35		0
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
0	S3 = 60	10,15	12,5	9,45	14

Среди оставшихся клеток, не принадлежащих закрытой строке или закрытому столбцу (см. табл. 7), наименьшую стоимость перевозки имеет клетка С₂₄. Запишем в нее значение Х₁₄ = min (50,40) = 40. Остаток для строки S₂ =55-40=15, а для столбца К₄ = 40-40 = 0. Запишем их в соответствующие клетки. Четвертый столбец становится закрытым (табл. 8).

Табл. 8

Остатки	Ki	35		0	0
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
15	S2 = 55	13	13,5	15	12, 40
0	S3 = 60	10,15	12,5	9,45	14

Из оставшихся незакрытых клеток (табл. 8) С₂₁=13- клетка с наименьшей стоимостью перевозки, следовательно, в клетку соответствующую С₂₁ записывается значение х₂₁ = min (15,35) = 15. В клетки S₂ и К₄ записываются остатки: остаток во второй строке - (15-15 = 0), в первом столбце - (35-15=20). Вторая строчка становится закрытой (табл. 9).

Табл. 9

Остатки	Ki	20		0	0
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
0	S2 = 55	13,15	13,5	15	12,40
0	S3 = 60	10,15	12,5	9,45	14

Незакрытыми остаются первая строка и первый со вторым столбцом (см. табл. 9). Остаются ячейки ячейка С₁₂=14 и С₁₁=16. В клетки, соответствующие С₁₂ и С₁₁, записываются значения х₁₂ = min (50,30) = 30 и х₁₁ = min (20,20) = 20 соответственно. В клетки с остатками S₁ , К₂ и К₁ записываются остатки: остаток во второй строке - (50-30-20 = 0), во втором столбце - (30-30 = 0), в первом столбце - (20-20 = 0). (Первый столбец, второй столбец и первая строка закрываются) (табл. 10).

Табл. 10

Остатки	Ki	0	0	0	0
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
0	S1= 50	16,20	14,30	11	12,5
0	S2 = 55	13,15	13,5	15	12,40
0	S3 = 60	10,15	12,5,	9,45	14

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

Z= 20*16 + 30*14 + 15*13 + 40*12 + 15*10 + 45*9 = 1970.

Последовательное улучшение допустимого решения методом потенциалов

Выберем вспомогательные коэффициенты U_i и V_j (i=, j=), обращающие в нули коэффициенты при базисных переменных, то есть

С_ij- U_i- V_j=0

Такие переменные называются потенциалами. Введем в табл. 10 для записи потенциалов вспомогательную строку и столбец (табл. 11).

Метод потенциалов заключается в выполнении следующих шагов:

1. Для всех Ху > 0 (т.е. всех занятых клеток) составляются потенциальные уравнения по формуле (16). Для определения т + п потенциалов необходимо, чтобы было т + п - 1 уравнений (где т - число строк, п - число столбцов). Тогда одному из потенциалов можно присвоить значение, равное нулю, а значения других потенциалов получить, решая систему уравнений (17). Для данной задачи т + п -1 = 6, и число занятых клеток равно 6 (см. табл. 10). Следовательно, решение невырожденное.

Табл.11

	Заводы
Поставщики	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16,20	14,30	11	12,5	U1 =
S2 = 55	13,15	13,5	15	12,40	U2 =
S3 = 60	10,15	12,5	9,45	14	U3 =
Vi	V1 =	V2 =	V3 =	V4 =

Составим потенциальные уравнения для заполненных клеток (3):

С11-U1-V1=0	16-U1-V1=0
С21-U2-V1=0	13-U2-V1=0
С31-U3-V1=0	10-U3-V1=0
С12-U1-V2=0	14-U1-V2=0
С33-U3-V3=0	9-U3-V3=0
С24-U2-V4=0	12-U2-V4=0

2. Решим систему уравнений (3), присвоив значение, равное нулю, наиболее часто встречающемуся неизвестному потенциалу: U₂ = 0, тогда

U₁ = 3

V₁ = 13

U₂ = 0

V₂ = 11

U₃ = -3

V₃ = 12

V₄ = 12

Данные потенциалы занесем в столбцы Ui и Vj табл. 12.

Табл. 12

	Заводы
Поставщики	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16,20	14,30	11	12,5	U1 =3
S2 = 55	13,15	13,5	15	12,40	U2 =0
S3 = 60	10,15	12,5	9,45	14	U3 =-3
Vj	V1 =13	V2 =11	V3 =12	V4 =12

3. Для всех небазисных переменных, т.е. для = 0 (для пустых клеток), определим невязки:

G_ij = C_ij - S_ij, где S_ij = U_i + V_j

(C_ij - стоимость перевозки единицы товара, S_ij-- косвенная стоимость). Получим (4)

G22=С22-U2-V2	G22=13,5-0+11=2,5
G32=С32-U3-V2	G32=12,5+3-11=4,5
G13=С13-U1-V3	G13=11-3-12=-4
G23=С23-U2-V3	G23=15-0-12=3
G14=С14-U1-V4	G14=12,5-3-12=-2,5
G34=С34-U3-V4	G34=14+3-12=5

Так как имеются отрицательные невязки: G₁₃= -4 и G₁₄ = -2,5, найденный план не оптимален.

4. Найдем новое базисное решение (табл. 13).

Табл. 13

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16 (-),20	14,30	11 (+)	12,5	U1 =3
S2 = 55	13,15	13,5	15	12,40	U2 =0
S3 = 60	10 (+),15	12,5	9 (-),45	14	U3 =-3
Vj	V1 =13	V2 =11	V3 =12	V4 =12

Для этого введем переменную Хij (назначим перевозку) в ту клетку табл. 13, которой соответствует отрицательная невязка, например, в клетку (1,3). Отметим ее знаком (+) (см. табл. 15). Знак (+) означает, что в эту клетку следует ввести перевозку. Вводя новую переменную (перевозку), в какую-нибудь клетку, необходимо изменить значения других переменных по меньшей мере в трех заполненных клетках, чтобы не нарушились итоговые значения в строках Si и столбцах Kj. Для этого построим четырехугольник (или многоугольник) вершинами которого будут отмеченные знаками клетки, причем отрезки, соединяющие их, должны располагаться по вертикали или горизонтали. Например, если в клетку (1,3) поставили (+), то в клетку (1,1) надо поставить (-), в клетку (3,1) - (+), в клетку (3,3) - (-). В пустые клетки знак (-) ставить нельзя. В свободную клетку должно быть перенесено меньшее из чисел, (обозначающих перевозку), стоящих в клетках со знаком (-). Значения перевозок в остальных, отмеченных знаками клетках, должны быть изменены на это же число: если в клетке стоит знак (+) - увеличены, если стоит знак (-) - уменьшены.

В табл. 13 числа, находящиеся в клетках со знаком (-), равны = 20 и = 45, min (20,45) = 20, поэтому во всех клетках, помеченных знаком (+), значения перевозок увеличим на 20, а во всех клетках, помеченных знаком (-) - уменьшим на 20. В результате = 0 и исключается из базиса, = 25 и оно остается в базиса. Получим план перевозок, представленный в табл. 14, для которого значение целевой функции равно:

Z =15*13 + 35*10 + 30*14 + 20*11 + 25*9 + 40*12 = 1890 тыс. у.е.

Табл.14

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14,30	11,20	12,5
S2 = 55	13,15	13,5	15	12,40
S3 = 60	10,35	12,5	9,25	14

Перейдем к повторению выполнения действий, описанных в пунктах 1- 4.

1. Для всех x_ij >0 (т.е. для всех занятых клеток) составим потенциальные уравнения. Как уже говорилось, должно быть т + п -1 = 6. (табл. 15).

Табл. 15

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16	14,30	11,20	12,5	U1 =-1
S2 = 55	13,15	13,5	15	12,40	U2 =0
S3 = 60	10 35	12,5	9,25	14	U3 =-3
Vj	V1 =13	V2 =15	V3 =12	V4 =12



Получим потенциальные уравнения (5):

С21-U2-V1=0	13-U2-V1=0
С31-U3-V1=0	10-U3-V1=0
С12-U1-V2=0	14-U1-V2=0
С13-U1-V3=0	11-U1-V3=0
С33-U3-V3=0	9-U3-V3=0
С24-U2-V4=0	12-U2-V4=0

2. Решим систему уравнений (5), присвоив значение, равное нулю, потенциалу U₂. Если U₂ = 0, тогда:

U₁ = -1

V₁ = 13

U₂ = 0

V₂ = 15

U₃ = 3

V₃ = 12

V₄ = 12

Занесем их в столбцы U_i и V_j табл. 15.

3. Для всех небазисных переменных, т.е. для которых x_ij = 0, определим невязки:

G_ij = C_ij - S_ij, где S_ij = U_i + V_j (6)

G11=C11-U1-V1	G11=16+1-13=4
G22=C22-U2-V2	G22=13,5-0-15=-1,5
G32=C32-U3-V2	G32=12,5+3-15=0,5
G23=C23-U2-V3	G23=15-0-15=3
G14=C14-U1-V4	G14=12,5+1-12=1,5
G34=C34-U3-V4	G34=14+3-12=5

Имеем одну отрицательную невязки G₂₂ = -1,5, поэтому найденный план не оптимален.

4. Найдем новое базисное решение.

Клетку (2,2), которая соответствует отрицательная невязка, равная -1,5, отметим знаком (+) (табл. 16). Одновременно установим равновесие по всему многоугольнику: если в клетку (2,2) поставили (+), то в клетку (2,1) поставим (-), если в клетку (3,1) - (+), в клетку (3,3) - (-), если в клетку (1,3) - (+), в клетку (1,2) - (-).

Табл. 16

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14 (-),30	11 (+),20	12,5
S2 = 55	13 (-),15	13,5 (+)	15	12,40
S3 = 60	10 (+),35	12,5	9 (-),25	14

Наименьшим из чисел, находящихся в клетках со знаком (-), является содержимое клетки (2,1), где Х₂₁ = 15, поэтому во всех клетках, помеченных знаком (+), надо увеличить перевозки на 15, а во всех клеток, помеченных знаком (-) уменьшить перевозки на 15 (табл. 17). Переменная Х₂₁ становится равной нулю, т.е. выводится из базиса.

Табл. 17

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14,15	11,35	12,5
S2 = 55	13	13,5,15	15	12,40
S3 = 60	10,50	12,5	9,10	14

Получим план перевозок (см. табл. 17), при котором значение целевой функции равно:

Z= 50*10 + 15*14 + 15*13.5 + 35*11 + 10*9 + 40*12 = 1867, 5 тыс.у.е.

Повторим действия, описанные в пунктах 1- 4.

1. Для всех xij > 0 (см. табл. 17) составим потенциальные уравнения: (7)

10-U3-V1=0
14-U1-V2=0
13,5-U2-V2=0
11-U1-V3=0
9-U3-V3=0
12-U2-V4=0

2. Определим неизвестные потенциалы (7), присвоив значение, равное нулю, например, наиболее часто встречающемуся неизвестному индексу: U₂ = 0, тогда

U₁ = 0,5

V₁ = 11,5

U₂ = 0

V₂ = 13,5

U₃ = -1,5

V₃ = 10,5

V₄ = 12

Занесем вычисленные потенциалы в табл. 18

Табл. 18

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16	14,15	11,35	12,5	U1 =0,5
S2 = 55	13	13,5,15	15	12,40	U2 =0
S3 = 60	10,50	12,5	9,10	14	U3 =-1,5
Vj	V1 =11,5	V2 =13,5	V3 =10,5	V4 =12

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

G11=16-0,5-11,5=4
G21=13-0-11,5=1,5
G32=12,5+1,5+-13,5=0,5
G23=15-0-10,5=4,5
G14=12,5-0,5-12=0
G34=14+1,5-12=3,5

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

Таким образом, минимальная стоимость перевозок (с учетом принятой единицы измерения, равной 100 у.е.) Z=186 750 у.е. и достигается она при значениях перевозок:

, , , , ,

Решение задачи в Еxcel

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



Рис. 1

Рис. 1-а

Для работы в диалоговом окне Поиск решения следует выполнить:

1. Команду: Сервис - Поиск решения. На экране появится диалоговое окно Поиск решения.

2. В поле Установить целевую ячейку ввести адрес $В$16.

3. Выбрать направление изменения целевой функции: установить переключатель в положение Минимальному значению.

4. В поле Изменяя ячейки ввести адрес блока ячеек SC$13: $F$15.

5. Для ввода ограничений нажать кнопку Добавить. В диалоговом окне Добавление ограничения ввести: в левое поле - левую часть ограничения $В$13:$В$15, из раскрывающегося списка выбрать знак ограничения =, в правое поле - правую часть ограничения $В$6:$В$8; щелкнуть по кнопке Добавить; в диалоговое окно Добавление ограничения аналогично ввести второе ограничение $C$12:$F$12 = $C$4:$F$4; нажать кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями (рис. 2).

Рис. 2

6. Щелкнуть по кнопке Параметры. Появится диалоговое окно

Рис. 3

7. Оставить, предлагаемые по умолчанию, Максимальное время решения задачи (100 с) и Предельное число итераций (100).

8. Установить флажки Линейная модель и Неотрицательные значения.

9. Нажать кнопку ОК. Появится диалоговое окно Поиск решения.

10. Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты поиска решения. Решение найдено.

11. В окне Результаты поиска решения в поле Тип отчета выделите названия всех трех отчетов: Результаты, Устойчивость, Пределы Появятся три новых листа с именами всех отчетов.

12. Нажать кнопку ОК. На экране появится исходная таблица (рис. 3), где в блоке ячеек C13:F15 находятся значения искомых переменных: Ху, а в ячейке В16 минимальное значение целевой функции.

Рис. 4

Таким образом, минимальная стоимость перевозок равна Z =186 750 и достигается при объемах перевозок:

, , , , ,

Как видно, вычисления, выполненные при ручном счете и средствами Excel, совпадают.

Определение разницы между наилучшим и наихудшим планами перевозок

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

Чтобы определить, насколько полученный при оптимизации план лучше, чем другие возможные планы, надо найти план, приносящий максимум издержек. Для этого следует запустить Поиск решения еще раз и поменять цель поиска на максимум - выбрать направление изменения целевой функции: установить переключатель в положение Максимальному значению (рис. 5). Получим решение (рис. 6)

Рис.5

Рис. 6

В полученном решении суммарная стоимость перевозок возрастет на 55 250 (у.е.). Таким образом, наихудший план отличается от наилучшего на 29,6%.

Ответы на вопросы

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

б)Определить, каким будет план перевозок, если Поставщик 4 сможет поставлять на 5 машин продукции больше, чем планировал.

Вычислим:

суммарное количество продукции на складах: (4)

суммарное количество продукции, заказанное клиентами:

Тогда (5)

И транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.

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



Рис. 7

Затем решим задачу, используя Поиск решения (рис. 8).

Рис. 8

Решение задачи изменилось: минимальная стоимость перевозок стала равной 179 750 (у.е.)

в) Определить, каким будет план перевозок, если Поставщик 4 не сможет поставлять на 5 машин продукции больше, чем планировал, а Поставщик 1 сможет поставлять на 10 машин меньше.

Вычислим:

суммарное количество продукции на складах:

суммарное количество продукции, заказанное клиентами:

Тогда

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

Так как , в таблицу транспортных издержек и в таблицу

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

Рис. 9



Рис.10

Решение задачи изменилось: минимальная стоимость перевозок в этом случае будет равной 209 500 (у.е.), а перевозка от фиктивного поставщика х₄₂ = 10. Недополучит 10 машин продукции Завод 2.

2. Задача №2 (Вариант 12)

Условие задачи

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

Расстояния от базы до каждого магазина и между магазинами приводятся в таб. 1:

Табл. 1

	база	Т2	Т3	Т4	Т5	Т6
база	-	15	3	27	9	11
Т2	15	-	10	12	21	14
Т3	3	10	-	15	18	14
Т4	27	12	15	-	24	20
Т5	9	21	18	21	-	26
Т6	11	14	14	20	26	-

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

Построение математической модели

Сеть дорог, связывающих базу с магазинами области можно представить в виде неориентированного графа, вершинам которого поставлены в соответствие название базы и магазинов, ребрам - связывающие их дороги, и каждому ребру поставлен в соответствие вес - длина дороги. Для удобства обозначим название базы через х₁, а торговые точки через х₂, х₃, х₃, х₅. Расстояния от вершины Х₁ до всех остальных и между вершинами представим в виде матрицы весов неориентированного графа (табл. 2). Для наглядности в матрице весов знаки оо (показывающие отсутствие дороги) опустим. Тогда задача сводится к нахождению кратчайших путей от вершины X₁ до всех остальных. Для ее решения используем метод Дейкстры.

Табл. 2

	х1	х2	х3	х4	х5	х6
х1	-	15	3	27	9	11
х2	15	-	10	12	21	14
х3	3	10	-	15	18	14
х4	27	12	15	-	24	20
х5	9	21	18	24	-	26
х6	11	14	14	20	26	-

Решение задачи

Построение графа

Построим граф (рис. 1), соответствующий матрице смежности (табл. 2).



Рис.1

Определение кратчайших расстояний от вершины х₁ до всех остальных

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

Табл. 3

	0	1	2	3	4	5
Х1	0*
Х2	?
Х3	?
Х4	?
Х5	?
Х6	?

Предварительно всем вершинам графа, кроме вершины х1, присвоим временные метки, равные бесконечности: L(х₂) = L(х_з) = L(х₄) = L(х₅) =L(x₆) =?, а вершине х₁ присвоим постоянную метку L*(х₁) = О. Занесем метки в нулевой столбец табл. З.

Выполним последовательность следующих шагов:



Шаг 1

а) Определим множество вершин графа, смежных с вершиной х₁ (рис. 1, табл. 2):

S(x₁) = {x₂, x₃, x₄, x₅, x₆}

в) Для каждой вершины, принадлежащей множеству S (х₁), вычислим новые временные метки L(х_j), равные min{ L^сТ(х_j), L*(х₁) + R_1j,}, где L^сТ(х_j) -- старая временная метка вершины х_j, L *(х₁) = 0 -- постоянная метка вершины x₁, R_1j- вес ребра(x₁, x_j).

Вычисления выполним в табл. 3-а.

Табл. 3-а

(xj)	L*(x1)+R1j		min{(xj),(L*(x1)+R1j}
L(x2)=?	L*(x1)+R12=	0+15=15	min {,15}=15
L(x3)=?	L*(x1)+R13=	0+3=3	min {,3}=3
L(x4)=?	L*(x1)+R14=	0+27=27	min {,27}=27
L(x5)=?	L*(x1)+R15=	0+9=9	min {,9}=9
L(x6)=?	L*(x1)+R16=	0+11=11	min {,11}=11

Прим: L*(x₁)= 0

Вершинам х₂, х₃ х₄ , х_5, х₆ присвоим новые временные метки, вычисленные в табл.3а

L(x₂) ⁼ 15, L(x₃) =3, L(x₄)=27; L(x₅)=9, L(x₆)=11.

Занесем новые метки в первый столбец табл. 4.

с) Из всех имеющихся временных меток в столбце 1 (табл. 4) выберем наименьшую и сделаем ее постоянной для своей вершины: min{15,3,27,9,11}=3. Эта метка соответствует вершине х₃. Отметим ее звездочкой в столбце 1 L*(x₃)= 3.

Табл. 4

	0	1	2	3	4	5
х1	0*
х2	?	15
х3	?	3*
х4	?	27
х5	?	9
х6	?	11

Шаг 2

а) Определим множество вершин графа, смежных с вершиной х₃, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(х₃) = {х₂, х₄, х_5, x₆ } .

в) Для каждой вершины, принадлежащей множеству S(х₃), вычислим новые временные метки L(х,), равные min{( (х_j),L *(Х₂) + R_2J}, где( (х_j) - старая временная метка вершины х_j, L *(х₃) = 3 - постоянная метка вершины х₃ , R_3j - вес ребра (х₃, х_j) (см. табл. 4-а)

Табл. 4-а

(xj)	L*(x3)+R3j		min{(xj),(L*(x3)+R3j}
L(x2)=15	L*(x3)+R32=	3+10=13	min {15,13}=13
L(x4)=27	L*(x3)+R34=	3+15=18	min {27,18}=18
L(x5)=9	L*(x3)+R35=	3+18=21	min {9,21}=9
L(x6)=11	L*(x3)+R36=	3+14=17	min {11,17}=11

Прим: L*(x₃)= 3

Метки вершин х₅, х₆ остаются без изменения, т.е. L(x₅) = 9, L(x₆) =11. Занесем их во второй столбец (табл. 5).

с) Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13, 18,9,11} = 9. Эта метка соответствует вершине L(х₅) = 9. Отметим ее звездочкой.

Табл. 5

	0	1	2	3	4	5
х1	0*
х2	0	15	13
х3	0	3*
х4	0	27	18
х5	0	9	9*
х6	0	11	11

Шаг 3

а) Определим множество вершин графа, смежных с вершиной х₅, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(х₅) = {х_2, х_4, х₆}.

в) Для вершины х₅, принадлежащей множеству S(х₅), вычислим новую временную метку L(x₅), равную min{L^ст(х_j), L*(x₅) + R_5j } где L^cт(х₅) - старая временная метка вершины х₅, L*(х₅) = 9 - постоянная метка вершины х₂, R_5j - вес ребра (х₅, х_j) (см. табл. 5-а).

Табл. 5-а

(xj)	L*(x5)+R5j		min{(xj),(L*(x5)+R5j}
L(x2)=13	L*(x5)+R52=	9+21=30	min {13,30}=13
L(x4)=18	L*(x5)+R54=	9+24=33	min {18,33}=18
L(x6)=11	L*(x5)+R56=	9+26=35	min {11,35}=11

Прим: L(x₅)= 9

Метки вершин х₂,х_4, х₆ остаются без изменения, т.е. L(x₂) = 13, L(x₄) = 18, L(x₆)=11. Занесем их во второй столбец (табл. 6).

с) Из всех имеющихся временных меток в третьем столбце табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13,18, 11} = 11. Эта метка соответствует вершине х₆: L* (х₆) = 11. Отметим ее звездочкой.

Табл. 6

	0	1	2	3	4	5
х1	0*
х2	0	15	13	13
х3	0	3*
х4	0	27	18	18
х5	0	9	9*
х6	0	11	11	11*

Шаг 4

а) Определим множество вершин графа, смежных с вершиной x₆, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(x₆) = {x_2, x₄}

в)Для вершины Х₆, принадлежащей множеству S(х₆), вычислим новую временную метку L(x₆), равную min{X^CT(x_j), L*(x₆) + R_6j}, где L^CT(x₆) - старая временная метка вершины x₆, L*(х₆) = 11 - постоянная метка вершины Х₆, R_6j - вес ребра (х₆, х_j)

Табл. 6-а

(xj)	L*(x6)+R6j		min{(xj),(L*(x6)+R6j}
L(x2)=13	L*(x6)+R62=	11+14=25	min {13,25}=13
L(x4)=18	L*(x6)+R64=	11+20=31	min {18,31}=18

Прим: L(x₆) = 11

Метки вершин х₂,х_4, остаются без изменения, т.е. L(x₂) = 13, L(x₄) = 18. Занесем их во второй столбец (табл. 7).

с) Из всех имеющихся временных меток в четвертом столбце табл. 7 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13,18} = 13. Эта метка соответствует вершине х₂: L* (х₂) = 13. Отметим ее звездочкой.

Табл. 7

	0	1	2	3	4	5
х1	0*
х2	0	15	13	13	13*
х3	0	3*
х4	0	27	18	18	18
х5	0	9	9*
х6	0	11	11	11*

Шаг 5

а) Определим множество вершин графа, смежных с вершиной Х₂, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(x₂) = {x₄}.

в)Для вершины Х₂, принадлежащей множеству S(х₂), вычислим новую временную метку L(x₂), равную min{X^CT(x₂), L*(x₂) + R₂₄}, где L^CT(x₂) - старая временная метка вершины x₂, L*(х₂) = 13 - постоянная метка вершины x₂,

Табл. 7-а

(xj)	L*(x2)+R24		min{(xj),(L*(x2)+R24}
L(x4)=18	L*(x2)+R24=	13+12=25	min {18,25}=18

Прим: L(x₂) = 13

Вершине x₄ присвоим новую временную метку, т.е. L(x₄) = 18. Занесем ее в четвертый столбец (табл. 8).

Табл.8

	0	1	2	3	4	5
х1	0*
х2	0	15	13	13	13*
х3	0	3*
х4	0	27	18	18	18	18*
х5	0	9	9*
х6	0	11	11	11*

Процесс расстановки меток закончен. Значения их дают кратчайшие расстояния от исходной вершины Х₁ до всех остальных:

L(x₂) = 13, L(x₃) = 3, L(х₄) = 18, L(x₅) = 9, L(x₆)=11.

На рисунке 2 в квадратных скобках укажем найденные кратчайшие расстояния от вершины X₁ до всех остальных, т.е. взвесим вершины исходного графа.

Рис.2

Определение кратчайших путей

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

L*(xj) = L*(xi) + R_ij

где вершина X_i предшествует вершине X_j.

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

Вершина х₄ имеет пять смежных вершин х₁,х₂ х₃, х_5, х₆: S(х₁,х₂,х₃,х_5,х₆) . Определим, какая из этих вершин удовлетворяет соотношению (1)

L*(x₄) = 18

L*(x₁) = 0 R₁₄ = 27L*(x₄) ? L*(x₁) + R₁₄ = 0+27=27

L*(x₂) = 13 R₂₄ = 12L*(x₄) ? L*(x₂) + R₂₄ = 13+12=25

L*(x₃) = 3 R₃₄ = 15L*(x₄) = L*(x₃) + R₃₄ = 3+15=18

L*(x₅) = 18 R₅₄ = 24L*(x₄) ? L*(x₅) + R₅₄=18+24=42

L*(x₆) = 11 R₆₄ = 20L*(x₄) ? L*(x₆) + R₆₄=11+20=31

Как видно, только вершина х₃ удовлетворяет соотношению (1). Следовательно, в кратчайшем пути вершине х₄ предшествует вершина х₃ (Рис. 2). Выделим на графе ребро (х₃, х₄)

Рис.3

b) Определим, какая вершина предшествует вершине х₃ в кратчайшем пути. Вершина х₃ имеет четыре смежные вершины:х₁, х₂, х_5, х₆ (вершина х₄ уже вошла в искомый путь и поэтому не рассматривается): S(х₁, х_2, х₅, х₆). Определим, какая из этих вершин удовлетворяет соотношению (2).