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

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

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

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

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

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

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

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

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

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

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

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

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

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 — Матричная запись задачи

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

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

.

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

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

X_ij?0,

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

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

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 — Значения целевой функции в каждой итерации

Команда «Сервис > Сценарии» открывает диалоговое окно «Диспетчер сценариев», которое отображает сохраненные сценарии каждой итерации нахождения оптимального плана перевозок (рис 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 г.