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

по дисциплине «Методы оптимизации в управлении»

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

 

 

 

 

 

Москва 2013

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

Цель курсовой работы – продемонстрировать на конкретном примере решение задачи линейного программирования (ЗЛП), приобрести навыков решения задач линейного программирования в табличном редакторе 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г.