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

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

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



Введение

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

В общем виде задачу можно представить следующим образом: в 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. Запишем условия задачи в распределительную таблицу, которую будем использовать для нахождения решения (таблица. 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. Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (C_ij) (рисунок 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 Математическая модель задачи

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

.

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

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

X_ij?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. При этом в клетке A₄B₃ матрицы «Стоимость перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от параметра k: L7=1+L9.

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

В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: 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(x₁)_min=830.

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

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

Полученное значение целевой функции F(x₂)_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(x₁)_min = 830, (k=0);

F(x₂)_min = F(x₁)_min +20 = 830+20, (k=1);

F(x₃)_min = F(x₂)_min +20 = 830 + 20*2 = 870, (k=2).

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

F(x₄)_min = 830 + 20*3, (k=3).

F(x₅)_min = 830 + 20*4, (k=4).

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

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

.

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

Ответ.

, , F(X₁)_min = 830 + 20k.

, , F(X₂)_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