Автор работы: Пользователь скрыл имя, 25 Февраля 2012 в 11:07, реферат
Наше время характерно стремительным развитием компьютерной техники. Следовательно, мощным потоком программного обеспечения. Компьютерные технологии проникают во все сферы человеческой деятельности. Современный человек должен иметь не просто минимальные знания по информационным технологиям, а быть по настоящему подготовленным пользователем.
Теперь все готово для составления системы уравнений и целевой функции, определяющей время выполнения плана перевозок и направленной на минимум. По смыслу ясно, что количество единиц товара, привезенных с каждого склада в контору, в сумме должно равняться потребности этой конторы. Т.е.
X11+ X21=15
X12+ X22=12
X13+ X23=20
X14+ X24=3
Аналогично получаем следующие условия:
X11+X12+X13+X14=20
X21+X22+X23+X24=30
Целевая функция, как я уже говорил, определяет время выполнения намеченного плана транспортировки товара. Поэтому:
E=5* X11 + 20* X12 + 8* X13 + 10* X21 + 15* X22 + 12* X23 ->min
Тарифы на доставку товара в виртуальную контору принимаются равными нулю, поэтому слагаемое "0*X14+0*X24" в записи формулы для целевой функции можно опустить. Теперь приступим непосредственно к решению поставленной задачи. Согласитесь, проделанные до сих пор операции не вызывают больших трудностей.
Выбор метода решения
А найти решение нам поможет мощный табличный процессор Microsoft Excel, широко используемый не только как удобное средство для хранения разнообразных данных и многофункциональный инструмент, позволяющий выполнять над ними многочисленные математические операции, но и как орудие для решения несложных оптимизационных задач. Последним, в частности, и занимается программная надстройка "Поиск решения". Если она у вас не установлена, то проделайте следующие действия: "Сервис" > "Надстройки", потом поставьте галочку около пункта "Поиск решения". Для поиска ответа остается только занести шесть ограничений и целевую функцию в Excel. Я не буду докучать читателю ((с) Джонатан Свифт, "Путешествия Гулливера";) подробным описанием того, как следует вводить данные в ячейки таблицы или как нужно составлять ограничения в "Поиск решения". Этот титанический труд был проделан в первой статье по оптимизации в среде Excel, опубликованной в 21-м номере. Отмечу, что хоть задача про изготовление баннеров и задача про перевозки принадлежат к различным типам задач, для нахождения ответа на которые разработано множество "своих" методов, все-таки обе задачи являются задачами линейного программирования. Поэтому их можно решать и общим для всех задач линейного программирования способом - симплекс-методом. Конечно, для решения транспортных задач вручную намного предпочтительнее использовать специально разработанные для этих целей алгоритмы. Но в конкретном случае мы переложим наше бремя на плечи машины. Ей-то какая разница, выполнять 10 или 100 итераций. Если мы собираемся использовать тот же самый подход, что и при решении задачи об изготовлении баннеров, то алгоритм поиска оптимального ответа в данном примере почти не будет отличаться от алгоритма, описанного в предыдущей статье. Различия будут заключаться лишь в подготовительных работах, которые мы, сами того не зная, уже проделали выше.
Итак, в ячейки строки с целевой функцией запишем коэффициенты перед переменными, входящими в целевую функцию. Так же поступим и cо всеми ограничениями в виде равенств (в столбце "L" записывается правая часть уравнений). В столбце с решением "J" в каждую ячейку введем формулу вида "=СУММПРОИЗВ(Bn:Gn;B2:G2)", где n изменяется от 3 до 9. Теперь открываем рабочее окно "Поиск решения" и записываем все ограничения, показанные на рисунке.
Нажимаем на кнопку "Выполнить" и вместе с Васей радуемся полученным результатам.
Анализ полученных результатов
Оптимальный план перевозок груза выглядит следующим образом: с первого склада нужно переправить 15 ед. груза в первую контору и 5 ед. груза в третью контору, а со второго - 12 ед. груза во вторую и 15 ед. груза в третью конторы. На все это Вася будет тратить 475 минут (7 часов и 55 минут). Это оптимальный вариант. Сравним его с любым другим возможным. Допустим, что Вася решил делать все наобум и выбирал маршрут случайным образом. Пусть план следующий: (X11, X12, X13, X21, X22, X23)=(0, 0, 20, 15, 12, 0). Тогда целевая функция будет равна 490 минут (за смену Вася не управится). С одной стороны, это не много, с другой, если бы в качестве тарифов выступало не время, а деньги, то экономия была бы существенной. Да и если вспомнить фразеологизм "Время - деньги", то всякие сомнения по поводу рациональности использования оптимизации в управлении и финансах отпадают. Ведь выгода заключается не в том, что Васе приходится быстрее крутить педали, а в том, что при помощи математической модели находится наилучший вариант протекания реального процесса.
В качестве следствия можно отметить, что если предстоит решать задачу с правильным балансом, то из всех рассуждений необходимо просто исключить переменные X14 и X24.
Конечно, существует много программ, которые специализируются именно на исследовании транспортных задач. Но с Excel'ем как-то проще ((с) Реклама про "Биосистему"). Иногда время и деньги, потраченные на поиски нужной программы в интернете, сравнимы с выгодой, полученной в ходе оптимизации. На одной web-странице программу, работающую с транспортными задачами, предлагалось приобрести за $100. Другое приложение оказалось бесплатным, но не умело решать задачи в общем случае (с неправильным балансом). Вот такие пироги (или проги ;).
В современном обществе методы оптимизации применяются повсеместно, принося существенную экономическую выгоду и предупреждая финансовые крахи. Они позволяют принимать разнообразные управленческие решения в условиях риска и неопределенности. Правда, уже при помощи более мощных программных комплексов, работающих на основе генетических алгоритмов, нечеткой логики и нейронных сетей.
Решение транспортной задачи в Excel
Нужно подготовить рабочий лист, как показано на рисунке:
Лучше взять готовую «рыбу», которую можно скачать, например, здесь:[1]
Ячейки рядом с серыми (на изображении — строка 12 и столбец F) содержат формулы суммирования по строке и столбцу.
F9: =СУММ(B9:E9)
F10: =СУММ(B10:E10)
F11: =СУММ(B11:E11)
B12: =СУММ(B9:B11)
C12: =СУММ(C9:C11)
D12: =СУММ(D9:D11)
E12: =СУММ(E9:E11)
В отмеченной красным цветом итоговой ячейке использована формула =СУММПРОИЗВ(B4:E6;B9:E11), которая вычисляет сумму произведений цены на объем для каждого из путей перевозки груза. Другие ячейки на этом рабочем листе формул не содержат.
Если число строк и столбцов (поставщиков и потребителей) не совпадает с примером, их добавляют, "не задевая" первую и последнюю колонку из диапазона, чтобы не испортились настройки. Например, чтобы добавить еще одну колонку, добавляйте ее после столбца B, а нового поставщика — после строки Поставщик 1 в двух местах), после чего нужно «размножить» соответствующие формулы и оформление из имеющихся ячеек на вновь вставленные.
В отмеченные зеленым цветом клетки затем надо ввести цены, в отмеченные серым — объем спроса и предложения. Желтые ячейки (объемы перевозки) при вызове надстройки «Поиск решения» программа посчитает сама.
Сумма спроса и сумма запасов (в этом примере = 90) должны совпадать, в противном случае требуется ввести фиктивного отправителя или поставщика с нулевыми ценами доставки (см.Транспортная задача#Балансировка задачи).
Чтобы начать расчет, нужно убедиться, что в меню Сервис есть пункт меню «Поиск решения»:
Если его там нет, то нужно зайти в пункт «Надстройки» и установить соответствующую надстройку:
Затем необходимо вызвать пункт меню «Сервис — Поиск решения»:
В этом примере наложено целочисленное ограничение, если оно не требуется, то его можно убрать (выделить в настройках строку со словом «целое» и нажать кнопку «Удалить»).
Для начала поиска решения нужно нажать кнопку «Выполнить», затем в появившемся окне — «Сохранить найденное решение».
В итоговом решении могут оказаться числа наподобие 19.99999 или 1E-6 — для их форматирования до чисел с нужной разрядностью следует использовать кнопку «Формат с разделителями» на панели инструментов.
По нажатию кнопки Параметры доступно окно с параметрами поиска решения:
В частности, задано ограничение на время исполнения алгоритма и на число итераций (повторений) цикла во избежание зацикливания, при необходимости длительных вычислений можно выставить значения до 32767. Если алгоритм впал в бесконечный цикл, можно исправить ситуацию, прибавив к объемам груза у потребителей в исходной задаче небольшие числа, такие как 0.0001. Чтобы при этом задача не оказалась разбалансированной, сумму этих небольших чисел надо прибавить к объему груза одного из поставщиков.
Основная статья: Вырожденность в транспортной задаче
Общая стоимость транспортировки содержится в отмеченной красным цветом ячейке «Целевая функция». Чем меньше это значение, тем меньше будет затрачено денег на перевозку всего груза.
Excel 2003 выдает ошибку на таблицах определенной величины (из 2-3 десятков потребителей и поставщиков).
Содержание
Введение
§1. Постановка Транспортной задачи (ТЗ) для n переменных
§2. Пример решения Транспортной задачи
§3. Транспортные задачи по различным критериям
§4. Решение транспортной задачи в Excel
Список литературы
Введение
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.
В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.
§1. Постановка Транспортной задачи (ТЗ) для n переменных
Пусть имеется несколько поставщиков однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки – стоимость перевозки единицы продукции. Если какая – либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+∞). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.
Таким образом, требуется составить план перевозок продукции от поставщиков к потребителям так, чтобы потребности потребителей были бы удовлетворены за счет вывоза запаса от поставщиков. Цель – минимизация суммарной стоимости всех перевозок.
Транспортные задачи бывают:
1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)
2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)
Метод потенциалов «работает» только для закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.
Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.
Закрытая транспортная задача формулируется как Задача Линейного Программирования (ЗЛП) следующего вида:
, где
- запас i – го поставщика
- потребность j – го потребителя
- цена перевозки единицы продукции по коммуникациям (i,j)
(от i – го поставщика к j – му потребителю)
- объем перевозки продукции (неизвестный) по коммуникациям (i,j).
Для вывода критерии оптимальности транспортной задачи построим двойственную задачу.
Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей переменной содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.
Вектор двойственных переменных Y = (,…,,,…,) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные ,,…, - потенциалы поставщиков; переменные ,…,- потенциалы потребителей.
Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем:
Информация о работе Решение транспортных задач с помощью MS Excel