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

В качестве примера была рассмотрена транспортная задача для 2 складов и 5 магазинов.

·В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах.

·В ячейки E5:I5 - заявки на продукцию, поступившие от магазинов.

·В ячейки B8:F9 - матрицу транспортных расходов, задающую расходы на перевозку из I-го склада в J-й магазин единицы продукции.

·В ячейки B13:F14 - план перевозок - матрицу, задающую количество товара, перевезенного из I-го склада в J-й магазин. Начальное распределение плана задано по принципу "каждой сестре по серьге", равномерно распределив всю имеющуюся на складе продукцию по магазинам. Эти ячейки являются регулируемыми и Решатель должен найти более подходящее решение, изменив значения в этих ячейках.

·В ячейку D15 - записал целевую функцию:

{ =СУММ((B8:F8*B13:F13)+(B9:F9*B14:F14))}

·В ячейки D17:H17 записал ограничения, задающие требование о точном выполнении заявки каждого магазина. Как обычно, я записал соответствующую формулу в первую из этих ячеек:

{=СУММ(B13:B14) - E5 }

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

·Затем задают следующую группу ограничений. Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D18, имеет вид:

{=C4 - СУММ(B13:F13)}

Эта формула скопирована уже по столбцу в ячейку D19. Подготовительный этап завершен - можно вызывать Решатель.

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

Рисунок 3.3.1 – Окно Решателя при решении транспортной задачи

Прежде чем дать команду на решение задачи, проводится настройка параметров в окне Options. В частности я включил флажки, указывающие на линейность модели и положительность переменных. Кроме того, увеличена точность решения целочисленной задачи, задавая в окне Tolerance значение в 1% вместо 5%, принятых по умолчанию.

Рисунок 3.3.2 – Настройка в окне параметров Решателя при решении транспортной задачи

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

Рисунок 3.3.3 – Решение транспортной задачи

Параметры, управляющие работой Решателя

Рассмотрим возможности управления работой Решателя, задаваемые в окне Параметры (Options):

· Максимальное время (MaxTime) - ограничивает время, отведенное на процесс поиска решения. По умолчанию задано 100 секунд, что обычно достаточно для задач небольшой размерности, имеющих около 10 ограничений. Для задач большой размерности придется это значение увеличивать.

· Предельное число итераций (Iterations) - еще один способ ограничения времени поиска путем задания максимального числа итераций. По умолчанию задано 100, но это число можно увеличивать до 32767. Чаще всего, если решение не получено за 100 итераций, надежд получить его при увеличении этого значения мало. Лучше попытаться изменить начальное приближение и запустить процесс поиска заново.

· Относительная погрешность (Precision) - задает точность выполнения ограничений. Иногда проще изменить ограничение, отодвинув границу, чем пытаться выполнить ограничения с высокой точностью.

· Сходимость (Convergence) - задается десятичной дробью, меньшей единицы, позволяя остановить процесс поиска при сходимости решения к неподвижной точке, когда относительные изменения в течение последних 5 итераций не превышают заданную дробь.

· Линейная модель (Assume Linear Model) - этот флажок следует включать, когда целевая функция и ограничения - линейные функции. Эта дополнительная информация позволяет Решателю упростить процесс поиска решения.

· Неотрицательные значения (Assume Non-Negative) - этим флажком можно задать ограничения на переменные, что позволит искать решения в положительной области значений, не задавая специальных ограничений на их нижнюю границу.

· Показывать результаты итераций (Show Iteration Results) - флажок, позволяющий включить пошаговый процесс поиска, показывая на экране результаты каждой итерации. В сложных ситуациях, когда Решатель не находит решения автоматически, рекомендуется включать этот флажок, так как иногда можно найти точку, от которой процесс поиска уклонился в сторону.

· Автоматическое масштабирование (Use Automating Scaling) - флажок автоматического изменения масштаба следует включать, когда масштаб значений входных переменных и целевой функции и ограничений отличается, возможно, на порядки. Например, переменные задаются в штуках, а целевая функция, задающая суммарную стоимость, измеряется в миллионах рублей.

· Относительная погрешность (Tolerance) - задается в процентах. Указанное значение имеет смысл только для задач с целочисленными ограничениями. Решатель в таких задачах вначале находит оптимальное не целочисленное решение, а потом пытается найти ближайшую целочисленную точку, решение в которой отличалось бы от оптимального не более чем на указанное данным параметром количество процентов. Если такая точка найдена, Решатель сообщает об успехе. При большом допуске (по умолчанию 5%) может быть потеряно лучшее целочисленное решение, правда, отличающееся от найденного Решателем в пределах допуска. Для целочисленных задач допуск имеет смысл уменьшить, что я и сделал при решении транспортной задачи. Хочу еще раз обратить внимание на эту особенность решения задач целочисленного программирования. Если значение параметра Tolerance задать большим, то Решатель может остановиться раньше времени, не найдя лучшего целочисленного решения. Если же его взять малым, то наилучшее целочисленное решение будет отличаться от оптимального нецелочисленного решения на величину большую, чем ту, которая задается параметром Tolerance. В этом случае формально решение заканчивается неуспехом, поскольку найденное решение не удовлетворяет всем требованиям. Конечно, параметр Tolerance играет служебную роль, и "умный" Решатель, найдя наилучшее целочисленное решение, должен был бы уведомлять, что решение найдено, но ограничение по Tolerance не выполнено. Этого, однако, не происходит. Мы еще столкнемся с этой ситуацией при рассмотрении следующей задачи.

· Сохранить модель (Save Model) - командная кнопка; позволяет открыть диалоговое окно, где можно указать имя сохраняемой модели. Имеет смысл использовать эту возможность, когда на рабочем листе несколько моделей, так как единственная модель запоминается автоматически.

· Загрузить модель (Load Model) - позволяет загрузить одну из сохраненных моделей.

· Есть еще несколько более специальных параметров, которыми можно управлять, варьируя процедурами, применяемыми в процессе поиска. К ним следует прибегать в тяжелых ситуациях, когда решение найти не удается.

3.8 Решение транспортной задачи на BORLAND С++

Описание Алгоритма программы

ПРОГРАММА НАПИСАНА НА BORLAND С++ версии 3.1

Программа решает Транспортную Задачу (ТЗ) 3 методами:

1. Северо-западным углом

2. Северо-восточным углом

3. Методом минимального элемента в строке.

Программа состоит из функций:

1. Main()

2. Data()

3. Opplan()

4. Sohran()

5. Bas()

6. Kost()

7. Potenzial()

8. Optim()

9. Plmi()

10. Abcikl()

11. Cikl()

12. Prpoisk()

13. Levpoisk()

14. Verpoisk()

15. Nizpoisk()

16. Pr()

Главная функция main() невелика, но в ней происходит обращение функциям, выполняющим определенные действия в процессе решения ТЗ. Здесь следует обратить особое внимание на строку программы if(!z) break; - если бы не она (она показывает, что после очередной проверки базисного плана, если он оптимален, возвращаемое значение из функции optim() равно 0, что приводит к выходу из бесконечного цикла улучшения базисных планов). Иногда возникает ситуация, когда базисная переменная (одна или несколько) равна нулю, и ее следует отличать от других базисных переменных. В матрице matr() такие элементы я пометил как –2. Основные переменные я описал в комментариях в программе.

Функция data() производит ввод данных на ТЗ.

Функция opplan() выполняет задачи по составлению первоначального базисного плана методом северо-заподного угла. В этой функции используются следующие переменные:

Int *matr указатель на матрицу базисных переменных

Int *po указатель на вектор пунктов отправления

Int *pn указатель на вектор пунктов назначения

Int m количество пунктов отправления

Int n количество пунктов назначения

Функция kost() производит вывод суммарной стоимости перевозок по текущему базисному плану. Используются следующие переменные:

Int *matr, m,n;

Int *st указатель на матрицу стоимостей.

Функция potenzial() выполняет подсчет потенциалов.

Использует следующие переменные:

Int *pu указатель на вектор потенциалов строк

Int *pv указатель на вектор потенциалов столбцов

Int matr, m, n, *st;

Первоначально элементы векторов потенциалов *(pu+i) и *(pv+j) заполняются минимальными значениями для целых переменных = 32768, определенных предпроцессорным оператором define MIN – 32768. Далее пологая, что *pu=0, и используя структуру struct poten{…}, элементы векторов потенциалов приобретают свои реальные значения.

Работу этого модуля я бы разделил на эти этапы:

· Выделение памяти под элемент структуры top = (struct poten*)malloc(sizeof(struct poten)); заполнение полей элемента структуры необходимой информацией; установление связей между элементами структуры;

· Вычисление потенциалов строк и столбцов с занесением информации в секторы pu и pv;

· Проверка правильности заполнения векторов pu и pv, т.е. установление не содержат ли элементы этих векторов значения MIN. При необходимости, если существуют такие элементы векторов, производятся дополнительные вычисления;

· Вывод векторов pu и pv;

Функция optim() проверяет план на оптимальность, если он оптимален, то функция отправляет в главную функцию main() значение 0, в противном случае, если он не оптимален, то управление передается функции abcikl() и возврат главной функции main() значение –1. Функция optim() использует переменные:

Int m,n,*pu,*pv,*matr,*st. Цепь строится относительно первой попавшейся графоклетки, для которой u_i + v_j =c_ij, а не относительной характеристики. В ходе решения ТЗ промежуточные базисные планы отличаются от тех, которые я построил, начиная с координат графоклетки с минимальным значением отрицательной характеристики, но врезультате оптимальный план будет тот же.

Функция abcicl() – использует следующие переменные

Int *matr, m, n;

Int *matr2 //указатель на рабочую (изменяемую) матрицу, по началу она является копией оригинальной.

Int ik,jk; // координаты графоклетки, с которой начинает строиться цепь. В этой функции присваивается графоклетки, с которой будет происходить поиск цикла(цепь), значение -1.

Функция cikl() производит поиск относительно графоклетки со значением –1. Она использует следующие переменные:

Int *matr2, ik, jk;

Int ch; // счетчик количества элементов в массивах *zi и *zj

Int *zi, *zj // указатели на массивы индексов. Хранят индексы элементов matr, подлежащих перераспределению.

Функции prpoisk(), levpoisk(), verpoisk(), nizpoisk()-поиск, соответственно, вправо, влево, вверх, вниз – относительно текущей графоклетки. Поиск происходит в массиве *matr2. Если известна строка, то выполняется поиск столбца, т.е. его индекса, если известен столбец –ищется строка.

Данные функции возвращают координаты столбца или строки найденной графоклетки, либо значение –1, если графоклетка в данном направлении не найденна.

Работа модуля cikl() заключается в следующем:

Поиск нужного элемента начинается относительно графоклетки, помеченной –1 в матрице matr2 (с координатами ik и jk согласно входным данным) по возможным направлениям (поочередно);

· Если поиск успешен, то поля структуры заполняются информацией, найденный элемент структуры включается в список(работу модуля поддерживает линейный список, в котором хранится информация о ходе поиска цепи), и за основу берется уже эта (текущая) графоклетка матрицы matr2(). Далее процедура поиска повторяется:

· Если поиск на каком-то шага не неуспешен по возможным направлениям, то найденный элемент исключается из списка и за основу берется последний элемент списка (после удаления). В рабочей матрице matr2() «обнуляется» элемент с координатами, который хранил исключенный элемент, что необходимо для того, чтобы исключить повторное обращение к элементу matr2, не входящемму в цепь;

· Поиск цикла (цепи) будет закончен, когда при прохождении по какому-либо направлению мы снова наткнемся на элемент матрицы matr2 со значением –1. В конце модуля элементы списка, т.е. его поля с координатами, переписываются в векторы zi и zj.

Внешние переменные:

Int m, n, *matr2;

Входные данные:

Int i1, j1 // координаты текущей графоклетки, относительно которой строится цепь.

Выходные данные:

I(j)- координаты строки, столбца, если переменная найдена;

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

Функция plmi() перераспределяет поставки по цепи, т.е. улучшает план.

Используются следующие переменные:

Int zi,zj;

Int ch,chr; /переменные размерности массивов zi,zj

Int matr /указатель на матрицу базисных переменных

Работа с модулями выполняется в несколько этапов. Если имеется нулевой базисный элемент (помеченный как –2 в матрице matr) и индекс k нечетен для векторов zi,zj, то элементы matr, помеченные, как –1 и –2(новый элемент помеченный как –2 обнуляем), меняются местами, в противном случае(если k четно или нет нулевых базисных элементов в matr) осуществляется:

Нахождение минимального элемента в матрице базисных переменных: min=matr [i][j], где i=zi[k]; j=zj[k]; k-нечетное число;

Перераспределение поставок:

a) если k четное число, то matr[i][j] = matr[i][j]+min, где i=zi[k]; j=zj[k];

b)если k нечетное число, то matr[i][j] = matr[i][j]-min, где i=zi[k]; j=zj[k];

Модуль bas() подсчитывает количество ненулевых базисных переменных в матрице matr.

Модуль sohran() находит нулевую базисную переменную в matr и устанавливает её в –2.

Int basper; /количество базисных переменных.

Функция opplan1() построение первоначального плана методом северо-восточного угла, а opplan2()- методом выбора наименьшего элемента в строке.

Ниже приведен текст программы

#include <stdio.h> //Подключение стандартных#include <alloc.h> // Библиотек#include <conio.h>#include <process.h>#include <stdlib.h>#define MIN -32768 int *po = NULL; //Указатель на массив пунктов отправления

int *pn = NULL; //Указатель на массив пунктов назначения

int *st = NULL; //Указатель на матрицу стоимостей

int *matr=NULL; //Указатель на матрицу базисных переменных

int *matr2 = NULL; //Указатель на рабочую матрицу

int n,m; //Размерность задачи

int *pu,*pv; //Указатели на массивы потенциалов

int *zj,*zi; // Указатель на массивы индексов

int ch=0,ch2=0; //Счетчики

FILE *fpdat; //Указатель на вводной файл

int iter=0; //Счетчик итерации

FILE *fil; //Указатель на выводной файл

int zen = -1; //Переменная для сохранения стоимости п-на

int z = 1; //Флаг для выхода при оптимальном плане

int basper;.

Листинг программы прилогается в пиложении А.