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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


реферат Решение транспортных задач с помощью MS Excel

Информация:

Тип работы: реферат. Добавлен: 13.11.2012. Сдан: 2012. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


?РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ПОМОЩЬЮ  MICROSOFT EXCEL
 
Наше время характерно стремительным развитием компьютерной техники. Следовательно, мощным потоком программного обеспечения. Компьютерные технологии проникают во все сферы человеческой деятельности. Современный человек должен иметь не просто минимальные знания по информационным технологиям, а быть по настоящему подготовленным пользователем.
Одной из самых распространенных проблем во всех областях экономики является транспортировка груза или товара с минимальными материальными и временными затратами. Так как огромное количество возможных вариантов перевозок затрудняет получение самого экономичного плана эмпирическим или экспертным путем, то появилась необходимость разработки специальной теории, позволяющей быстро решать подобные задачи с помощью алгоритмизации. Применение математических методов в планировании перевозок дает большой экономический эффект. Транспортные задачи очень просто можно решать с помощью MS Excel.
Рассмотрим следующую транспортную задачу. Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготовить 100, 150 и 50 условных единиц кирпича (предложение поставщиков). Потребности в кирпиче  на каждом из строящихся объектов ежедневно составляют 75, 80, 60 и 85 условных единиц (спрос потребителей). Тарифы перевозок одной условной единицы кирпича с каждого из заводов к каждому из строящихся объектов задаются матрицей транспортных расходов С.
                                       
В левом верхнем углу произвольной (i,j) клетки стоит коэффициент затрат – затраты на перевозку единицы груза от i –го поставщика к j-му потребителю. Задача формулируется следующим образом: найти объемы перевозок для каждой пары «поставщик - потребитель» так, чтобы: мощности всех поставщиков были реализованы, спросы всех потребителей были удовлетворены, суммарные затраты на перевозку были бы минимальны. Обозначим через xijобъем перевозки от i –го поставщика к j-му потребителю. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных xij. Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:

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

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести ограничение не отрицательности переменных:
xij ?0.
Суммарные затраты F на перевозку выражаются через коэффициенты затрат следующим образом:
 
Для математической постановки транспортной задачи в общей постановке обозначим через сij коэффициенты затрат, через Mi – мощности поставщиков, через Nj – мощности потребителей, (i=1,2,…,m)., (j=1,2,…,n), m – число поставщиков, n – число потребителей. Тогда система ограничений примет вид:
                                                  (1)
Система (7) включает в себя уравнения баланса по строкам и по столбцам.
При этом суммарная мощность поставщиков равна суммарной мощности потребителей, т.е.

Целевая функция в данном случае следующая:
                                  (2)
Таким образом, на множестве неотрицательных решений системы ограничений (1) найти такое решение, при котором значение целевой функции (2) будет минимально.
Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи  показан на рис 1.

Рис.1
Затем настраиваем программу «Поиск решения» как показано на рис. 2

Рис.2
В появившемся окне "Поиск решения" установите курсор на кнопку "Выполнить" и щелкните левой клавишей мыши.
После того как на рабочем листе появилось решение (рис.3) в появившемся диалоговом окне "Результаты поиска решения" (рис.4) установите курсор на переключатель "Восстановить исходные значения" и щелкните левой клавишей мыши. Для завершения расчетов щелкните на кнопке ОК.

Рис.3

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

Транспортная задача является наиболее популярной задачей линейного программирования и широко освещена в учебниках и справочниках. Популярнейшим методом аналитического решения является метод потенциалов. Справочная система Excel содержит описание решения, но на наш взгляд она освещена крайне плохо, и не является простой в понимании, осмыслении сделанного и увиденного. Мы предлагаем свою методику решения. 

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

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


Оформим лист Excel'я следующим образом: 


В ячейки (B4:F6) заносится матрица цен, далее в ячейки (B11:F13) помещаются любые значения больше нуля. В ячейках (G11:G13), вычисляются суммы ячеек (B11:F11; B12:F12; B13:F13) соответственно. В (B14:F14), вычисляются суммы ячеек (B11:B13; C11:C13; D11:D13; E11:E13; F11:F13) соответственно. В ячейку F16 записывается следующая формула: "=СУММПРОИЗВ (B11:F13;B4:F6)", вычисляющая произведение соответствующих элементов массивов, а затем суммирует получившиеся значения. 

Далее выделив ячейки (B11:F13) вызываем формат ячеек и в закладке "Число", выставляем число десятичных знаков равным нулю. 

Оформим окно поиска решений следующим образом:
1. Установить целевую ячейку    F16
2. Равной:                      Минимальному значению
3. Изменяя ячейки:                      B11:F13
4. Ограничения:                 B11:F13 >= 0    B14 = 100               C14 = 130
                                D14 = 80                E14 = 190               F14 = 100
                                G11 = 200               G12 = 175               G13 = 225
Нажимаем кнопку: "Выполнить" После нажатия кнопки лист Excel'я должен выглядеть следующим образом: 


Итак из ячейки F16 мы видим, что минимальные затраты на перевозку составляют: 1610 ед. А в ячейках (B11:F13) был получен план грузоперевозок. 

Задания для самостоятельного решения: 

1.
 

2.
 

3.
 

4.
 

5.
 

6.
 

7.
 

 
8.
 

9.
 
 
 
Решение транспортных задач в среде Excel
Продолжение темы, начатой в "КВ" №21/2005
Одной из самых распространенных проблем во всех областях экономики является транспортировка груза или товара с минимальными материальными и временными затратами. Так как огромное количество возможных вариантов перевозок затрудняет получение самого экономичного плана эмпирическим или экспертным путем, то появилась необходимость разработки специальной теории, позволяющей быстро решать подобные задачи с помощью алгоритмизации. Применение математических методов в планировании перевозок дает большой экономический эффект. В этом нам и предстоит сейчас убедиться при помощи нашего знакомого Васи, который как раз устроился работать курьером.

Постановка задачи
Компания, где Василий нашел вакантное место курьера, имеет два склада, на которых хранится товар, и три магазинчика - конторы, где этот товар реализуется. Задача Васи заключается в строгом выполнении плана, который он получает каждый день. В качестве транспортного средства он использует старый, но выносливый советский велосипед, который не позволяет перевозить всю партию за раз. Поэтому нашему ненасытному другу приходится мотаться туда-сюда. На что он опять копит? Что же он там перевозит? Не ждите от меня ответов на эти вопросы, если б знал - давно бы уже сказал бы.
И тут Василий, изнывая от мучительных болей в ногах и предвидя жесткий выговор со стороны начальства за невыполнение работы в намеченный срок, задумался: можно ли составить с учетом выдаваемого ему плана такой маршрут движения, чтобы на выполнение всего задания уходило минимум времени и сил. Конечно, можно! Этим мы сейчас и займемся.

Составление математической модели
Сначала необходимо проделать подготовительную работу, а именно - определить тарифы на каждом участке будущего оптимального плана перевозок. Поскольку Вася заинтересован в том, чтобы делать свою работу максимально быстро, то в качестве тарифов в данной задаче выступает время, потраченное на перевозку единицы товара из n-го склада в m-ую контору. При помощи карты Минска (CityInfo) с учетом времени на перекур и на подкачку шин, Вася оценил среднее время перевозки товара из каждого склада в каждую контору. В результате была составлена таблица 1.
Таблица 1. Время на перевозку
Склад\Контора
Контора №1
Контора №2
Контора №3
Есть на складах
Склад №1
5
20
8
20
Склад №2
10
15
12
30
Потребность
15
12
20
47/50

Данная транспортная задача относится к типу задач с неправильным балансом (47<>50), но нас это не должно смущать. Я вас уверяю, мы ничего не будем решать вручную. Хотелось бы отметить, что в реальной жизни транспортные задачи с правильным балансом встречаются не очень часто. Далее задачу необходимо, как говорится, формализировать, т.е. записать в виде уравнений (формул). Пусть X - количество единиц товара, перевозимых из каждого склада в каждую контору. Тогда X11 - количество единиц товара, перевозимых из первого склада в первую контору, X12 - количество единиц товара, перевозимых из первого склада во вторую контору, и т.д. (такие предложения пишутся простым копированием, если вы не знали.;) Поскольку задача с неправильным балансом, то необходимо ввести также фиктивную контору. Все переменные представлены в таблице 2.
Таблица 2. Количество перевозимых товаров
Склад\Контора
Контора №1
Контора №2
Контора №3
Фиктивная
Есть на складах
Склад №1
X11
X12
X13
X14
20
Склад №2
X21
X22
X23
X24
30
Потребность
15
12
20
3
50/50

Теперь все готово для составления системы уравнений и целевой функции, определяющей время выполнения плана перевозок и направленной на минимум. По смыслу ясно, что количество единиц товара, привезенных с каждого склада в контору, в сумме должно равняться потребности этой конторы. Т.е.
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 десятков потребителей и поставщиков).
 
 
 
 
 
 
 
 
 
 

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

Содержание
Введение
§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 компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные ,,…, - потенциалы поставщиков; переменные ,…,- потенциалы потребителей.
Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем:  

В полученной двойственной задаче n·m ограничений, соответствующих каждой переменнойТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:
.
Неизвестные потенциалы и (их общее количество равно m + n) могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже).
 
для заполненных клеток (i,j) таблицы ТЗ.
Решение полученной системы (содержащей неизвестных на единицу больше, чем число уравнений) ищется, когда одно из неизвестных (вообще говоря, любое) полагается равным некоторому числу (тоже, вообще говоря, любому). После этого оставшаяся система имеет единственное решение.
 
§2. Пример решения Транспортной задачи
Метод потенциалов представляет из себя модификацию симплекс-метода, учитывающую специфику транспортной задачи, поэтому его алгоритм не отличается от алгоритма симплекс-метода, за исключением шага проверки целевой функции на неограниченность на множестве решений. Отсутствие указанного шага в методе потенциалов обусловлено теоремой о том, что закрытая ТЗ всегда разрешима. Итак, алгоритм метода потенциалов для решения ТЗ состоит из следующих шагов:
ШАГ 1. Построение начального плана перевозок.
ШАГ 2. Проверка текущего плана на оптимальность.
Если план оптимален, то алгоритм завершен.
ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.
Опишем алгоритм по шагам, иллюстрируя каждый шаг
ШАГ 1. Построение начального плана перевозок.
Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

Клетка ( i , j ) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.
Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:
а)число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);
б)сумма перевозок в любой строке должна быть равна запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перево
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.