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

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

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 21.10.2014
Размер файла 802,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

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

Введение

математический перевозка транспортный компьютерный

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

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

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

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

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

Цель курсовой работы - продемонстрировать на конкретном примере решение задачи линейного программирования (ЗЛП), приобрести навыков решения задач линейного программирования в табличном редакторе Microsoft Excel.

Задачи работы обусловлены ее целью:

Во-первых, раскрыть теоретическое содержание данной темы.

Во-вторых, сформулировать и найти оптимальное решение задач с помощью средств MS Excel.

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

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

1. Описание метода потенциалов

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

Метод потенциалов впервые предложили Л.В. Канторович и М.К. Гавурин в 1949 г. Позже аналогичный метод разработал Г. Данциг, исходя из общих идей ЛП.

Общая схема метода такова.

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

Описание алгоритма метода потенциалов.

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

· Проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

· Находится опорный план перевозок путем составления 1-й таблицы;

· Проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью «0»;

· Для опорного плана определяются потенциалы ui и vj, соответствующие базисным клеткам, по условию: ui + vj = cij

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

· После этого для небазисных клеток опорного плана определяются оценки cij, где cij =ui + vj - cij

При этом если cij Ј0, то опорный план оптимален, если же среди cij окажется хотя бы один положительный элемент, то опорный план можно улучшить.

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

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

Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «-» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.

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

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

Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой.

Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

а) в качестве начальной небазисной переменной принимается та, у которой оценка cij имеет максимальное значение;

б) составляется цикл пересчета;

в) находится число перерасчета по циклу: число X=min{Xij}, где Xij - числа в заполненных клетках со знаком «-»;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

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

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

В общем виде задачу можно представить следующим образом: в m пунктах производства A1, A2, …, Am имеется однородный груз в количестве соответственно a1, a2, …, am. Этот груз необходимо доставить в n пунктов назначения B1, B2, …, Bn в количестве соответственно b1, b2, …, bn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.

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

Обозначим через xij количество груза, перевозимого из пункта Ai, в пункт Bj. Запишем условия задачи в распределительную таблицу, которую будем использовать для нахождения решения (таблица. 2.1).

Таблица 2.1. Модель распределительной таблицы

Bi

Ai

B1

B2

Bj

Bn

b1

b2

bi

bn

A1 a1

c11

x11

c12

x12

с1j

x1j

c1n

x1n

A2 a2

c21

x21

c22

x22

c2j

x2j

c2n

x2n

Ai ai

ci1

xi1

ci2

xi2

cij

xij

cin

xin

Am am

cm1

xm1

cm2

xm2

cmj

xmj

cmn

xmn

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

при ограничениях:

Оптимальным решением задачи является матрица

удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

3. Метод решения задачи об оптимальных перевозках средствами Ms Excel

Нахождение оптимального плана перевозок с применением компьютерной программы Ms Excel осуществляется посредством функции «Поиск решения».

Схема выполнения:

1. Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (Cij) (рисунок 3.1.), а также матрицу, которая должна будет отображать искомый план перевозок (рисунок. 3.2.).

Рисунок 3.1 - Фрагмент окна программы Ms Excel: Модель таблицы «Стоимость перевозок».

2. В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.

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

Рисунок 3.2 - Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок»

4. В ячейке целевой функции ввести формулу, высчитывающую сумму произведений элементов матрицы «Стоимость перевозок» и соответствующих элементов матрицы «План перевозок».

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

6. В диалоговом окне «Параметры поиска решения» установить параметр «Линейная модель» и число итераций, равное 100.

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

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

4. Решение параметрической транспортной задачи

4.1 Постановка параметрической транспортной задачи

Имеется четыре поставщика: A1 - ОАО» Катрен», A2 - ОАО «СИА ИНТЕРНЕЙШЕНЛ», A3 - ЗАО «ПрофитМед», A4 - ЗАО» Роста» однородного груза лекарственных препаратов с объемами поставок 100, 70, 70, 20 т. и три потребителя: B1 - ООО «Родник», B2 - «36,6», B3 - «Будь здоров» с объемами потребления 120, 80, 60 т. Стоимость транспортных расходов задана матрицей

причем стоимость перевозки груза от четвертого поставщика до третьего потребителя изменяется в диапазоне 0?k?9.

Определить оптимальный план перевозок, обеспечивающий минимальные транспортные расходы.

Изобразим матричную запись задачи (таблица. 4.1.1)

Таблица 4.1.1 - Матричная запись задачи

Bj

Ai

B1

B2

B3

120

80

60

A1

100

2

4

2

X11

X12

X13

A2

70

5

5

6

X21

X22

X23

A3

70

4

7

3

X31

X32

X33

A4

20

6

8

1+k

X41

X42

X43

4.2 Математическая модель задачи

Целевая функция

.

где Xij - объем поставок груза,

при ограничениях:

Xij?0,

Подробные ограничения по потребностям и запасам каждого потребителя и поставщика соответственно отражены в Таблице 4.2.1.

Таблица 4.2.1 - Ограничения по потребностям и запасам

По потребностям

По запасам

B1

X11+X21+X31+X41=120

A1

X11+X12+X13=100

B2

X12+X22+X32+X42=80

A2

X21+X22+X23=70

B3

X13+X23+X33+X43=60

A3

X31+X32+X33=70

A4

X41+X42+X43=20

4.3 Решение задачи средствами Ms Excel

Создадим в окне программы Ms Excel две матрицы «План перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис 4.3.1). Также нужно указать ячейку содержащую изменяемый параметр k. При этом в клетке A4B3 матрицы «Стоимость перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от параметра k: L7=1+L9.

Рисунок 4.3.1 - Фрагмент окна программы Ms Excel: Матрицы «План перевозок» и «Стоимость перевозок» с изменяемым тарифом C43

В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ (C4:E4), C3=СУММ (С4:С7).

В ячейку целевой функции (N7) введем =СУММПРОИЗВ (C4:E7; J4:L7).

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

В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения и ссылки на необходимые ячейки (рис. 4.3.2). Также необходимо в ограничениях указать пределы изменения параметра k, т.е. 0?k?9.

Рисунок 4.3.2 - Диалоговое окно «Поиск решения»

В диалоговом окне «Параметры поиска решения» установить необходимые параметры (рис. 4.3.3).

Рисунок 4.3.3 - Диалоговое окно «Параметры поиска решения»

После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» (рис. 4.3.5) нажать «Сохранить сценарий…» и в появившемся диалоговом окне «Сохранение сценария» задать имя данному сценарию и нажать «ОК» (рис. 4.3.4.).

Рисунок 4.3.4 - Диалоговое окно «Сохранение сценария»

После сохранения сценария в диалоговом окне «Результаты поиска решения» выделить необходимые типы отчетов и нажать «OK» (рисунок. 4.3.5.).

Рисунок 4.3.5 - Диалоговое окно «Результаты поиска решений

После выполнения всех операций в матрице «План перевозок» получим оптимальный план перевозок при k=0 (рисунок 4.3.6.).

Рисунок. 4.3.6 - Фрагмент окна программы Ms Excel: Результат поиска решения при k=0

Полученное значение целевой функции F(x1)min=830.

Теперь аналогичным способом найдем оптимальный план перевозок при k=1. Проведя повторный расчет, получим новый план перевозок и значение целевой функции (рисунок 4.3.7.).

Рисунок 4.3.7 - Фрагмент окна программы Ms Excel: Результат поиска решения при k=1

Полученное значение целевой функции F(x2)min = 850.

Как видно из рисунков 4.3.5. и 4.3.6 планы перевозок в обоих случаях (k=0, k=1) одинаковы. После дальнейших расчетов при всех остальных значениях параметра k обнаружим, что при план перевозок остается неизменным, изменяется лишь значение целевой функции. При значении параметра «Поиск решения» выдает другой план перевозок, и значение целевой функции на данном промежутке остается неизменным F(x)min = 910. Полученный план перевозок при значении k=4 изображен на рисунке 4.3.8.

Рисунок 4.3.8 - Фрагмент окна программы Ms Excel: Результат поиска решения при k=4

Значения целевой функции, соответствующие параметру k в каждой итерации представлены в таблице 4.3.1.

Из представленных в таблице 4.3.1 данных можно вывести определенную закономерность изменения значения целевой функции на промежутке :

F(x1)min = 830, (k=0);

F(x2)min = F(x1)min +20 = 830+20, (k=1);

F(x3)min = F(x2)min +20 = 830 + 20*2 = 870, (k=2).

Следуя по той же цепочке, найдем:

F(x4)min = 830 + 20*3, (k=3).

F(x5)min = 830 + 20*4, (k=4).

Исходя из подобной логики можно представить F(x1)min = 830 + 20*0.

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

.

Для значений значение функции постоянно F(x)=910.

Ответ.

, , F(X1)min = 830 + 20k.

, , F(X2)min = 910.

Таблица 3.3.1 - Значения целевой функции в каждой итерации

номер итерации i

значение параметра ki

значение функции F(xi)min

1

0

830

2

1

850

3

2

870

4

3

890

5

4

910

6

5

910

7

6

910

8

7

910

9

8

910

10

9

910

Команда «Сервис > Сценарии» открывает диалоговое окно «Диспетчер сценариев», которое отображает сохраненные сценарии каждой итерации нахождения оптимального плана перевозок (рис 4.3.9.).

Рисунок 4.3.9 - Диалоговое окно «Диспетчер сценариев»

С помощью «Диспетчера сценариев» можно просмотреть план перевозок и значение целевой функции, получаемые при каждом значении параметра k. Также можно просмотреть отчет, отображающий значения изменяемых ячеек в каждой из итераций.

Заключение

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

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

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

Во-первых, раскрыть теоретическое содержание данной темы.

Во-вторых, сформулировать и найти оптимальное решение задач с помощью средств MS Excel.

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

Используемая литература

1. Кудинов Ю.И. Практическая работа в Excel: Учебное пособие. - Липецк: ЛГТУ, 2001. - 67 с.

2. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. - 3-е изд., исп. - М.: Дело, 2002. - 688 с.

3. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. Издательство «Советское радио» Москва -1961

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 1979 г.

5. Т.Н. Павлова, О.А. Ракова. Решение задач линейного программирования средствами Excel. Учебное пособие, 2002 г.

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


Подобные документы

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

    контрольная работа [551,9 K], добавлен 27.08.2009

  • Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.

    задача [58,6 K], добавлен 16.02.2016

  • Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.

    курсовая работа [1,0 M], добавлен 12.01.2011

  • Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.

    курсовая работа [541,3 K], добавлен 08.10.2015

  • Применение метода дополнительного аргумента к решению характеристической системы. Доказательство существования решения задачи Коши. Постановка задачи численного расчёта. Дискретизация исходной задачи и её решение итерациями. Программа и её описание.

    дипломная работа [5,7 M], добавлен 25.05.2014

  • Математическое моделирование и особенности задачи распределения. Обоснование и выбор метода решения. Ручное решение задачи (венгерский метод), а также с использованием компьютера. Формулировка полученного результата в сопоставлении с условием задачи.

    курсовая работа [383,9 K], добавлен 26.05.2010

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

    курсовая работа [64,6 K], добавлен 19.12.2009

  • Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.

    контрольная работа [23,5 K], добавлен 12.06.2011

  • Целочисленные задачи математического программирования. Постановка транспортной задачи по критерию стоимости в матричной форме. Задача о назначении (проблема выбора, задача о женихах и невестах). Алгоритм метода Гомори. Формирование правильного отсечения.

    курсовая работа [868,8 K], добавлен 05.12.2012

  • Метод разделения переменных в задаче Штурма-Лиувилля. Единственность решения смешанной краевой задачи, реализуемая методом априорных оценок. Постановка и решение смешанной краевой задачи для нелокального волнового уравнения с дробной производной.

    курсовая работа [1003,8 K], добавлен 29.11.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.