Транспортная задача линейного программирования
Семь угольных карьеров добывают уголь и поставляют его на пять электростанций. Потребности в угле по электростанциям распределены следующим образом: для электростанции М1 требуется 200 тыс. тонн угля в месяц, для М2 – 600, М3 – 800, М4 – 900 и для М5 – 1200 тысяч тонн угля в месяц. Качество угля, оптовые цены и транспортные издержки отражены в показателях прибыли, приведенных в табл. 1, расположенной ниже.
Таблица 1
Показатели прибыли электростанций
Электростанции Распределение прибыли по карьерам, долл./т
1 2 3 4 5 6 7
М1
М2
М3
М4
М5 8
9
6
5
4 3
11
10
12
7 2
5
6
11
10 7
2
4
8
9 4
6
7
10
8 5
3
5
13
5 9
4
8
7
6
Производственные мощности карьеров представлены в таблице 2, расположенной ниже.
Таблица 2
Распределение производственных мощностей по карьерам, тыс. тонн
Карьеры Вариант 9
1 600
2 450
3 450
4 300
5 350
6 650
7 700
Решение
Для определения плана оптимального поставки угля на пять электростанций от семи угольных карьеров, который обеспечивает минимальные суммарные затраты на перевозку, необходимо реализовать четыре этапа.
1) Проверка сбалансированности модели задачи.
a=600+450+450+300+350+650+700=3500 тыс. тонн
b=200+600+800+900+1200=3700 тыс. тонн
В данном случае суммарная потребность груза на электростанциях выше, чем производственные мощности карьеров. Следовательно, данная модель транспортной задачи является открытой. Для получения закрытой модели введем дополнительный (фиктивный) карьер, значение запаса которого будет составлять 200 тыс. тонн. Качество угля, оптовые цены и транспортные издержки данного карьера примем равные нулю. Таким образом, получим следующую распределительную таблицу данной транспортной задачи (таблица 2).
Таблица 2
Распределительная таблица транспортной задачи
600 450 450 300 350 650 700 200
200 8 3 2 7 4 5 9 0
600 9 11 5 2 6 3 4 0
800 6 10 6 4 7 5 8 0
900 5 12 11 8 10 13 7 0
1200 4 7 10 9 8 5 6 0
2) Построение математической модели.
Неизвестными переменными в этой задаче являются объемы перевозок.
Пусть:
- xij – объем перевозок от i-го карьера на j-ую электростанцию;
ai – объем угля у i-ого карьера;
- bj – спрос на j-й электростанции;
- cij –прибыль в результате транспортировки от i-го карьера на j-ую электостанцию.
В таком случае суммарная прибыль F (целевая функция) имеет вид:
F=8x11+3x12+2x13+7x14+4x15+5x16+9x17+0x18+9x21+11x22+5x23+2x24+6x25+3x26+4x27+0x28+6x31+10x32+6x33+4x34+7x35+5x36+8x37+0x38+5x41+12x42+11x43+8x44+10x45+13x46+7x47+0x48+4x51+7x52+10x53+9x54+8x55+5x56+6x57+0x58→max
Составим систему ограничений для этого примера. Чтобы потребность в угле каждой электростанции была удовлетворена, необходимо выполнение баланса по каждой строке таблицы, т.е.:
x11+x12+x13+x14+x15+x16+x17+x18=200
x21+x22+x23+x24+x25+x26+x27+x28=600
x31+x32+x33+x34+x35+x36+x37+x38=800
x41+x42+x43+x44+x45+x46+x47+x48=900
x51+x52+x53+x54+x55+x56+x57+x58=1200
Аналогично, чтобы производственные мощности каждого карьера были реализованы, подобные уравнения баланса выписываем для каждого столбца таблицы:
x11+x21+x31+x41+x51=600
x12+x22+x32+x42+x52=450
x13+x23+x33+x43+x53=450
x14+x24+x34+x44+x54=300
x15+x25+x35+x45+x55=350
x16+x26+x36+x46+x56=650
x17+x27+x37+x47+x57=700
x18+x28+x38+x48+x58=200
Необходимо отметить, что все переменные xij должны быть неотрицательными.
3) Поиск первого опорного плана.
Для нахождения первого опорного плана воспользуемся методом наибольшей стоимости, суть которого заключается в том, что из всей таблицы стоимостей выбирают наибольшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую потребителю, потребности которого полностью удовлетворены, либо столбец, соответствующий поставщику, запасы которого полностью израсходованы, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя
. Из оставшейся части таблицы стоимостей снова выбирают наибольшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Первый искомый элемент равен c46=13, потребности и запасы которого составляют соответственно 900 тыс. тонн и 650 тыс. тонн. Поскольку минимальным в данном случае является значение 650 тыс. тонн, вычитаем его.
x46 = min(900,650) = 650
Второй искомый элемент равен c42=12, потребности и запасы которого составляют соответственно 250 тыс. тонн и 450 тыс. тонн. Поскольку минимальным в данном случае является значение 250, вычитаем его.
x42 = min(250,450) = 250
Третий искомый элемент равен c22=11, потребности и запасы которого составляют соответственно 600 тыс. тонн и 200 тыс. тонн. Поскольку минимальным в данном случае является значение 200, вычитаем его.
x22 = min(600,200) = 200
Четвертый искомый элемент равен c53=10, потребности и запасы которого составляют соответственно 1200 тыс. тонн и 450 тыс. тонн. Поскольку минимальным в данном случае является значение 450, вычитаем его.
x53 = min(1200,450) = 450
Пятый искомый элемент равен c54=9, потребности и запасы которого составляют соответственно 750 тыс. тонн и 300 тыс. тонн. Поскольку минимальным в данном случае является значение 300, вычитаем его.
x54 = min(750,300) = 300
Шестой искомый элемент равен c21=9, потребности и запасы которого составляют соответственно 400 тыс. тонн и 600 тыс. тонн. Поскольку минимальным в данном случае является значение 400, вычитаем его.
x21 = min(400,600) = 400
Седьмой искомый элемент равен c17=9, потребности и запасы которого составляют соответственно 200 тыс. тонн и 700 тыс. тонн. Поскольку минимальным в данном случае является значение 200, вычитаем его.
x17 = min(200,700) = 200
Восьмой искомый элемент равен c55=8, потребности и запасы которого составляют соответственно 450 тыс. тонн и 350 тыс. тонн. Поскольку минимальным в данном случае является значение 350, вычитаем его.
x55 = min(450,350) = 350
Девятый искомый элемент равен c37=8, потребности и запасы которого составляют соответственно 800 тыс. тонн и 500 тыс. тонн. Поскольку минимальным в данном случае является значение 500, вычитаем его.
x37 = min(800,500) = 500
Десятый искомый элемент равен c31=6, потребности и запасы которого составляют соответственно 300 тыс. тонн и 200 тыс. тонн. Поскольку минимальным в данном случае является значение 200, вычитаем его.
x31 = min(300,200) = 200
Одиннадцатый искомый элемент равен c58=0, потребности и запасы которого составляют соответственно 100 тыс. тонн и 200 тыс. тонн. Поскольку минимальным в данном случае является значение 100, вычитаем его.
x58 = min(100,200) = 100
Двенадцатый искомый элемент равен c38=0, потребности и запасы которого составляют соответственно 100 тыс. тонн и 100 тыс. тонн. Поскольку минимальным в данном случае является значение 100, вычитаем его.
x38 = min(100,100) = 100
Расчет первого оптимального плана представлен в таблице 3, расположенной ниже.
Таблица 3
Расчет первого опорного плана
600 450 450 300 350 650 700 200 1 2 3 4 5 6 7 8 9 10 11 12
200
8
3
2
7
4
5
9
0 200 200 200 200 200 200 0 0 0 0 0 0
200
600
9
11
5
2
6
3
4
0 600 600 400 400 400 0 0 0 0 0 0 0
400
200
800
6
10
6
4
7
5
8
0 800 800 800 800 800 800 800 800 300 100 100 0
200
500 100
900
5
12
11
8
10
13
7
0 250 0 0 0 0 0 0 0 0 0 0 0
250
650
1200
4
7
10
9
8
5
6
0 1200 1200 1200 750 450 450 450 100 100 100 0 0
450
300
350
100
1 600 450 450 300 350 0 700 200
2 600 200 450 300 350 0 700 200
3 600 0 450 300 350 0 700 200
4 600 0 0 300 350 0 700 200
5 600 0 0 0 350 0 700 200
6 200 0 0 0 350 0 700 200
7 200 0 0 0 350 0 500 200
8 200 0 0 0 0 0 500 200
9 200 0 0 0 0 0 0 200
10 0 0 0 0 0 0 0 200
11 0 0 0 0 0 0 0 100
12 0 0 0 0 0 0 0 0
Таким образом получим следующий опорный план задачи (таблица 4).
Таблица 4
Опорный план транспортной задачи
600 450 450 300 350 650 700 200
200 8 3 2 7 4 5 9 0
200 600 9 11 5 2 6 3 4 0
400 200 800 6 10 6 4 7 5 8 0
200 500 100
900 5 12 11 8 10 13 7 0
250 650 1200 4 7 10 9 8 5 6 0
450 300 350 100
В результате получен опорный план, который является допустимым, так как весь уголь из карьеров вывезен, потребность электростанций удовлетворена, а план соответствует системе ограничений транспортной задачи
Задать вопрос
на новый заказ в Автор24.
