Транспортная задача Однородный груз сосредоточен у m поставщиков A1

Транспортная задача
Однородный груз сосредоточен у m поставщиков A1, A2, …, Am в объемаa1, a2, …, amх. Данный груз необходимо доставить n потребителям B1,B2,…,Bn в объемах a1, a2, …, an. Известны ciji=1,2,…,m;j=1,2,…,n стоимость перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором:
мощности всех поставщиков были реализованы;
спросы всех потребителей были удовлетворены;
суммарные затраты на перевозку были минимальны.
Исходные данные транспортной задачи записываются в виде таблицы
Пункты отправления Пункты назначения Запасы

B1
… Bj
… Bn

A1
c11
… c1j
… c1n
a1
… … … … … … …
Ai
ci1
… cij
… c1n
ai
… … … … … … …
Am
cm1
… cmj
… cmn
am
Потребности b1
… bj
… bn

Решение. Обозначим xiji=1,2,…,m;j=1,2,…,n объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Математическая постановка задачи состоит в определении минимального значения функции
Fx=i=1mj=1ncijxij→min
при условиях
j=1nxij=ai,i=1,2,…,m
i=1mxij=bj,j=1,2,…,n
xij≥0,i=1,2,…,m;j=1,2,…,n
Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.
i=1mai=j=1nbj,
то модель такой транспортной задачи называется закрытой, задачу при этом называют сбалансированной. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.
Условие задачи
Предприятие Агрохолдинг «Красный Восток» располагает четырьмя пунктами сбора сырого молока – Азнакаево, Елабуга, Заинск, Тетюши. Собранное молоко автомобильным изотермическим транспортом отправляется в молокозаводы московского региона Лианозово, Обнинск, Шатура, Бронницы, Волоколамск. Известны мощности поставщиков и переработчиков сырого молока, стоимость перевозки грузов на 1 км. Необходимо разработать такой план перевозок, чтобы все молоко было перевезено, а общая стоимость перевозок была минимальной.
Обозначим пункты сбора соответственно как A1, A2, A3, A4. Мощности поставщиков соответственно 30, 48, 20, 30 единиц. Пункты переработки обозначим соответственно как B1, B2, B3, B4, B5. Мощности переработчиков соответственно 18, 27, 42, 26, 15 единиц.
Стоимость перевозок задается таблицей

В1
В2
В3
В4
В5
А1
15 7 14 7 5
А2
11 9 12 6 8
А3
6 10 11 8 11
А4
14 8 10 10 14
Требуется составить такой план перевозок, чтобы все заявки были выполнены, а общая стоимость перевозок была минимальна.
Существуют следующие разновидности методов нахождения первого опорного плана – метод минимального элемента и метод северо-западного угла. Также есть два метода улучшения опорного плана – метод потенциалов и распределительный метод. Решим данную задачу двумя способами: 1) метод нахождения первого опорного плана – метод минимального элемента, метод улучшения опорного плана – метод потенциалов; 2) метод нахождения первого опорного плана – метод северо-западного угла, метод улучшения опорного плана – распределительный метод. Также решим данную задачу с помощью инструмента «Поиск решения» пакета прикладных программ Microsoft Excel.

Часть выполненной работы