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

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

Введение

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

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

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

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

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

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

Цель курсовой работы - продемонстрировать на конкретном примере решение задачи линейного программирования (ЗЛП), приобрести навыков решения задач линейного программирования в табличном редакторе 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 AiB1B2…Bj…Bnb1b2…bi…bnA1 a1c11 x11c12 x12…с1j x1j…c1n x1nA2 a2c21 x21c22 x22…c2j x2j…c2n x2n…………………Ai aici1 xi1ci2 xi2…cij xij…cin xin…………………Am amcm1 xm1cm2 xm2…cmj xmj…cmn xmn

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 AiB1B2B31208060A1100242X11X12X13A270556X21X22X23A370473X31X32X33A420681+kX41X42X43

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

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

.

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

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

Xij?0,

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

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

По потребностямПо запасамB1X11+X21+X31+X41=120A1X11+X12+X13=100B2X12+X22+X32+X42=80A2X21+X22+X23=70B3X13+X23+X33+X43=60A3X31+X32+X33=70A4X41+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);(x3)min = F(x2)min +20 = 830 + 20*2 = 870, (k=2).

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

F(x4)min = 830 + 20*3, (k=3).(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)min108302185032870438905491065910769108791098910109910

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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