Задача №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 |
Пусть xIj- количество продукции, отправляемой от поставщика i к клиенту j, i=, j=, а cIj - стоимость перевозки единицы груза (xIj?0, cIj?0),
Тогда общая стоимость перевозки равна
Z=* (1)
Z=16*x11+14*x12+11x13+12,5x14+13x+13x21+13,5x22+15x2
В силу ограничений на возможность поставок продукции со склада и спрос на него клиентов должны выполняться следующие условия (ограничения) (2):
- на количество продукции, которое нужно вывести с каждого склада:
X11+ x12+ x13+ x14=50
X21+ x22+ x23+ x24=55
X31+ x32+ x33+ x34=60
- на количество продукции, которое надо доставить клиентам (заводам):
X11+ x21+ x31=50
X12+ x22+ x32=30
X13+ x23+ x33=45
X14+ x24+ x34=40
Суммарное количество продукции на складах:
Cуммарное количество продукции, заказанное клиентами (заводами):
Так как имеет место равенство:
Транспортная задача является Закрытой (с балансом).
Решим задачу методом наименьшего элемента:
Задача формулируется следующим образом: определить такие неотрицательные значения переменных, i=1,m, j=1,n, которые удовлетворяют ограничениям (2) и обращают в минимум целевую функцию (1).
Решение задачи
Решение транспортной задачи состоит из двух этапов:
- 1. Определение допустимого решения (базисного решения). 2. Определение оптимального решения путем последовательного улучшения допустимого решения методом потенциалов.
Определение допустимого решения методом наименьшей стоимости
На основе транспортной таблицы (табл. 4) построим вспомогательную таблицу (табл. 5), в верхнем правом углу каждой клетки которой будем записывать стоимости перевозки. Введем в таблицу вспомогательную строку и столбец для записи остатков.
Определим клетку таблицы (табл. 5), которой соответствует наименьшая стоимость перевозки. Такая клетка одна: =9, поэтому, выбрав ее, запишем:
=min()=min(60,45)=45
Рассуждаем так: в S3 имеется 60 единиц товара, в К3 требуется 45. Организуем перевозку из S3 в К3, т. е. запишем в клетку значение Х33 = 45 (табл. 6). В S2 осталось 60-45 = 15 ед. товара, спрос К3 полностью удовлетворен. Остатки по строке и столбцу запишем в соответствующие клетки столбца и строки остатков: в S2 - 35, а в К2 -- О. Так как в столбце К2 остаток равен нулю, этот столбец закрывается и далее не рассматривается (табл. 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 ищем клетку, в которой записана наименьшая стоимость перевозки (за исключением клеток закрытого столбца К2). Это клетка С11. В нее запишем значение Х11 = min (15, 50) = 15. Определим остатки для строки S3 и столбца К1. Остаток по строке S3 равен 15-15 = 0, остаток по столбцу К1 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), наименьшую стоимость перевозки имеет клетка С24. Запишем в нее значение Х14 = min (50,40) = 40. Остаток для строки S2 =55-40=15, а для столбца К4 = 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) С21=13- клетка с наименьшей стоимостью перевозки, следовательно, в клетку соответствующую С21 записывается значение Х21 = min (15,35) = 15. В клетки S2 и К4 записываются остатки: остаток во второй строке - (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). Остаются ячейки ячейка С12=14 и С11=16. В клетки, соответствующие С12 и С11, записываются значения Х12 = min (50,30) = 30 и Х11 = min (20,20) = 20 соответственно. В клетки с остатками S1 , К2 И К1 записываются остатки: остаток во второй строке - (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.
Последовательное улучшение допустимого решения методом потенциалов
Выберем вспомогательные коэффициенты UI И VJ (i=, j=), обращающие в нули коэффициенты при базисных переменных, то есть
СIj- UI- VJ=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), присвоив значение, равное нулю, наиболее часто встречающемуся неизвестному потенциалу: U2 = 0, тогда
U1 = 3
V1 = 13
U2 = 0
V2 = 11
U3 = -3
V3 = 12
V4 = 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 (для пустых клеток), определим невязки:
GIj = CIj - SIj, где SIj = UI + VJ
(CIj - стоимость перевозки единицы товара, SIj-- косвенная стоимость). Получим (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 |
Так как имеются отрицательные невязки: G13= -4 и G14 = -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. Для всех xij >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), присвоив значение, равное нулю, потенциалу U2. Если U2 = 0, тогда:
U1 = -1
V1 = 13
U2 = 0
V2 = 15
U3 = 3
V3 = 12
V4 = 12
Занесем их в столбцы UI и VJ табл. 15.
3. Для всех небазисных переменных, т. е. для которых xij = 0, определим невязки:
GIj = CIj - SIj, где SIj = UI + VJ (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 |
Имеем одну отрицательную невязки G22 = -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), где Х21 = 15, поэтому во всех клетках, помеченных знаком (+), надо увеличить перевозки на 15, а во всех клеток, помеченных знаком (-) уменьшить перевозки на 15 (табл. 17). Переменная Х21 становится равной нулю, т. е. выводится из базиса.
Табл. 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), присвоив значение, равное нулю, например, наиболее часто встречающемуся неизвестному индексу: U2 = 0, тогда
U1 = 0,5
V1 = 11,5
U2 = 0
V2 = 13,5
U3 = -1,5
V3 = 10,5
V4 = 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 (у. е.), а перевозка от фиктивного поставщика х42 = 10. Недополучит 10 Машин продукции Завод 2.
Похожие статьи
-
Постановка задачи - Экономико-математические методы
Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Экономико-математическая модель ТЗ - Экономико-математические методы
Рассмотрим ситуацию (3.1). Обозначим через количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю....
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Построение исходного опорного плана - Экономико-математические методы
Моделирование экономический математический опорный Построение опорных планов, а также их преобразование будем производить непосредственно в...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Введение - Экономико-математические методы и модели в логистике
Курсовая работа состоит в выполнении двух задач. Первая из них - транспортная задача, связанная с оптимизацией издержек при перевозках. По условию дана...
-
Модели и моделирование - Экономико-математические методы
Одним из основных методов научного познания является эксперимент, а самой распространенной его разновидностью - метод моделирования систем. В процессе...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Транспортная задача - Экономико-математические методы
Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...
-
Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее...
-
Общая постановка задачи исследования операций - Экономико-математические методы
Все факторы, входящие в описание операции, можно разделить на две группы: Постоянные факторы (условия проведения операции), на которые мы влиять не...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Постановка задачи применительно для КУП "СПЕЦКОММУНТРАНС": двум погрузчикам разной мощности, это автомобили ТО 28 и ТО 49, за 23 часа нужно погрузить на...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Элементы математических методов и моделей
Введение Основной целью данного курса является ознакомление студентов с основными математическими моделями и методами, используемых в процессах принятия...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Якщо в транспортній задачі не виконується така умова, тобто загальна кількість продукції постачальників не дорівнює загальному попиту всіх споживачів, то...
-
Пример решения задачи симплекс-методом, Условие задачи - Математические методы и модели в экономике
Рассмотрим алгоритм симплексного метода на примере решения задачи планирования товарооборота предприятия торговли. Требуется определить оптимальную...
-
Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы
Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Метод множителей Лагранжа - Экономико-математические методы
Среди задач (4.1)-(4.3) особое место занимают задачи типа (6.10) , (6.11) Для решения которых можно воспользоваться классическим методом оптимизации...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
Задача №1 (Вариант 12) - Экономико-математические методы и модели в логистике