Xreferat.com » Рефераты по информатике и программированию » Постановка и решение транспортной параметрической задачи

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ДИМИТРОВГРАДСКИЙ ИНСТИТУТ ТЕХНОЛОГИИ,

УПРАВЛЕНИЯ И ДИЗАЙНА

УЛЬЯНОВСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА


Кафедра математики и информационных технологий


КУРСОВАЯ РАБОТА

ТЕМА: Постановка и решение транспортной параметрической задачи


Выполнил:

задача № 25.7 (3)

Проверил: Бронз Г.А.


Димитровград 2005

Оглавление


Введение

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

2. Аналитический метод решения параметрической транспортной задачи

2.1 Методика нахождения исходного опорного решения задачи об оптимальных перевозках методом Фогеля

2.2 Проверка полученного опорного плана на оптимальность

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

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

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

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

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

4.3 Решение задачи аналитическим методом

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

Заключение

Библиографический список

Введение


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

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

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

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

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

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

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

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


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

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

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


Таблица 1.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


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


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


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

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

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

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


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


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


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

2. Аналитический метод решения параметрической транспортной задачи


2.1 Методика нахождения исходного опорного решения задачи об оптимальных перевозках методом Фогеля


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

1. В каждой строке и каждом столбце распределительной таблицы вычислить разности между всеми парами элементов (Cij) и выбрать минимальную.

2. Среди всех выбранных минимальных разностей Cij выбрать максимальное значение и выделить соответствующий столбец (строку).

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

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

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


2.2 Проверка полученного опорного плана на оптимальность


Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+n действительных чисел ui и vj, удовлетворяющих условиям ui+vj=cij для занятых клеток и ui + vj –cij ≤ 0 для свободных клеток.

Числа ui и vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ui.

Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал ui, то vj=cij–ui; если известен потенциал vj, то ui=cij-vj.

Обозначим ∆ij=ui+vj–cij. Эту оценку называют оценкой свободных клеток. Если ∆ij≤0, то опорное решение является оптимальным. Если хотя бы одна из оценок ∆ij>0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому [1].


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


Задача формулируется следующим образом: для всех значений параметра δ≤k≤φ где δ и φ – произвольные действительные числа, найти такие значения Постановка и решение транспортной параметрической задачи которые обращают в минимум функцию


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


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

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

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

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


Пользуясь методом потенциалов, (Фогеля) решаем задачу при k=δ до получения оптимального решения. Признаком оптимальности является условие:

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

и Постановка и решение транспортной параметрической задачи для занятых клеток,

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

Условие совместимости транспортной задачи запишется в виде


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


Значения aij и Bij определяются из условия


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


где Постановка и решение транспортной параметрической задачиопределяются из систем уравнений


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


Значения k находятся в пределах k1≤k≤k2:

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


если существует хотя бы одно Bij>0;

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


если все Bij≥0

если существует хотя бы одно Bij>0;

если все Bij≤0.

Алгоритм решения.

Задачу решаем при конкретном значении параметра k=δ до получения оптимального решения.

Определяем aij и Bij.

Вычисляем значение параметра k.

Если k>δ, производим перераспределение поставок и получаем новое оптимальное решение. Если k = δ, то процесс решения окончен [1].

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 Постановка параметрической транспортной задачи


Имеется четыре поставщика однородного груза с объемами поставок 100, 70, 70, 20 т. и три потребителя с объемами потребления 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=70

4.3 Решение задачи аналитическим методом


Полагая k=0, по известному алгоритму составим опорное решение методом Фогеля. Полученный опорный план перевозок и алгоритм выполнения с нахождением минимальных разностей стоимостей перевозок (Cij) в каждом столбце и строке изображен на рисунке 4.3.1.


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

Рис. 4.3.1. Составление первого опорного решения задачи по методу Фогеля


Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В3 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.1.

Решение, полученное при k=0, является оптимальным для всех значений параметра k, удовлетворяющих условию Постановка и решение транспортной параметрической задачи.

Из условия для свободных клеток найдем:


∆13 = v3 + u1 - c'13 = -1 + 2 - 2 = -1

∆21 = v1 + u2 - c'21 = 0 + 3 - 5 = -2

∆23 = v3 + u2 - c'23 = -1 + 3 - 6 = -4

∆32 = v2 + u3 - c'32 = 2 + 4 - 7 = -1

∆41 = v1 + u4 - c'41 = 0 + 2+k - 6 = -4 + k

∆42 = v2 + u4 - c'42 = 2 + 2+k - 8 = -4 + k


Табл. 4.3.1. Проверка первого опорного решения на оптимальность методом потенциалов

заполненные незаполненные
vi + uj = cij значения vi + uj ≤ cij условие
А1В1 v1+u1=2 v1=0, u1=2 А1В3 v3+u1<=2 соблюдается
А1В2 v2+u1=4 v2=2 А2В1 v1+u2<=5 соблюдается
A2B2 v2+u2=5 u2=3 А2В3 v3+u2<=6 соблюдается
A3B1 v1+u3=4 u3=4 А3В2 v2+u3<=7 соблюдается
A3B3 v3+u3=3 v3= -1 A4B1 v1+u4<=6 соблюдается
A4B3 v3+u4=1+k u4=2+k A4B2 v2+u4<=8 соблюдается

Определение значений k1 и k2:

k1 = max(-aij/Bij) = Постановка и решение транспортной параметрической задачи т.к. все Bij ≥ 0

k2 = min(-aij/Bij) = (-a41/B41; -a42/B42) = min(4;4) = 4. Все Bij > 0.

Так как по условию задачи k≥0, то оптимальное решение сохраняется при 0≥k≥4.

При этом минимальная стоимость транспортных расходов составляет:

F(X1)min = 20*(1+k) + 40*3 + 30*4 + 90*2 + 10*4 + 70*5 = 830 + 20k

Таким образом, при Постановка и решение транспортной параметрической задачи, F(X1)min = 830 + 20k и


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


Чтобы получить оптимальное решение при k≥4 перераспределим поставки товаров в клетку (4,1), где k2=4. Вновь полученное распределение с учетом изменения стоимости перевозки в ячейке A4B3 (k=4) представлено на рисунке 4.3.2.


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

Рис. 4.3.2. Составление второго опорного решения задачи по методу Фогеля


Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В1 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.2.


Табл. 4.3.2 Проверка второго опорного решения на оптимальность методом потенциалов

заполненные незаполненные
vi + uj = cij значения vi + uj ≤ cij условие
А1В1 v1+u1=2 v1=0, u1=2 А1В3 v3+u1<=2 соблюдается
А1В2 v2+u1=4 v2=2 А2В1 v1+u2<=5 соблюдается
A2B2 v2+u2=5 u2=3 А2В3 v3+u2<=6 соблюдается
A3B1 v1+u3=4 u3=4 А3В2 v2+u3<=7 соблюдается
A3B3 v3+u3=3 v3= -1 A4B2 v2+u4<=8 соблюдается
A4B1 v1+u4=6 u4=6 A4B3 v3+u4<=1+k соблюдается

Решение, полученное при k=4, является оптимальным для всех значений параметра k, удовлетворяющих условию Постановка и решение транспортной параметрической задачи.

Из условия для свободных клеток найдем:


∆13 = a3 + b1 - C'13 = -1 + 2 - 2 = -1

∆21 = a1 + b2 - C'21 = 0 + 3 - 5 = -2

∆23 = a3 + b2 - C'23 = -1 + 3 - 6 = -4

∆32 = a2 + b3 - C'32 = 2 + 4 - 7 = -1

∆42 = a2 + b4 - C'42 = 2 + 6 - 8 = 0

∆43 = a3 + b4 - (C'43 + С''43) = -1 + 6 - (1+k) = 4-k


Определение значений k1 и k2

k1 = max(-aij/Bij) = -a43/B43 = 4. Все Bij < 0

k2 = min(-aij/Bij) = Постановка и решение транспортной параметрической задачи т.к. все Bij ≤ 0

Так как по условию задачи k ≤ 9, то оптимальное решение сохраняется при 4≥k≥9.

При этом минимальная стоимость транспортных расходов составит:

F(X2)min = 20*6 + 60*3 + 10*4 + 90*2 + 10*4 + 70*5 = 910

Таким образом, при Постановка и решение транспортной параметрической задачи F(X2)min = 910 и


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


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


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


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

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


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

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: