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

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

 

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

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

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

 

 

 

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

 

 

 

 

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

 

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

 

 

 

 

 

 

Выполнил:                                                                      

задача № 25.7 (3)

 

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

 

 

 

 

 

 

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

 

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ………………………………………………………………………	3
Математическая постановка задачи об оптимальных перевозках………………………………………………………………..	5
аналитический метод решения параметрической транспортной задачи
Методика нахождения исходного опорного решения задачи об оптимальных перевозках методом Фогеля ………………………………	6
Проверка полученного опорного плана на оптимальность ………..	6
Методика решения параметрической транспортной задачи ………	7
Метод решения задачи об оптимальных перевозках средствами Ms Excel ………………………………………………...	8
РЕШЕНИЕ ПАРАМЕТРИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ
Постановка параметрической транспортной задачи ……………….	10
Математическая модель задачи ……………………………………...	10
Решение задачи аналитическим методом …………………………...	11
Решение задачи средствами Ms Excel ……………………………….	14
ЗАКЛЮЧЕНИЕ …………………………………………………………………	19
БИБЛИОГРАФИЧЕКИЙ СПИСОК …………………………………………...	20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

В общем виде задачу можно  представить следующим образом: в m пунктах производства A₁, A₂, …, A_m имеется однородный груз в количестве соответственно a₁, a₂, …, a_m. Этот груз необходимо доставить в n пунктов назначения B₁, B₂, …, B_n в количестве соответственно b₁, b₂, …, b_n. Стоимость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

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

Обозначим через x_ij количество груза, перевозимого из пункта Ai, в пункт B_j. Запишем условия задачи в распределительную таблицу, которую будем использовать для нахождения решения (табл. 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. В каждой строке  и каждом столбце распределительной таблицы вычислить разности между всеми парами элементов (C_ij) и выбрать минимальную.

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

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

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

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

 

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

 

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

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

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

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

 

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

 

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

 

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

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

 

Xij≥0,

 

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

 для незанятых клеток

и для занятых клеток,

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

 

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

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

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

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

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

если все B_ij≥0

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

если все B_ij≤0.

 

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

1. Задачу решаем при конкретном значении параметра k=δ до получения оптимального решения.
2. Определяем a_ij и B_ij.
3. Вычисляем значение параметра k.
4. Если k>δ, производим перераспределение поставок и получаем новое оптимальное решение. Если k = δ, то процесс решения окончен [1].

 

 

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

 

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

 

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

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