Транспортная задача в excel: как минимизировать затраты на перевозку груза между продавцом и покупателями

Что такое симплекс-метод

Задача линейного программирования — это задача поиска неотрицательных значений параметров, на которых заданная линейная функция достигает своего максимума или минимума при заданных линейных ограничениях.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.

Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c1·x1 + c2·x2 + … + cn·xn

Ограничение — условие вида a1·x1 + a2·x2 + … + an·xn v b, где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x1 … xn.

Распределительный метод

Один из наиболее простых методов решения транспортных задач – распределительный метод.Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции на этом решении F(Х1). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину  можно получить новое опорное решение Х2.Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δlm равно разности двух сумм:где – сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; – сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции. Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Δlm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ•Δlm, т.е. опорное решение можно улучшить.Если же величины Δlm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условиеΔlm≥0, ∀xlm=0Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, m) построить цикл и вычислить оценку Δlm. Если оценка неотрицательная,переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину θ=min{xij}. В результате получится новое опорное решение.

Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очередность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимости перевозок cij ,так как решается задача на нахождение минимума.

Пример. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице:

		b1	b2	b3
		20	40	40
a1	20		1		3		2
a2	30		4		5		7
a3	50		6		8		15

Решение. Строим начальное опорное решение методом минимальной стоимости :Затем вычисляем значение целевой функции на нем: F(X1) = 20∙1 + 30∙5 + 10∙8 + 40∙15 = 850.ТаблицаНаходим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2).Вычисляем оценку Δ12 = (3 + 15) – (2 + = 8. Так как Δ12 = 8 > 0,переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1,3), (3, 3), (3, 2), (2, 2) (см. табл.).Оценка Δ21 = (4 + 2 + – (1 + 15 + 5) =14 – 21 = -7. Так как Δ21| = -7 < 0,определяем величину груза, перераспределяемого по циклу, θ=min{20,40,30}=20. Приращение целевой функции ΔF=-7∙20=-140. Получим новое опорное решение X2 . Значение целевой функции на нем F(X2)=20∙2+20∙4+10∙5+30∙8+20∙15=710.Вычисляем Δ11 = (1 + 15 + 5) – (2 + 8 + 4) =7>0 , Δ12= (3 + 15) – (2 + =8>0,   Δ 23 = (7 + – (5 + 15)=-5<0, Δ31= (6 + 5) – (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так какΔ23 =-5<0,  осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину θ=min{10,20}=10. Приращение целевой функции ΔF=-5∙10=-50. Получаем третье опорное решение X3. Значение целевой функции на нем F(X3)=20∙2+20∙4+10∙7+40∙8+10∙15=660.Вычисляем оценки для свободных клеток Δ11 = (1 + 7) – (2 + 4) =2>0 ,  Δ12 = (3 + 15) – (2 + =8>0,   Δ22 =(5 + 15) – (7 +   =5>0,   Δ31 = (6 + 7) – (4 + 15) =-6<0. Так как  Δ31 =-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину θ=min{20,10}=10. Приращение целевой функции ΔFm=-6∙10=-60. Получаем четвертое опорное решение X4 Значение целевой функции на нем F(X4)=20 ∙2+10∙4+20∙7+10∙6+40∙8=600. Вычисляем оценки для свободных клеток Δ11 = (1 + 7) – (2 + 4) =2>0 ,  Δ12 = (3 + 7+ 6) – (2 +4+ =2>0,   Δ22 =(5 + 6) – (4 +   =-1<0. Так как  Δ22 =-1<0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1),на величину θ=min{10,40}=10. Приращение целевой функции ΔF=-1∙10=-10. Получаем пятое опорное решение X5.Значение целевой функции на нем F(X5)=20 ∙2+10∙5+20∙7+20∙6+30∙8=590.Вычисляем оценки для свободных клеток Δ11 = (1 + 7) – (2 + 4) =2>0 ,  Δ12 = (3 + 7) – (2 +5) =3>0,   Δ33 =(15 + 5) – (7 +   =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

см. также Пример решения задачи распределительным методом

Постановка задачи и подготовка таблиц

Цель задачи сводится к математическому моделированию минимизации грузопотоков. Довольно часто студенты пишут рефераты на тему поиска решения транспортной задачи. Этот пример можно взять за основу реферата. Рассмотрим решение на конкретном примере.

Задача

В хозяйстве имеются 5 складов минеральных удобрений и 4 пункта, в которые необходимо доставить удобрения. Потребность каждого пункта в удобрениях различна, а так же запасы на каждом складе ограничены. Требуется определить, с какого склада, в какой пункт поставлять, сколько удобрений для минимализации грузооборота перевозок.

Исходные данные:

Наличие минеральных удобрений (либо иной продукции)  на складах.

Склады	Наличие удобрений, т.
Склад № 1	200
Склад № 2	190
Склад № 3	220
Склад № 4	145
Склад № 5	280

Потребность в минеральных удобрениях на различных пунктах.

Пункты	Потребность в удобрениях
1 пункт	200
2 пункт	150
3 пункт	220
4 пункт	330

Расстояние между складами и пунктами доставки

	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад № 1	6	4	5	11
Склад № 2	12	6	4
Склад № 3	15	7	10	4
Склад № 4	9	5	12	5
Склад № 5	3	7	12	11

Данные в таблицах. На пересечении столбца конкретного пункта доставки со строкой склада находится информация о расстоянии между этим пунктом доставки и складом. Например, расстояние между 3 пунктом и складом № 3 равно 10 километрам.

Пример решения транспортной задачи в Excel

Теперь давайте разберем конкретный пример решения транспортной задачи.

Условия задачи

Имеем 5 поставщиков и 6 покупателей. Объёмы производства этих поставщиков составляют 48, 65, 51, 61, 53 единиц. Потребность покупателей: 43, 47, 42, 46, 41, 59 единиц. Таким образом, общий объем предложения равен величине спроса, то есть, мы имеем дело с закрытой транспортной задачей.

Кроме того, по условию дана матрица затрат перевозок из одного пункта в другой, которая отображена на иллюстрации ниже зеленым цветом.

Решение задачи

Перед нами стоит задача при условиях, о которых было сказано выше, свести транспортные расходы к минимуму.

1. Для того, чтобы решить задачу, строим таблицу с точно таким же количеством ячеек, как и у вышеописанной матрицы затрат.
2. Выделяем любую пустую ячейку на листе. Кликаем по значку «Вставить функцию», размещенному слева от строки формул.
3. Открывается «Мастер функций». В списке, который предлагает он, нам следует отыскать функцию СУММПРОИЗВ. Выделяем её и жмем на кнопку «OK».
4. Открывается окно ввода аргументов функции СУММПРОИЗВ. В качестве первого аргумента внесем диапазон ячеек матрицы затрат. Для этого достаточно выделить курсором данные ячейки. Вторым аргументом выступит диапазон ячеек таблицы, которая была приготовлена для расчетов. Затем, жмем на кнопку «OK».
5. Кликаем по ячейке, которая расположена слева от верхней левой ячейки таблицы для расчетов. Как и в прошлый раз вызываем Мастер функций, открываем в нём аргументы функции СУММ. Кликнув по полю первого аргумента, выделяем весь верхний ряд ячеек таблицы для расчетов. После того, как их координаты занесены в соответствующее поле, кликаем по кнопке «OK».
6. Становимся в нижний правый угол ячейки с функцией СУММ. Появляется маркер заполнения. Жмем на левую кнопку мыши и тянем маркер заполнения вниз до конца таблицы для расчета. Таким образом мы скопировали формулу.
7. Кликаем по ячейке размещенной сверху от верхней левой ячейки таблицы для расчетов. Как и в предыдущий раз вызываем функцию СУММ, но на этот раз в качестве аргумента используем первый столбец таблицы для расчетов. Жмем на кнопку «OK».
8. Копируем маркером заполнения формулу на всю строку.
9. Переходим во вкладку «Данные». Там в блоке инструментов «Анализ» кликаем по кнопке «Поиск решения».
10. Открываются параметры поиска решения. В поле «Оптимизировать целевую функцию» указываем ячейку, содержащую функцию СУММПРОИЗВ. В блоке «До» устанавливаем значение «Минимум». В поле «Изменяя ячейки переменных» указываем весь диапазон таблицы для расчета. В блоке настроек «В соответствии с ограничениями» жмем на кнопку «Добавить», чтобы добавить несколько важных ограничений.
11. Запускается окно добавления ограничения. Прежде всего, нам нужно добавить условие того, что сумма данных в строках таблицы для расчетов должна быть равна сумме данных в строках таблицы с условием. В поле «Ссылка на ячейки» указываем диапазон суммы в строках таблицы расчетов. Затем выставляем знак равно (=). В поле «Ограничение» указываем диапазон сумм в строках таблицы с условием. После этого, жмем на кнопку «OK».
12. Аналогичным образом добавляем условие, что столбцы двух таблиц должны быть равны между собой. Добавляем ограничение, что сумма диапазона всех ячеек в таблице для расчета должна быть большей или равной 0, а также условие, что она должна быть целым числом. Общий вид ограничений должен быть таким, как представлен на изображении ниже. Обязательно проследите, чтобы около пункта «Сделать переменные без ограничений неотрицательными» стояла галочка, а методом решения был выбран «Поиск решения нелинейных задач методом ОПГ». После того, как все настройки указаны, жмем на кнопку «Найти решение».
13. После этого происходит расчет. Данные выводятся в ячейки таблицы для расчета. Открывается окно результатов поиска решения. Если результаты вас удовлетворяют, жмите на кнопку «OK».

Как видим, решение транспортной задачи в Excel сводится к правильному формированию вводных данных. Сами расчеты выполняет вместо пользователя программа.

Виды транспортных задач

Условия и ограничения транспортной задачи достаточно обширны и разнообразны. Поэтому для ее решения разработаны специальные методы. С помощью некоторых из них можно найти эталонное решение. А затем улучшить его и получить лучший вариант.

Условия транспортной задачи можно представить двумя способами:

• в виде схемы;
• в виде матрицы.

В процессе решения могут быть ограничения (или задача решается без них).

В зависимости от характера условий различают следующие виды транспортных задач:

• открытые открытые транспортные задачи (инвентаризация товаров у поставщика не соответствует потребности в товарах у потребителя);
• закрытые (суммарный запас продукции у поставщиков и потребителей одинаков).

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

Решение транспортной задачи в Excel с примером и описанием

Практически все транспортные задачи имеют единую математическую модель. Классический вариант решения иллюстрирует самый экономный план перевозок одинаковых или схожих продуктов от производственного объекта в пункт потребления.

Планирование перевозок с помощью математических и вычислительных методов дает хороший экономический эффект.

Виды транспортных задач

Условия и ограничения транспортной задачи достаточно обширны и разнообразны. Поэтому для ее решения разработаны специальные методы. С помощью любого из них можно найти опорное решение. А впоследствии улучшить его и получить оптимальный вариант.

Условия транспортной задачи можно представить двумя способами:

• в виде схемы;
• в виде матрицы.

В процессе решения могут быть ограничения (либо задача решается без них).

По характеру условий различают следующие типы транспортных задач:

• открытые открытые транспортные задачи (запас товара у поставщика не совпадает с потребностью в товаре у потребителя);
• закрытые (суммарные запасы продукции у поставщиков и потребителей совпадают).

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

Пример решения транспортной задачи в Excel

Предприятия А1, А2, А3 и А4 производят однородную продукцию а1, а2, а3 и а4, соответственно. В условных единицах – 246, 186, 196 и 197. Затем товар поступает в пять пунктов назначения: В1, В2, В3, В4 и В5. Это потребители продукции. Они готовы ежедневно принимать 136, 171, 71, 261 и 186 единиц товара.

Стоимость перевозки единицы продукции с учетом удаленности от пункта назначения:

Производители	Потребители	Объем производства
В1	В2	В3	В4	В5
А1	4,2	4	3,35	5	4,65	246
А2	4	3,85	3,5	4,9	4,55	186
А3	4,75	3,5	3,4	4,5	4,4	196
А4	5	3	3,1	5,1	4,4	197
Объем потребления	136	171	71	261	186

Задача: минимизировать транспортные расходы по перевозке продукции.

1. Проверим, является ли модель транспортной задачи сбалансированной. Для этого все количество производимого товара сравним с суммарным объемом потребности в продукции: 246 + 186 + 196 + 197 = 136 + 171 + 71 + 261 + 186. Вывод – модель сбалансированная.
2. Сформулируем ограничения: объем перевозимой продукции не может быть отрицательным и весь товар должен быть доставлен к пунктам назначения (т.к. модель сбалансированная).
3. Введем стоимость перевозки единицы продукции в рабочие ячейки Excel.
4. Введем формулы для расчета суммарной потребности в товаре. Это будет первое ограничение.
5. Введем формулы для расчета суммарного объема производства. Это будет второе ограничение.
6. Вносим известные значения потребности в товаре и объема производства.
7. Вводим формулу целевой функции СУММПРОИЗВ(B3:F6; B9:F12), где первый массив (B3:F6) – стоимость единицы перевозки товаров. Второй (B9:F12) – искомые значения транспортных расходов.
8. Вызываем команду «Поиск решения» на закладке «Данные» (если там нет данного инструмента, то его нужно подключить в настройках Excel, а как это сделать описано в статье: расширенные возможности финансового анализа). Заполняем диалоговое окно. В графе «Установить целевую ячейку» — ссылка на целевую функцию. Ставим галочку «Равной минимальному значению». В поле «Изменяя ячейки» — массив искомых критериев. В поле «Ограничения»: искомый массив >=0, целые числа; «ограничение 1» = объему потребностей; «ограничение 2» = объему производства.
9. Нажимаем «Выполнить». Команда подберет оптимальные переменные при заданных ограничениях.

Так выглядит «сырой» вариант работы инструмента. Экспериментируя с полученными данными, находим подходящие значения.

Решение открытой транспортной задачи в Excel

При таком типе возможны два варианта развития событий:

• суммарный объем производства превышает суммарную потребность в товаре;
• суммарная потребность больше суммы запасов.

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

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

Единица перевозки груза для фиктивного участника равняется 0.

Когда все преобразования выполнены, транспортная задача становится закрытой и решается обычным способом.

Вступление (лирическое)

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

Итак, мне досталась задача, которая по постановке напоминает транспортную задачу открытого типа и решать ее нужно было непременно в запросе. Сохранившиеся в памяти фрагменты университетского курса по этой проблеме ответов не дали. Поиски в интернете тоже ничем полезным не закончились. Однако в голове сохранялось четкое ощущение того, что решение существует и достаточно простое.

В итоге, примерно за неделю проб и ошибок, было найдено решение, которое можно использовать даже не вникая в методику его получения. Но, думаю, большинству читателей будет интересно проследить ход моих мыслей и проверить их.

Пример задачи

На складах A1 — A4 есть суммарно 100 тонн зерна, и их нужно развести по текущим расценкам в пункты B1 – B3, потратив как можно меньше средств на доставку. Тарифы на доставку указаны в центре таблицы.

Дублируем нашу таблицу в Excel.

Рисуем другую таблицу.

Диапазон ячеек D12 – F15 заполняем единицами. Эти значения мы впоследствии будем изменять, чтобы найти самый дешёвый вариант перевозки. В диапазоне H12 – H15 должна быть сумма трёх единиц таблицы в строке D12 – F12, а в D17 – F17 – сумма четырёх единиц в столбце. Так напротив каждой строки и каждого столбца

Рисуем третью таблицу, которая перемножит соответствующие ячейки первых двух таблиц.

Для этого выделяем диапазон 3 на 4 клетки, жмём на кнопку « = », выделяем диапазон D3-F6, жмём на клавиатуре « * », выделяем D12 – F15 и зажимаем сочетание клавиш Ctrl + Shift + Enter. Всё, вы перемножили значения.

Теперь суммируем все значения последней таблицы. Для этого просто выберите произвольную свободную ячейку в MS Excel. Введите в неё « =СУММ( » и выделите третью таблицу. Нажмите Enter.

Переходим во вкладку «Данные» и находим там «Поиск решения».

Щелкаем по данной кнопке. Далее всё делаем, как представлено на рисунке.

Описываю сверху вниз всё окно. Выберите целевую ячейку ту, которую мы сделали в 4-ом шаге нашего решения. Далее выберите минимум. В поле «Изменяя ячейки переменных» выберите диапазон, где мы проставили единицы. Выставляем ограничения. Значения, которые будут находиться вместо единиц, должны быть больше нуля и целыми, а потребности не должны превысить запасов. Жмём «Найти решение».

Получаем следующий результат.

Если вы всё сделали правильно, то у вас должно быть всё точно так же.

Лабораторная работа 2. Решение транспортной задачи в пакете ms Excel.

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

Однородный
продукт, сосредоточенный в

Примем
следующие обозначения: i
– номер пункта производства, j
–номер пункта потребления,

Условия
задачи удобно записывать в виде таблицы,
которая называется матрицей
планирования:

с11 с12 … с1n . . . сm1 сm2 … сmn	a1 … am
b1 b2… bn

Рассмотрим решение
транспортной задачи в табличном
процессоре MS
Excel.
Так как транспортная задача является
частным случаем задачи линейного
программирования, то эту задачу можно
решать так, как описано выше. Однако
благодаря свойствам задачи, ее можно
записать в более компактной форме.

Рассмотрим
транспортную задачу, матрица планирования
которой имеет вид:

Bj Ai	B1	B2	B3	B4	B5
A1	14	25	18	19	23	33
A2	2	17	16	24	2	25
A3	29	3	7	15	22	25
A4	5	20	17	23	10	17
	33	11	11	11	34	bj ai

Для решения
транспортной задачи введем данные, как
показано на рис.6.

Рис.6.
Исходные данные транспортной задачи.

Вячейки
B2
: F5
введем стоимость перевозок. Ячейки B8
: F11
отведены под значения объемов перевозок,
пока не­известные. В ячейки H8
: h21
введены объемы производства, а в ячейки
B13
: F13
— потребности (спрос) в продукции в
пунктах потребления.

В
ячейку G12
вводится целевая функция

=
СУММПРОИЗВ (B2
: F5; B8
: F11)
.

В
ячейки B12
: F12
вводятся формулы

=
СУММ (B8
: B11),

=
СУММ (C8
: C11),

=
СУММ (D8
: D11),

=
СУММ (E8
: E11),

=
СУММ (F8
: F11),

определяющие объем
продукции, ввозимой в пункты потребления.
В ячейки

G8
: G11
введены формулы

= СУММ (B8
: F8),

= СУММ (B9
: F9),

= СУММ (B10
: F10),

= СУММ (B11
: F11),

характеризующие
объем продукции, вывозимой из пунктов
производства.

Далее выбираем
команду Сервис,
Поиск решения изаполняем
открывшееся диалоговое окно Поиск
решения, как
показано на рис.7.

Рис.7.
Диалоговое окно Поиск
решения для транспортной задачи.

В диалоговом окне Параметры
поиска решения установить
флажок Линейная
модель (рис.8).

Рис.8.
Диалоговое окно Параметры
поиска решений.

После нажатия
кнопки Выполнить получаем
оптимальный план поставок продук­ции
и соответствующие ему транспортные
расходы (рис. 9).

Рис.9.
Оптимальное решение транспортной
задачи.

Заключение

Таким образом, с помощью программы Эксель достаточно просто решить транспортную задачу. Самое главное – правильно заполнить начальные данные и четко следовать плану действий, и тогда проблем быть не должно, т.к. программа все расчеты выполнит сама.

Решим транспортную задачу методом потенциалов. Нам известны торговые запасы, потребительские запросы и стоимость доставки за единицу продукции. Сделаем три исходные таблицы.

Построим опорный план транспортной задачи с помощью инструмента «Поиск решений». Рядом составим такие же по объему таблицы с пустыми ячейками. Таблица А – аналог стоимостной, Б – «запасов», В – «спроса».

Элементы таблицы Б – сумма соответствующих строк в таблице А. Элементы таблицы В – сумма соответствующих столбцов в таблице А.

Отдельно составим результирующую таблицу Г. В ней отразятся оптимальные транспортные расходы. Каждый элемент таблицы Г – произведение элемента А и соответствующего элемента стоимостной таблицы.

В отдельном месте листа введем формулу функции: =СУММПРОИЗВ(A1:C3;G1:I3)

Первый массив – стоимостная таблица, второй – диапазон А.

Ставим курсор в ячейку со значением функции. Вызываем инструмент «Поиск решения». Заполняем диалоговое окно:

1. Целевая ячейка – ссылка на ячейку со значением функции.
2. Она должна быть равна «максимальному значению», как наиболее выгодному для перевозчика.
3. Команда изменяет значения ячеек в таблице А. Значения – целые числа.
4. Диапазон таблицы Б = «Запасам».
5. Диапазон В = «Потребительскому спросу».

В открытом диалоговом окне нажимаем кнопку «Параметры» и устанавливаем следующие настройки:

Жмем ОК – «Выполнить». Получаем опорный план транспортной задачи:

Он залит бледно-зеленым цветом. Ячейки со значениями выше нуля называются «базисными», «занятыми». Ячейки со значением 0 – «свободными».

Далее действуем по плану:

Посчитаем число занятых клеток с помощью функции СЧЕТЕСЛИ.

Так как результат равен 5, опорный план является не вырожденным. Проверим оптимальность опорного плана – найдем потенциалы по занятым клеткам.

Нужно составить систему уравнений. Предполагается, что αj = 0, а αi + βj = сij (стоимость доставки единицы груза). Вызываем команду «Поиск решения». Вносим условия системы уравнений в качестве ограничений.

Заполненное диалоговое окно:

Результат работы инструмента «Поиск решения»:

Посчитаем оценки свободных клеток. Формула: сij – (αi + βj). Берем свободную клетку из таблицы А. Смотрим ее значение в стоимостной таблице. Это будет сij. Далее смотрим, какие потенциалы соответствуют данной клетке. Вставляем их значения в формулу.

В программе Excel найдем оценки с помощью математических операторов и ссылок на соответствующие ячейки.

План считается оптимальным, если оценки больше или равны 0. В нашем случае получились отрицательные значения – план не является оптимальным. Поэтому двигаемся дальше.

Находим, какой клетке в таблице А соответствует минимальная оценка. Строим для этой клетки цикл – замкнутую ломаную линию. Условия: обязательно чередование вертикального и горизонтального направления, только по базисным клеткам.

В исходной клетке (с минимальной оценкой) ставим знак «+». Далее чередуем: «-», «+» и т.д.

В таблице стоимости находим минимальное значение со знаком «-».

В нашем примере – это «5», ячейка В1. Эту клетку нужно убрать из базиса. А ячейку с минимальной оценкой сделать базисной.

С учетом изменившихся данных вновь строим опорный план транспортной задачи. Применяем инструмент «Поиск решения». Пересчитанный план перевозок выглядит так:

Обратите внимание: ячейка I1 (где была минимальная оценка) стала базисной, занятой. Проводим те же расчеты для нового плана (с пункта №1): находим потенциалы, оценки свободных клеток для проверки оптимальности. И так до тех пор, пока оценки свободных клеток не будут больше или равны 0

И так до тех пор, пока оценки свободных клеток не будут больше или равны 0

Проводим те же расчеты для нового плана (с пункта №1): находим потенциалы, оценки свободных клеток для проверки оптимальности. И так до тех пор, пока оценки свободных клеток не будут больше или равны 0.

Полученное решение сохраняется в файле Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в Excel .

Решение матричной игрыС помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Задачи динамического программирования

• вычеркивания (метод двойного предпочтения);
• северо-западного угла;
• минимального элемента;
• аппроксимации Фогеля.