Транспортная задача-одна из распространенных задач линейного программирования. Её цель-разработка наиболее распространенных способов и путей транспортирования товаров.
Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей
Транспортная задача
Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.
Просмотр содержимого документа
«Транспортная задача»
Транспортная задача
Общая постановка задачи
Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспонирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
В общем виде транспортную задачу можно представить следующим образом: Некий продукт (например, сталь) вырабатывается на m заводах 
, причем ежемесячная выработка составляет 
соответственно. Пусть эту сталь нужно доставить на предприятия 
(всего k), причем 
- ежемесячная потребность этих предприятий. Наконец, пусть задана стоимость 
, перевозки одной тонны стали с завода 
на предприятие 
. Принято считать, что общее производство стали равно суммарной потребности в ней:
а1+а2+…+ат= b1+b2+…bk.
Требуется составить план перевозок, при котором:
1) была бы точно удовлетворена потребность в стали предприятий 
;
2) была бы вывезена вся сталь с заводов ;
3)общая стоимость перевозок была бы наименьшей.
Обозначим через 
количество стали (в тоннах), предназначенной к отправке с завода 
на предприятие 
. План перевозок состоит из 
неотрицательных чисел 
.
|
| в | в | в | … | в | Отправлено |
| из |
|
|
| … |
|
|
| из |
|
|
| … |
|
|
|
|
|
|
| … |
|
|
| из |
|
|
| … |
|
|
| Привезено |
|
|
| … |
|
|
Условие 1) примет вид:
Условие 2) примет вид:
Раз стоимость перевозки одной тонны из Pi в Qj равна cij, то общая стоимость S всех перевозок равна S = c11x11+c12x12+…+c1kx1k+…+cmkxmk.
Таким образом, мы приходим к следующей чисто математической задаче: дана система m+k линейных уравнений с mk неизвестными и линейная функция S. Требуется среди всех неотрицательных решений данной системы найти такое, при котором функция S достигает наименьшего значения (минимизируется).
Открытые и закрытые транспортные задачи
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Определение 1: Если в транспортной задаче суммарный спрос потребителей и суммарное предложение поставщиков равны, то задача называется закрытой, т.е
. В противном случае задача называется открытой, т.е. 
.
Приведение открытой транспортной задачи к закрытой
При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей.
При этом :
1) если 
то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется невывезенной. Для решения такой задачи вводят фиктивного (n+1)-го потребителя, потребности которого 
.
2) Если 
то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного (m+1) –го поставщика: 
.
При введении фиктивного поставщика или потребителя открытая транспортная задача становится закрытой и решается по ранее рассмотренному алгоритму для закрытых транспортных задач. Тарифы, соответствующие фиктивному поставщику или потребителю, больше или равны наибольшему из всех транспортных тарифов, иногда их считают равными нулю. В целевой функции фиктивный поставщик или потребитель не учитываются.
Построение начального плана транспортной задачи по правилу
« северо–западного» угла.
Алгоритм.
1.Составляем транспортную таблицу;
2.Транспортную таблицу начинают заполнять с левого - верхнего (северо-западного) угла.
2.1. При заполнении двигаемся по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на спрос и предложение.
2.2 . Если спрос удовлетворен – двигаемся по строке вправо, если исчерпано предложение – по столбцу вниз.
Процесс продолжается до тех пор, пока не исчерпается предложение и не удовлетворится спрос.
Пример.
На 3 складах имеются запасы продукции в количествах 110, 140, 190 тонн соответственно. 4 потребителя должны получить эту продукцию в количествах 90,150,160, 40 тонн соответственно. Расходы по перевозке 1 т продукции заданы матрицей:
Определить начальное решение транспортной задачи, используя правило «северо-западного угла».
1) Заполним транспортную таблицу.
| № | 1 | 2 | 3 | 4 | Предложение |
| 1 | 90 3 | 20 4 | 5 | 6 | 110 |
| 2 | 7 | 130 5 | 10 8 | 1 | 140 |
| 3 | 9 | 2 | 150 3 | 40 4 | 190 |
| Спрос | 90 | 150 | 160 | 40 |
|
Решение:
1) В первую клетку помещаем 
. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают.
2) Остаток сырья в первом пункте составляет : 110-90=20 у.е. Двигаемся по первой строке вправо 
. Предложение поставщика исчерпано, первая строка вычеркивается.
3) Второму потребителю не хватает 150-20=130 у.е. Двигаемся по второму столбцу вниз 
. Второй столбец вычеркивается.
4) Двигаемся по второй строке вправо 
. Вторая строка вычеркивается.
5) Двигаемся по третьему столбцу вниз 
. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо . Спрос третьего потребителя удовлетворен.
6) Двигаемся по третьей строке вправо
.
Таблица заполнена. Начальный план перевозок имеет вид:
Стоимость перевозок по этому плану составляет
Использование данного правила - наиболее простой способ нахождения начального решения транспортной задачи. План перевозок, полученный этим способом обычно бывает далек от оптимального. Это происходит потому, что при его построении никак не учитываются значения тарифов сij. В связи с этим на практике для получения исходного плана используется другой способ – метод «минимального элемента», в котором при распределении объемов перевозок в первую очередь заполняются клетки с наименьшими тарифами.
Построение начального решения транспортной задачи
методом «минимального элемента»
Алгоритм.
1. Составляют транспортную таблицу.
2. Выбирают клетку таблицы, которой соответствует минимальное значение тарифа. Если клеток с одним и тем же минимальным тарифом несколько - выбирают любое из них.
3. В выбранную клетку аналогично правилу «северо-западного» угла помещают максимально возможное количество единиц продукции, разрешенное ограничениями на спрос и предложение. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку; если удовлетворен спрос - соответствующий столбец.
4. Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае, переходят к шагу 2 без учета заполненных и вычеркнутых клеток.
Пример.
Найдем начальное решение предыдущего примера методом «минимального элемента».
| № |
|
|
|
| Предложение |
|
| 90 3 | 4 | 20 5 | 6 | 110 |
| 2 | 7 | 5 | 100 8 | 40 1 | 140 |
|
| 9 | 150 2 | 40 3 | 4 | 190 |
| Спрос | 90 | 150 | 160 | 40 |
|
1
3
1
Минимальный тариф 
Спрос 4-го потребителя удовлетворен – соответственно 4-ый столбец вычеркиваем.
Минимальный тариф для оставшихся клеток 
Спрос 2-го потребителя удовлетворен – 2-ой столбец вычеркиваем.
Для оставшихся клеток минимальный тариф:
Спрос 1-го потребителя удовлетворен - вычеркиваем 1-ый столбец.
Для оставшихся клеток минимальный тариф:
Предложение 3-его поставщика исчерпано – вычеркиваем 3-ю строку.
Следующий минимальный тариф для оставшихся клеток: 
,
Предложение 1-го поставщика исчерпано – вычеркиваем 1-ую строку.
Для последней оставшейся клетки:
.
План перевозок, полученный по методу минимального элемента, имеет вид:
Стоимость перевозок по этому плану составляет
у.е.
Видим, что стоимость перевозок, полученных по методу минимального элемента, меньше стоимости перевозок, полученных с использованием правила «северо – западного угла» на 60 у.е. План, полученный данным методом более близок к оптимальному.
Проверка найденного решения на оптимальность
Метод потенциалов
Определение 1: Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок невырожденный.
Определение 2: Если число заполненных клеток транспортной таблицы меньше m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок вырожденный.
Вырожденный план перевозок получится, если на каком – то шаге одновременно удовлетворяется спрос потребителя и исчерпывается предложение поставщика, т.е. одновременно вычеркивается строка и столбец.
Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность.
Для оценки водится понятие косвенных затрат. Косвенные затраты – это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не больше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута.
Рассмотрим получение оптимального плана перевозок с использованием метода потенциалов.
1 шаг: Получение начального плана перевозок .( методом «минимального элемента» или другим методом).
2 шаг: Проверка плана на невырожденность
Если полученный план вырожденный, то формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m + n – 1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.
3 шаг: Проверка плана на оптимальность
3.1 Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: Ui +VJ = Cij,
где i , j – номера строк и столбцов, на пересечении которых стоят заполненные клетки, Ui потенциал i – го поставщика Vj – потенциал j –го потребителя Cij - тариф на перевозку из пункта i в пункт j. Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают Ui = 0. Решая систему уравнений, находят значения потенциалов Ui и Vj , i =1,m, j = 1,n.
3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: C1qp = Uq + Vp , где q p – номера строк и столбцов, на пересечении которых стоит свободная клетка, Uq - потенциал q-го поставщика, Vp- потенциал p-го потребителя, C1qp – косвенные тарифы.
3.3 Проверка на оптимальность.
Для каждой свободной клетки таблицы составляется разность между C1qp и Cqp (косвенным и реальным тарифами) 
. Если все 
, то полученный план оптимален. Если хотя бы для одной свободной клетки 
, то план может быть улучшен.
4 шаг. Улучшение плана
4.1 Выбирают клетку, которой соответствует максимальное положительное значение разности, полученной на шаге 3.3. Если имеется несколько одинаковых из них выбирают любое.
Переменная транспортной задачи, соответствующая этой клетке, вводится в список базисных переменных, т.е. данная клетка транспортной таблицы заполняется.
4.2 Выбор переменной выводимой из списка базисных переменных.
Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и оканчивающийся в выбранной свободной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно ставят знак «+», а в остальных вершинах цикла, чередуясь ставят «-» и « + ».Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком « - », которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком «+» и отнимают от значений, стоящих со знаком «-». При таком распределении общий баланс не изменяется. Свободная клетка заполняется. А клетка со знаком «-», которой соответствует наименьшее количество продукции, становится свободной.
Для нового плана повторяют все действия. (т.е переходят к шагу 2).
Пример 1.
Найти оптимальный план перевозок для транспортной задачи.
1) Получим начальный план решения методом минимального элемента.
| № | 1 | 2 | 3 | 4 | Предложение |
| 1 | 7 | 8 | 160 – 1 | + 2 | 160 |
| 2 | 120 4 | 5 | 9 | 20 8 | 140 |
| 3 | 9 | 50 2 | 30 + 3 | 90 – 6 | 170 |
| Спрос | 120 | 50 | 190 | 110 |
|
2) Проверим число заполненных клеток m+n-1= 4+3-1=6, т.е. данный план невырожденный. Определим потенциалы производителей и потребителей, составив уравнения Ui +VJ = Cij, для заполненных клеток и занесем их в таблицу:
2.1 U1+V3=1, U1=0, V1=0,
U2+V1=4, U2=4, V2=0,
U2+V4=8, U3=2. V3=1,
U3+V2=2, V4=4.
U3+V3=3,
U3+V4=6.
2.2 Составим разности для свободных клеток :
Получена положительная разность 
. Заполним клетку первой строки и четвертого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: (3,4), (3,3), (1,3). В клетке (1,4) ставим «+», в клетке (3,4) – «-», в клетке (3,3) «+», в клетке (1,3) ставим « - ». Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком « - » находится в клетке (3,4) х34=90. Отнимаем 90 от значений, стоящих в клетках со знаком « - », и прибавляем к значениям, стоящим в клетках со знаком «+». Получаем новый план перевозок, представленный в следующей транспортной таблице:
| № | 1 | 2 | 3 | 4 | Предложение |
| 1 | 7 | 8 | 70 – 1 | 90 + 2 | 160 |
| 2 | 120 4 | + 5 | 9 | 20 – 8 | 140 |
| 3 | 9 | 50 – 2 | 120 + 3 | 6 | 170 |
| Спрос | 120 | 50 | 190 | 110 |
|
3) Проверим число заполненных клеток: m+n-1=4+3-1= 6 - план невырожденный.
4) Проверим на оптимальность.
4.1 U1+V3=1, U1=0, V1=-2,
U1+V4=2, U2=6, V2=0,
U2+V1=4, U3=2. V3=1,
U2+V4=8, V4=2.
U3+V2=2,
U3+V3=3.
4.2 Составим разности для свободных клеток:
4.3 Получена положительная разность 
. Заполним клетку (2,2). Цикл будет содержать клетки (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2,2).
Для того, чтобы не загромождать таблицу цикл можно вынести отдельно:
|
|
| 70 |
|
| 90 |
|
|
|
| – | + |
|
|
|
|
|
| – |
|
|
| + |
|
|
| 20 |
|
| – | + |
|
|
|
| 50 |
|
| 120 |
|
|
Минимальное значение х24=20 для клеток со знаком « - ». Перераспределив продукцию по циклу, получим новый план перевозок, представленный в таблице:
| № | 1 | 2 | 3 | 4 | Предложение |
| 1 | 7 | 8 | 50 1 | 110 2 | 160 |
| 2 | 120 4 | 20 5 | 9 | 8 | 140 |
| 3 | 9 | 30 2 | 140 3 | 6 | 170 |
| Спрос | 120 | 50 | 190 | 110 |
|
5) Полученный план невырожденный. Проверим на оптимальность.
5.1 U1+V3=1, U1=0, V1=-1,
U1+V4=2, U2=5, V2=0,
U2+V1=4, U3=2. V3=1,
U2+V2=2, V4=2.
U3+V2=2,
U3+V3=3.
5.2 Составим разности для свободных клеток:
Все разности отрицательные, следовательно полученный план является оптимальным.
Стоимость перевозки: Lmin=50·1+110·2+120·4+20·5+30·2+140·3=1330 у.е.
Пример 2.
Три торговых склада могут поставлять некоторое изделие в количестве 9,4 и 8 тонн. Величины спроса трех магазинов розничной торговли на это изделие равны 3, 5 и 6 т.
Какова минимальная стоимость транспортировки от поставщиков к потребителям, если матрица стоимостей имеет вид 
?
Решение: Запасы складов 
потребности магазинов: 
- задача открытая. Введем фиктивный магазин со спросом 
и тарифом 20 у.е. и решим задачу методом минимального элемента.
| № | 1 | 2 | 3 | 4ф | Предложение | ui |
| 1 | 10 | 1 20 | 6 5 | 2 20 | 9 | 0 |
| 2 | 2 | 4 10 | 8 | 20 | 4 | -10 |
| 3 | 3 1 | 20 | 7 | 5 20 | 8 | 0 |
| Спрос | 3 | 5 | 6 | 7 |
|
|
| vj | 1 | 20 | 5 | 20 |
|
|
Оптимизируем полученное решение:
Найдем потенциалы заполненных клеток. (см. таблицу);
Оценим свободные клетки:
.
Видим, что положительных оценок нет, значит, полученное решение является оптимальным.
.
Минимальная стоимость транспортных расходов Lопт=93 у.е.
Вырожденность в транспортных задачах
При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m+n-1. В этом случае задача имеет вырожденное решение. Для возможного его исключения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и в каждом столбце было не менее одной занятой клетки.
Пример.
Фирма осуществляет поставку бутылок на три завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 – 3000 бутылок и на складе 3 - 4000бутылок. Первому заводу требуется 4000бутылок, второму – 5000 бутылок, третьему – 1000 бутылок. Стоимость перевозки одной бутылки от каждого склада к каждому заводу задана матрицей:
Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?
Решение:
1.1 Запишем данные в распределительную таблицу.
1.2 Найдем опорное решение методом минимального тарифа.
1.3 Проверим вырожденной или невырожденной является транспортная задача: m+n-1=3+4-1=6, а число заполненных клеток равно 5, следовательно, задача является вырожденной (см. определение).
| № | 1 | 2 | 3 | 4 | Предложение | ui |
| 1 | 6 | 3000 4 | 9 | 3000 8 | 6000 | 0 |
| 2 | 5 | 2000 3 | 1000 2 | 8 | 3000 | -1 |
| 3 | 4000 2 | 0 3 | 6 | 8 | 4000 | -1 |
| Спрос | 4000 | 5000 | 1000 | 3000 |
|
|
| vj | 3 | 4 | 3 | 8 |
|
|
Исключим вырожденность. Для этого:
1. Введем в какую–нибудь клетку нулевую поставку. Такая клетка становится условно занятой. Ее целесообразно определить при вычислении потенциалов занятых клеток, она должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми.
2.1.2. Определим потенциалы занятых клеток:
u1+v2=4, u1+v4=8, u2+v2=3, u2+v3=2, u3+v1=2.
Полагая, что u1=0 находим v2=4, u2=-1,v3=3.
Для того чтобы найти u3 и v1 поместим нулевую поставку в клетку (3,2), и из равенства u3+v2=0 найдем сначала u3, затем v1.
3.1. Составим разности для свободных клеток:
Все оценки отрицательные, значит полученное начальное решение является оптимальным.
Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 – 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 – 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28000 у.е.
Приложения транспортных моделей
Алгоритм и методы решения транспортных задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов Cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:
- оптимальное закрепление за станками операций по обработке деталей. В них Cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения Сij берутся с отрицательным знаком;
- оптимальные назначения или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью Сij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
- решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким – то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.
Выбор оптимального варианта использования
производственного оборудования
На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 130 ч.
Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей.
Производительность каждой группы станков на каждую операцию задана матрицей
Решение. Воспользуемся алгоритмом решения закрытой транспортной задачи .
Так как в задаче требуется найти максимум, а согласно алгоритму транспортной задачи находится минимум, тарифы умножим на (—1).
| № | 1 | 2 | 3 | 4 | 5 |
| ui |
| 1 | -3 40 | -5 | -11 | -10 | -5 60 |
100
|
0 |
| 2 | -5 60 | -10 120 | -15 70 | -3 | -2 | 250 | -2
|
| 3 | -4
| -8 | -6 | -12 110 | -10 70 | 180 | -5 |
|
| 100 | 120 | 70 | 110 | 130 |
|
|
| VJ | -3 | -8 | -13 | -7 | -5 |
|
|
Находим потенциалы свободных клеток:
.
Так как 
, перераспределим грузы, получим
|
|
|
| 60 | 60 |
|
|
|
|
| + | – |
|
|
|
|
|
|
| – | + |
|
|
|
|
|
| 110 |
|
| 70 | 50 |
|
| 130 |
Полученное перераспределение грузов занесем в таблицу.
| № | 1 | 2 | 3 | 4 | 5 |
| ui |
| 1 | -3 40 | -5 | -11 | -10 60 | -5
|
100
| 0 |
| 2 | -5 60 | -10 120 | -15 70 | -3 | -2 | 250 | -2
|
| 3 | -4
| -8 | -6 | -12 50 | -10 130 | 180 | -2 |
|
| 100 | 120 | 70 | 110 | 130 |
|
|
| VJ | -3 | -8 | -13 | -10 | -8 |
|
|
Оценки свободных клеток составляют:
Найденное решение является оптимальным, так как все оценки свободных клеток отрицательные.
.
Таким образом, на первой группе станков целесообразно выполнять операции 1 и 4 продолжительностью 40 и 60 часов соответственно, на второй группе – операции 1,2 и 3 продолжительностью 60,120 и 70 часов соответственно. При этом максимальное количество обработанных деталей составит 5170 штук.
Решение транспортной задачи средствами MathCAD.
Решение транспортной задачи можно осуществить средствами MathCAD. Для этого необходимо, чтобы транспортная задача была закрытой. Так как одним из самых эффективных методов решения транспортной задачи является метод потенциалов, рассмотрим, как можно осуществить алгоритм этого метода с помощью пакета MathCAD.
Пример.
Дана транспортная задача (в виде таблицы). Найти ее исходное решение.
| № | В1 | В2 | В3 | Предложение |
| А1 | 70 | 38 | 24 | 14 |
| А2 | 58 | 18 | 56 | 20 |
| А3 | 19 | 10 | 100 | 26 |
| Спрос | 30 | 22 | 8 |
|
т.
Решение:
Исходный план будет состоять из 9-ти чисел ( для данной задачи):
, где 
- количество единиц груза, которое необходимо перевезти из пункта i в пункт j.
Математическая модель такой задачи имеет вид:
Целевая функция:
Системы равенств:
Система ограничений:
, при i=1,2,3; j=1,2,3.
Решение транспортной задачи с использованием MathCAD
Given
: =Minimize (y, 
,
,
, 
,
, 
, 
,
, 
)
=
(y, ,,, ,, , ,, )=
Найденное решение означает следующее:
Производимые на предприятия А1 14 единиц продукции следует распределить по складам следующим образом:
склад В1 – 4 единицы;
склад В2 – 2 единицы;
склад В3 – 8 единиц.
Производимые на предприятии №2 20 единиц продукции следует распределить по складам следующим образом:
склад В1 – 0 единиц;
склад В2 – 20 единиц;
склад В3 – 0 единиц.
Производимые на предприятии №3 26 единиц продукции следует распределить по складам следующим образом:
склад В1 – 26 единиц;
склад В2 – 0 единиц;
склад В3 – 0 единиц.
Затраты на перевозку всех грузов при таком распределении продукции составят 1402 у.е. и эти затраты являются минимальными.
Полезное для учителя
Распродажа видеоуроков!
1580 руб.
2640 руб.
1410 руб.
2350 руб.
1500 руб.
2500 руб.
1250 руб.
2090 руб.
Курсы ПК и ППК для учителей!
500 руб.
2500 руб.
800 руб.
4000 руб.
800 руб.
4000 руб.
600 руб.
3000 руб.
ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО
* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт
Удобный поиск материалов для учителей
Проверка свидетельства