Лабораторная работа №2
Цель работы – приобретение навыков построения математических моделей транспортных задач линейного программирования
В хозяйстве имеются пять складов минеральных удобрений и четыре пункта, куда их необходимо доставить. Потребность каждого пункта в минеральных удобрениях различна, и запасы на каждом складе ограничены. Требуется определить, с какого склада, в какой пункт поставлять, сколько минеральных удобрений для минимизации грузооборота перевозок.
Исходные данные.
Наличие минеральных удобрений на складах Таблица 7
Склады |
Наличие удобрений, т. |
Склад №1 |
200 |
Склад №2 |
190 |
Склад №3 |
220 |
Склад №4 |
145 |
Склад №5 |
280 |
Потребность в минеральных удобрениях Таблица 8
Пункты |
Потребность в удобрениях, т. |
1 пункт |
200 |
2 пункт |
150 |
3 пункт |
220 |
4 пункт |
330 |
Расстояния между складами и пунктами доставки Таблица 9
|
Пункт 1 |
Пункт 2 |
Пункт 3 |
Пункт 4 |
Склад №1 |
6 |
4 |
5 |
11 |
Склад №2 |
12 |
6 |
4 |
9 |
Склад №3 |
15 |
7 |
10 |
4 |
Склад №4 |
9 |
5 |
12 |
5 |
Склад №5 |
3 |
7 |
12 |
11 |
На пересечении столбца конкретного пункта доставки со строкой склада находится информация о расстояниях между этими пунктом доставки и складом. Например, расстояние между пунктом 3 и складом №3 равно 10 километрам.
Для решения задачи подготовим необходимые данные (рисунок 5)
Рисунок 5 - Изменяемые ячейки
Значения ячеек по столбцу В с четвертой по восьмую строку определяются суммированием данных ячеек соответствующих строк начиная со столбца С до столбца F .
Например, значение ячейки B4=СУММ(C4:F4)
Значения ячеек по 9 строке по столбцам от С до F определяются суммированием данных ячеек соответствующих столбцов с 4 по 8 строки.
Например, значение ячейки С9=СУММ(C4:C8)
Каждое значение в ячейках на пересечении столбца конкретного пункта доставки и строки склада означает количество тонн, поставляемых с этого склада в данный пункт потребления. В нижней строке (строка 9) суммируется общее количество минеральных удобрений, поставляемых в определенный пункт доставки, а во втором столбце (столбец В) суммируется количество доставленного с конкретного склада минеральных удобрений.
Используя исходные данные, введем на этом же листе требуемые объемы поставок и расстояния между складами и пунктами доставки (рисунок 6).
Рисунок
6 - Исходная информация
В строке 16 по столбцам C-F определим грузооборот по каждому пункту доставки. К примеру для 1 пункта (ячейка С16) это рассчитывается с помощью формулы:
С16=С4*С11+С5*С12+С6*С13+С7*С14+С8*С15,
либо можно использовать функцию СУММПРОИЗВ
С16=СУММПРОИЗВ(C4:C8;C11:C15)
В ячейке С4 находится количество минеральных удобрений, перевозимых со склада №1 в 1 пункт доставки, а в ячейке С11 - расстояние от склада №1 до 1 пункта доставки. Соответственно первое слагаемое в формуле означает полный грузооборот по данному маршруту. Вся же формула вычисляет полный грузооборот перевозок минеральных удобрений в 1 пункт доставки.
В ячейке В16
по формуле =СУММ(С16:F16)
будет вычисляться общий объем грузооборота
минеральных удобрений.Таким образом,
информация на рабочем листе примет
следующий вид (рисунок 7) 
Рисунок 7 - Рабочий лист для решения транспортной задачи
Для решения транспортной задачи воспользуемся процедурой Поиск решения, которая находится в меню Сервис.
После выбора данной команды появится диалоговое окно (рисунок 8).
Рисунок 8 - Диалоговое окно «Поиск решения»
Поскольку в качестве критерия оптимизации нами выбрана минимизация грузооборота, в поле «Установить целевую ячейку» введите ссылку на ячейку, содержащую формулу расчета общего объема грузооборота минеральных удобрений. В нашем случае это ячейка $B$16. Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;
В поле «Изменяя ячейки» введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($С$4:$F$8). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с С4 по F8, то есть будут изменяться количество груза, перевезенного по конкретному маршруту.
Если сейчас запустить процесс подбора параметров, то будет найден вариант, где все переменные равны нулю. И это правильно - если не перевозить ничего, то это самый дешевый вариант. Но нам необходимо перевезти минеральные удобрения, поэтому надо наложить некоторые ограничения для поиска решения.
В группе полей «Ограничения» нажмите кнопку «Добавить». Появится диалог «Добавление ограничения» (рисунок 9).
Рисунок 9 - Диалоговое окно «Добавление ограничения»
Следует ввести левую часть ограничения в левое поле, выбрать знак условия, накладываемого на значение и ввести правую часть ограничения. Как и в других случаях, можно не вводить ссылки на ячейки, а выделить мышью эти ячейки. После ввода одного ограничения следует нажать кнопку «Добавить» и ввести следующее. По окончании ввода всех ограничений нажмите на кнопку ОК. В диалоге появятся строки введенных ограничений (рисунок 10).
Рисунок 10 - Диалоговое окно «Поиск решения» с заполненными полями
Для изменения и удаления ограничений в списке «Ограничения» диалогового окна «Поиск решения» укажите ограничение, которое требуется изменить или удалить. Выберите команду «Изменить» и внесите изменения либо нажмите кнопку «Удалить».
Рассмотрим более подробно условия, которые следует наложить на значения в некоторых ячейках для правильного решения задачи.
Первое условие $B$4:$B$8 <=$B$11:$B$12. Оно означает, что значение в ячейке В4 должно быть меньше или равно значению в В11, в В5 меньше или равно, чем в В12, и так далее до В8 и В15.
В ячейках с В4 по В8 на листе находятся объемы поставок с конкретных складов. В ячейках с В11 по В15 - запасы на этих же складах. Так как невозможно вывести со склада больше, чем на нем есть, первое значение должно быть не больше второго.
Второе условие $С$4:$F$8>=0. Оно означает, что объем перевозок не может быть отрицательным, то есть, если на складе не хватает минеральных удобрений, их не везут с пункта доставки, на который эти минеральные удобрения были завезены ранее. Грузопоток имеет только одно направление - от складов к пунктам доставки удобрений.
И. наконец, третье, и последнее условие $С$9:$F$9>=$C$10:$F$10. Оно означает, что значения в ячейках девятой строки должны быть больше или равны значениям в ячейках десятой строки,, то есть запросы пунктов доставки минеральных удобрений должны быть выполнены полностью. Перевыполнение объема поставок допустимо, а недовыполнение - нет.
Введенные условия должны позволить найти наиболее оптимальный вариант решения задачи.. Нажмите кнопку «Выполнить» для подбора решения.
После нахождения решения появляется диалог «Результаты поиска решения» (рисунок 11)
Рисунок 11 - Диалоговое окно «Результаты поиска решения»
Нажав кнопку ОК, вы занесете решение на рабочий лист (рисунок 12)
Рисунок 12 - Решенная транспортная задача
Данные для решения задач
Потребителям Б1, Б2, Б3 и Б4 требуется песок в количествах соответственно б1, б2, б3 и б4 тонн. На складах имеется следующее количество песка: А1 = а1 т, А2 = а2 т и А3 = а3 т. Требуемое и имеющееся количество песка приведено в таблице 2.4. Расстояния между поставщиками и получателями песка приведены в таблице 2.5. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.
Требуемое и имеющееся количества песка Таблица 10
Номер варианта (предпоследняя цифра шифра) |
a1 |
а2 |
а3 |
б1 |
б2 |
б3 |
б4 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
0 |
90 |
60 |
50 |
40 |
70 |
50 |
40 |
1 |
110 |
70 |
60 |
50 |
80 |
60 |
50 |
2 |
120 |
90 |
70 |
60 |
90 |
70 |
60 |
3 |
130 |
100 |
90 |
70 |
100 |
80 |
70 |
4 |
150 |
110 |
100 |
80 |
110 |
90 |
80 |
Продолжение таблицы 10
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
5 |
160 |
120 |
120 |
90 |
120 |
100 |
90 |
6 |
170 |
140 |
130 |
100 |
130 |
110 |
100 |
7 |
190 |
150 |
140 |
110 |
140 |
120 |
110 |
8 |
200 |
160 |
160 |
120 |
150 |
130 |
120 |
9 |
210 |
180 |
170 |
130 |
160 |
140 |
130 |
Расстояние между поставщиками и потребителями Таблица 11
Последняя цифра шифра |
x11 |
X12 |
X13 |
X14 |
X21 |
X22 |
X23 |
X24 |
X31 |
X32 |
X33 |
X34 |
0 |
10 |
25 |
6 |
9 |
5 |
21 |
13 |
6 |
18 |
22 |
11 |
28 |
1 |
11 |
24 |
7 |
10 |
6 |
20 |
14 |
8 |
19 |
23 |
13 |
27 |
2 |
12 |
23 |
8 |
11 |
7 |
19 |
15 |
10 |
20 |
24 |
14 |
26 |
3 |
13 |
22 |
9 |
12 |
8 |
18 |
16 |
12 |
21 |
25 |
16 |
25 |
4 |
14 |
21 |
10 |
13 |
9 |
17 |
17 |
14 |
22 |
26 |
17 |
24 |
5 |
15 |
20 |
11 |
14 |
10 |
16 |
18 |
16 |
23 |
27 |
19 |
23 |
6 |
16 |
19 |
12 |
15 |
11 |
15 |
19 |
18 |
24 |
28 |
20 |
22 |
7 |
17 |
18 |
13 |
16 |
12 |
14 |
20 |
17 |
25 |
29 |
21 |
21 |
8 |
18 |
17 |
14 |
17 |
13 |
13 |
21 |
15 |
26 |
30 |
22 |
20 |
9 |
19 |
16 |
15 |
18 |
14 |
12 |
22 |
13 |
27 |
31 |
24 |
19 |