16 Требуется перегнать автомобили с трех заводов в четыре торговых центра

16. Требуется перегнать автомобили с трех заводов в четыре торговых центра. Время, необходимое для перегонки каждого автомобиля, объемы поставок и размеры заказов приведены в таблице. Найти план перегонки автомобилей, минимизирующий суммарные расходы, если удельные затраты составляют 20 евро в час.
Заводы Торговые центры Объемы поставок
В1 В2 В3 В4 А1 7,1 8,2 6,5 10,0 80
А2 8,5 4,5 6,8 5,3 70
А3 9,2 6,4 8,4 9,5 50
Размеры заказов 30 55 45 20

Решение:

1. Составим математическую модель задачи.
Замечаем, что задача не сбалансирована: суммарные объемы поставок (200) превосходят суммарные размеры заказов (150), поэтому ограничения на объемы поставок с заводов будут иметь знак «≤», а ограничения на размеры заказов – знак «=».
Введем переменные задачи следующим образом:
Заводы Торговые центры
В1 В2 В3 В4
А1 x11
x12
x13
x14
А2 x21
x22
x23
x24
А3 x31
x32
x33
x34

Составляем ограничения по объему поставок с каждого из заводов:
— завод A1:
x11+x12+x13+x14≤80
— завод A2:
x21+x22+x23+x24≤70
— завод A3:
x31+x32+x33+x34≤50
Составляем ограничения на размеры заказов для каждого торгового центра:
— торговый центр В1:
x11+x21+x31=30
— торговый центр В2:
x12+x22+x32=55
— торговый центр В3:
x13+x23+x33=45
— торговый центр В4:
x14+x24+x34=20
Накладываем условия неотрицательности и целочисленности (число поставляемых автомобилей не может принимать отрицательные или дробные значения) на переменные задачи:
xij≥0,xij-целые (i=1..3, j=1..4)
И с учетом времени, необходимого для перегонки каждого автомобиля, и удельные затраты в размере 20 евро в час, получаем следующую задачу линейного программирования:
f=207,1×11+8,2×12+6,5×13+10×14+8,5×21+4,5×22+6,8×23+5,3×24+9,2×31+6,4×32+8,4×33+9,5×34→min

2. Решим полученную задачу средствами MS Excel.
Подготавливаем рабочий лист:
— ячейки B3:E5 резервируем для переменных задачи (объемы поставок автомобилей с заводов в торговые центры);
— в ячейках G3:G5 с помощью функции СУММ вычисляем суммарный объем поставок каждого из заводов;
— в ячейки I3:I5 вносим данные о максимально возможных объемах поставок для каждого завода;
— в ячейках B7:E7 с помощью функции СУММ вычисляем объем поставок в каждый торговый центр;
— в ячейки B9:E9 вносим данные о размерах заказов;
— ячейки B14:E16 вносим время, необходимое для перегонки каждого автомобиля;
— в ячейке E19 с помощью функции СУММПРОИЗВ вычисляем расходы на осуществление перегонов всех заказанных автомобилей в торговые центры.
Таким образом, рабочий лист приобретает вид:

В режиме отображения формул:

Вызываем надстройку Поиск решения и задаем параметры (условие целочисленности не устанавливаем для формирования отчетов по решению):

Нажимаем кнопку Найти решение и получаем сообщение об успешности поиска (выделяем отчеты для формирования дополнительной информации):

На рабочем листе получаем решение:

Т.е. для минимизации суммарных расходов на перегон автомобилей получаем следующую матрицу перевозок:
3004500500200500
Т.е. с завода А2 будут перегнаны все автомобили, на заводе А1 останется 5 автомобилей, а на заводе А3 останутся почти все, имеющиеся в наличии автомобили – только 5 из 50-ти имеющихся будут перегнаны в торговый центр В2.
И «стоимость» оптимального плана составит 17370 евро.

3. Расшифровка отчетов
3.1. Отчет по результатам
Microsoft Excel 16.0 Отчет о результатах

Лист: [Вариант16.xlsx]Лист1

Результат: Решение найдено. Все ограничения и условия оптимальности выполнены.
Модуль поиска решения

Модуль: Поиск решения лин. задач симплекс-методом

Время решения: 0,094 секунд.

Число итераций: 11 Число подзадач: 0

Параметры поиска решения

Максимальное время Без пределов, Число итераций Без пределов, Precision 0,000001, Использовать автоматическое масштабирование

Максимальное число подзадач Без пределов, Максимальное число целочисленных решений Без пределов, Целочисленное отклонение 1%, Считать неотрицательными
Ячейка целевой функции (Минимум)

Ячейка Имя Исходное значение Окончательное значение

$E$19 Суммарные затраты на перегон В4 0 17370

Ячейки переменных

Ячейка Имя Исходное значение Окончательное значение Целочисленное

$B$3 А1 В1 0 30 Продолжить

$C$3 А1 В2 0 0 Продолжить

$D$3 А1 В3 0 45 Продолжить

$E$3 А1 В4 0 0 Продолжить

Читайте также:  1 Метод Гаусса Меняем местами первую и вторую строки

$B$4 А2 В1 0 0 Продолжить

$C$4 А2 В2 0 50 Продолжить

$D$4 А2 В3 0 0 Продолжить

$E$4 А2 В4 0 20 Продолжить

$B$5 А3 В1 0 0 Продолжить

$C$5 А3 В2 0 5 Продолжить

$D$5 А3 В3 0 0 Продолжить

$E$5 А3 В4 0 0 Продолжить

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

Ячейка Имя Значение ячейки Формула Состояние Допуск

$B$7 Всего в ТЦ В1 30 $B$7=$B$9 Привязка 0

$C$7 Всего в ТЦ В2 55 $C$7=$C$9 Привязка 0

$D$7 Всего в ТЦ В3 45 $D$7=$D$9 Привязка 0

$E$7 Всего в ТЦ В4 20 $E$7=$E$9 Привязка 0

$G$3 А1 Всего с завода 75 $G$3<=$I$3 Без привязки 5

$G$4 А2 Всего с завода 70 $G$4<=$I$4 Привязка 0

$G$5 А3 Всего с завода 5 $G$5<=$I$5 Без привязки 45

$B$3 А1 В1 30 $B$3>=0 Без привязки 30

$C$3 А1 В2 0 $C$3>=0 Привязка 0

$D$3 А1 В3 45 $D$3>=0 Без привязки 45

$E$3 А1 В4 0 $E$3>=0 Привязка 0

$B$4 А2 В1 0 $B$4>=0 Привязка 0

$C$4 А2 В2 50 $C$4>=0 Без привязки 50

$D$4 А2 В3 0 $D$4>=0 Привязка 0

$E$4 А2 В4 20 $E$4>=0 Без привязки 20

$B$5 А3 В1 0 $B$5>=0 Привязка 0

$C$5 А3 В2 5 $C$5>=0 Без привязки 5

$D$5 А3 В3 0 $D$5>=0 Привязка 0

$E$5 А3 В4 0 $E$5>=0 Привязка 0

В третьей таблице отчета приводится список номеров и названий ячеек, в которых находятся левые части ограничений и их результирующие значения. В столбце «Формула» ограничения записаны через номера ячеек левых и правых частей ограничений. «Состояние» «Привязка» означает, что оптимальное решение задачи получается при выполнении строгого равенства в соответствующем ограничении.

3.2. Отчет по устойчивости
Microsoft Excel 16.0 Отчет об устойчивости

Ячейки переменных

Окончательное Приведенн. Целевая функция Допустимое Допустимое

Ячейка Имя Значение Стоимость Коэффициент Увеличение Уменьшение

$B$3 А1 В1 30 0 142 42 1E+30

$C$3 А1 В2 0 36 164 1E+30 36

$D$3 А1 В3 45 0 130 38 1E+30

$E$3 А1 В4 0 56 200 1E+30 56

$B$4 А2 В1 0 66 170 1E+30 66

$C$4 А2 В2 50 0 90 38 46

$D$4 А2 В3 0 44 136 1E+30 44

$E$4 А2 В4 20 0 106 46 1E+30

$B$5 А3 В1 0 42 184 1E+30 42

$C$5 А3 В2 5 0 128 36 38

$D$5 А3 В3 0 38 168 1E+30 38

$E$5 А3 В4 0 46 190 1E+30 46

В первой таблице отчета приведены номер и название ячеек, в которых находятся управляющие переменные, а также результирующие значения этих переменных. Наибольший интерес представляют значения, приведенные в столбце «Приведенная стоимость» для управляющих переменных, чьи окончательные значения равны нулю. Значения «Приведенной стоимости» показывают, на сколько изменится целевая функция при необходимости осуществить перегон одного автомобиля между соответствующими заводом и торговым центром (все ограничения при этом изменении должны по-прежнему выполняться).
Добавим в систему ограничений дополнительное ограничение x12≥5 (т.е. обяжем первый завод осуществить перегон 5 автомобилей в торговый центр В2) и снова запустим программу «Поиск решения»:
Получим следующий план перегонов:

Как видим, суммарные затраты выросли на 17550-17370=180, что соответствует приведенной стоимости, умноженной на количество автомобилей:
36*5=180
Продолжим анализировать отчет об устойчивости.
В столбце «Целевой коэффициент» приведены значения коэффициентов при управляющих переменных в целевой функции. Столбцы «Допустимое увеличение» и «Допустимое уменьшение» показывают, в каких пределах может изменяться целевой коэффициент, чтобы сохранялся оптимальный план. Например, для перегона автомобилей в направлении А3-В2, диапазон устойчивости (с учетом удельных затрат 20 евро в час): 6,4-3820≤c34≤6,4+3620, т.е. c34∈[4,5;8,2].
Увеличим коэффициент в пределах изменения, например, c34=8. Получим:

Как видим, структура оптимального плана не изменилась, а расходы увеличились на сумму, равную произведению разнице коэффициентов, количества перегоняемых автомобилей и удельных затрат:
17530-17370=160≡160=8-6,4*5*20
Теперь выйдем за пределы устойчивости, например, c34=9. Получим:

Читайте также:  Задания Определить изменение оптимального решения ДЛП при

В этом случае происходит изменение в структуре оптимального плана: теперь все заказы выполняются только за счет заводов А1 и А2 без привлечения завода А3.
Рассмотрим вторую таблицу отчета об устойчивости.
Ограничения

Окончательное Тень Ограничение Допустимое Допустимое

Ячейка Имя Значение Цена Правая сторона Увеличение Уменьшение

$B$7 Всего в ТЦ В1 30 142 30 5 30

$C$7 Всего в ТЦ В2 55 128 55 45 5

$D$7 Всего в ТЦ В3 45 130 45 5 45

$E$7 Всего в ТЦ В4 20 144 20 45 5

$G$3 А1 Всего с завода 75 0 80 1E+30 5

$G$4 А2 Всего с завода 70 -38 70 5 45

$G$5 А3 Всего с завода 5 0 50 1E+30 45

В ней приведены номер и название ячеек, в которых находятся полученные при решении значения левых частей ограничений, а также сами эти значения в столбце «Окончательное значение». В столбце «Тень цена» приводится значение, на которое изменится целевая функция при увеличении соответствующей правой части ограничения на одну единицу измерения. При этом остальные ограничения остаются неизменными. В столбце «Ограничение. Правая сторона» приведены значения правых частей ограничений. «Допустимое увеличение» и «Допустимое уменьшение» показывают, на сколько можно изменить правую часть ограничения, чтобы можно было использовать теневую цену для определения значения целевой функции.
Рассмотрим, например, объем заказа для торгового центра В2, для которого теневая цена составляет 128 ед, а допустимые пределы изменения 55-5≤b2≤55+45, т.е. b2∈[50;100]. Увеличим объем заказа в допустимых пределах, например, b2=85. Получим:

Изменение суммарных затрат составило 21210-17370=3840, что соответствует теневой цене и изменению объема заказа: 30*128=3840.
Теперь выйдем за пределы диапазона устойчивости, например, b2=45:

Как видим, в этом случае изменение прибыли уже нельзя объяснить только изменением ресурса времени: в данном случае происходит изменение теневых цен ресурсов:
Ограничения

Окончательное Тень Ограничение Допустимое Допустимое

Ячейка Имя Значение Цена Правая сторона Увеличение Уменьшение

$B$7 Всего в ТЦ В1 30 142 30 5 30

$C$7 Всего в ТЦ В2 45 90 45 5 45

$D$7 Всего в ТЦ В3 45 130 45 5 45

$E$7 Всего в ТЦ В4 20 106 20 5 20

$G$3 А1 Всего с завода 75 0 80 1E+30 5

$G$4 А2 Всего с завода 65 0 70 1E+30 5

$G$5 А3 Всего с завода 0 0 50 1E+30 50

3.3. Отчет по пределам
Microsoft Excel 16.0 Отчет о пределах

Лист: [Вариант16.xlsx]Лист1

Целевая функция

Ячейка Имя Значение

$E$19 Суммарные затраты на перегон В4 17370

Переменная

Нижний Целевая функция
Верхний Целевая функция

Ячейка Имя Значение
Предел Результат
Предел Результат

$B$3 А1 В1 30
30 17370
30 17370

$C$3 А1 В2 0
0 17370
0 17370

$D$3 А1 В3 45
45 17370
45 17370

$E$3 А1 В4 0
0 17370
0 17370

$B$4 А2 В1 0
0 17370
0 17370

$C$4 А2 В2 50
50 17370
50 17370

$D$4 А2 В3 0
0 17370
0 17370

$E$4 А2 В4 20
20 17370
20 17370

$B$5 А3 В1 0
0 17370
0 17370

$C$5 А3 В2 5
5 17370
5 17370

$D$5 А3 В3 0
0 17370
0 17370

$E$5 А3 В4 0
0 17370
0 17370
В первой и второй таблицах отчета приведены номер и название ячеек, в которых находятся целевая функция (первая таблица) и управляющие переменные (вторая таблица), а также их результирующие (оптимальные) значения. В столбцах «Нижний предел» и «Верхний предел» приведены такие минимальное и максимальное значения управляющей переменной, которые может принимать эта переменная при условии выполнения ограничений и сохранении остальными переменными полученных при решении оптимальных значений. В первом столбце «Целевая функция результат» приведено значение целевой функции при равенстве соответствующей управляющей переменной ее «Нижнему пределу». Во втором столбце «Целевая функция результат» приведено значение целевой функции при равенстве соответствующей управляющей переменной ее «Верхнему пределу».

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...