Математическая модель транспортной задачи

Размещено на http://www.allbest.ru

Введение

Моделирование -- исследование объектов познания на их моделях; построение и изучение моделей реально существующих предметов, процессов или явлений с целью получения объяснений этих явлений, а также для предсказания явлений, интересующих исследователя.

Процесс моделирования включает три элемента:

? субъект (исследователь),

? объект исследования,

? модель, определяющую (отражающую) отношения познающего субъекта и познаваемого объекта.

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

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

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

Наблюдение, эксперимент, анализ и теоретическое обобщение - основные этапы изучения объектов.

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

Аналогия - суждение о каком-либо соответствии, частном сходстве объектов. Естественно, что аналогия связывает гипотезу с экспериментом.

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

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

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

Моделирование включает построение модели и исследование с ее помощью свойств реального объекта. Итак, моделирование представляет собой метод научного познания.

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

Цель проекта - найти опорный план транспортной задачи методом северо-западного угла. Определить оптимальный план методом потенциалов.

1. Этапы проектирования моделирующей системы

Процесс экономико-математического моделирования включает в себя три структурных элемента: объект исследования, субъект (исследователь), модель, опосредующую отношения между познающим субъектом и познаваемым объектом. Ниже представлена общая схема процесса моделирования:

1. Пусть имеется некоторый объект, который нужно исследовать методом моделирования. На первом этапе конструируем другой объект - модель исходного объекта-оригинала. Этап построения модели предполагает наличие определенных сведений об объекте - оригинале. Познавательные возможности модели определяются тем, что модель отображает лишь некоторые существенные черты исходного объекта, поэтому любая модель замещает оригинал в строго ограниченном смысле. Из этого следует, что для одного объекта может быть построено несколько моделей, отражающих определенные стороны исследуемого объекта или характеризующих его с разной степенью детализации.

2. На втором этапе процесса моделирования модель выступает как самостоятельный объект исследования. Например, одну из форм такого исследования составляет проведение модельных экспериментов, при которых целенаправленно изменяются условия функционирования модели и систематизируются данные о ее "поведении". Конечным результатом этого этапа является совокупность знаний о модели в отношении существенных сторон объекта-оригинала, которые отражены в данной модели.

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

4. На четвертом этапе осуществляются практическая проверка с помощью модели знаний и их использования, как для построения обобщающей теории реального объекта, так и для его целенаправленного преобразования или управления им. В итоге мы снова возвращаемся к проблематике объекта-оригинала.

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

2. Методы решения поставленной задачи

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

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

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

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

Математическая модель транспортной задачи

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

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

Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

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

Нахождение опорного плана.

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента».

Метод северо-западного угла (диагональный)

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

Метод наименьшего элемента

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

Алгоритм:

1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел.

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

3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Симплекс метод.

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) -- максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку -- требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

- нахождение исходной вершины множества допустимых решений,

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

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

Алгоритм:

Первый шаг.

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

Второй шаг

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+x_s=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' -- простые, а x' ' -- непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на B ? 1 слева: x'+B^?1Dx'' = B^?1b. Таким образом мы выразили простые переменные через непростые, и в выражении B^?1Ax+B^?1x_s, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Z?c^Tx= 0 равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент -- все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение .

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

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами -- входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор c_B в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу x''.

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

3. Описание среды реализации поставленной задачи

Инструментом реализации модели задачи является прикладная программа пакета Microsoft Office - Microsoft Office Excel 2007.

Microsoft Office Excel - это электронная таблица, самая распространенная и мощная технология для профессиональной работы с данными. В ячейках (клетках) таблицы могут быть записаны данные различных типов: текст, даты, числа, формулы, функции и др. Главное достоинство электронной таблицы - возможность мгновенного автоматического пересчета всех данных, связанных формульными зависимостями, при изменении значения любого компонента таблицы.

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

Функциональные возможности табличного процессора Excel.

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

Данная программа широко применяется во всех сферах экономических расчетов, и остается актуальной и востребованной по сей день.

Область применения Excel широка:

- благодаря тому, что лист Excel представляет из себя готовую таблицу, Excel часто используют для создания документов без всяческих расчётов, просто имеющих табличное представление (например, прайс-листы в магазинах, расписания);

- в Excel легко можно создавать различные виды графиков и диаграмм, которые берут данные для построения из ячеек таблиц (график снижения веса тела за указанный период от начала занятий спортом);

- его могут использовать обычные пользователи для элементарных расчетов (сколько потратил за этот месяц, что/кому/когда дал/взял);

- Excel содержит многие математические и статистические функции, благодаря чему его могут использовать школьники и студенты для расчетов курсовых, лабораторных работ;

- Excel интенсивно используется в бухгалтерии - во многих фирмах это основной инструмент для оформления документов, расчётов и создания диаграмм. Естественно, он имеет в себе соответствующие функции;

- Excel может даже работать как база данных.

4. Характеристика входной и выходной информации

На четыре базы А1, А2, А3, А4 поступил однородный груз в количествах, соответственно равных 180, 160, 140 и 220 единиц. Этот груз требуется перевезти в четыре пункта назначения В1, В2, В3, В4 соответственно в количествах 150, 250, 120 и 180 единиц. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения показаны далее (Таблица 2):

Таблица 2 - Входные данные

Выходной информацией является целевая функция равная 8040 единицам, указывающая, что определен оптимальный план перевозки груза (Таблица 3).

Таблица 3 - Выходные данные

Из получившихся результатов видим, что первый пункт отправления (А1) доставит 60 и 120 единиц груза соответственно в пункты назначения (В1 и B3). Второй пункт отправления (А2) доставит груз в пункты В1 и В4 в количестве 10, 150 соответственно. Третий пункт отправления (А3) доставит груз в пункты назначения В3в количестве 140 единиц. Четвертый пункт отправления (А4) доставит груз в пункты В2 и В4 в количестве 190, 30 соответственно.

5. Математическое описание задачи

Имеются следующие исходные данные.

Наличие однородного груза на базах (см. таблицу 2.1).

Таблица 2.1 - Наличие груза.

Базы	Наличие груза, единицы
А1	180
А2	160
А3	140
A4	220

Потребность в грузе на различных пунктах (см. таблицу 2.2).

Таблица 2.2 - Потребность в грузе.

Пункты	Потребность в грузе, единицы
В1	150
В2	250
В3	120
В4	180

Расстояния между складами и пунктами доставки (см. таблицу 2.3).

Таблица 2.3 - Расстояния между пунктами доставки.

	В1	В2	В3	В4
А1	18	2	3	12
А2	3	4	8	7
А3	4	5	6	12
A4	7	1	5	6

Таблица 2.4 - опорное решение (метод мин. элемента)

Е = 2*30+3*120+12*30+3*150+7*10+12*140+1*220=3200 ден. ед.

Цикл 1.

Шаг 1. Составим систему уравнений для определения платежей по формуле: U_i+V_j=C_ij, где C_ij - это стоимость перевозок соответствующая Базисным переменным. U_i - платежи (потенциалы поставщиков), V_j - платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2

U2+V3=3

U1+V4=12

U2+V1=3

U2+V4=7

U3+V4=12

U4+V2=1

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V2=2

V3=3

V1=8

U2=-5

V4=12

U4=-1

U3=0

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):



Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:

Шаг 5. Если для всех величин D_ij выполняется условие D_ij ? 0 то оптимальное решение найдено. Если имеются D_ij ? 0 то выполняется следующий шаг.

Шаг 6. Определяется переменная для включения в Базис. Для этого выбирается переменная, которая соответствует максимальному по модулю отрицательному элементу D_ij. В этой ячейке ставится знак «+» т.е. обязательно должны выполняться перевозки от i - поставщика к j - потребителю. Так как максимальный по модулю D₃₄= -5, то переменная х₃₄ включается в Базис.

Шаг 7. Определяется переменная для исключении из Базиса, для чего строится цикл. Минимальная из х_ij помеченных знаком «-» при построении цикла исключаются из Базиса и обозначаются х_rs. В нашем случае х_rs=х₁₄=30.

Шаг 8. Определим новый план перевозок. Все переменные помеченные знаком «+» увеличиваем на величину х_rs, а знаком «-» уменьшаем.

Таблица 2.5 - Оптимизированный план.

Е = 2*60+3*120+12*30+3*150+7*10+12*140+1*190+6*30=2870 ден.ед.

Цикл 2.

Шаг 1. Составим систему уравнений для определения платежей по формуле: U_i+V_j=C_ij, где C_ij - это стоимость перевозок соответствующая Базисным переменным. U_i - платежи (потенциалы поставщиков), V_j - платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2

U1+V3=3

U4+V4=6

U2+V1=3

U2+V4=7

U3+V4=12

U4+V2=1

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V2=2

V3=3

V1=3

U2=-0

V4=7

U4=-1

U3=5

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):

Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:



Шаг 5. Если для всех величин D_ij выполняется условие D_ij ? 0 то оптимальное решение найдено. Если имеются D_ij ? 0 то выполняется следующий шаг.

Шаг 6. Определяется переменная для включения в Базис. Так как максимальный по модулю D₃₁= -4, то переменная х₃₁ включается в Базис.

Шаг 7. Определяется переменная для исключении из Базиса. В нашем случае х_rs=х₃₄=140.

Шаг 8. Определим новый план перевозок. Все переменные помеченные знаком «+» увеличиваем на величину х_rs, а знаком «-» уменьшаем.

Таблица 2.6 - Оптимизированный план.

Е = 2*30+3*120+12*30+3*10+7*150+4*140+1*190+6*30=2490 ден.ед.

Цикл 3.

Шаг 1. Составим систему уравнений для определения платежей по формуле:

U_i+V_j=C_ij,

где C_ij - это стоимость перевозок соответствующая Базисным переменным. U_i - платежи (потенциалы поставщиков), V_j - платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2

U1+V3=3

U2+V1=3

U2+V4=7

U3+V1=4

U4+V2=1

U4+V4=6

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V3=3

V4=7

V1=2

V2=2

U2=0

U4=-1

U3=1

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):



Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:

Шаг 5. Так как для всех величин D_ij выполняется условие D_ij ? 0 то оптимальное решение найдено.

Размещено на Allbest.ru

...