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

В 1930 г. впервые прозвучала постановка задачи линейного программирования в работах советского экономиста А. Н. Толстого, имеющая вид предложения по составлению такого плана перевозки груза между пунктами, чтобы общий пробег транспорта был наименьшим; основы математического аппарата для решения экономических задач линейного программирования были созданы в 1939 г. академиком Л. В. Канторовичем и его учениками.

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

Также транспортная задача применяется при решении экономических задач, которые по своему характеру не имеют ничего общего с транспортировкой груза. К задачам такого типа относят:

· Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега;

· Оптимальное закрепление за станками операций по обработке деталей;

· Оптимальное назначения, или проблема выбора;

· Задачи размещения с учетом транспортных и производственных затрат.

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

· Метод северо-западного угла;

· Метод минимальной стоимости;

· Метод двойного предпочтения;

А оптимальный план находится с помощью следующих методов:

· Метод потенциалов;

· Дельта-метод решения транспортной задачи;

В данной курсовой работе используется для нахождения опорного плана используется метод двойного предпочтения. Для определения оптимального плана — метод потенциалов.

оптимальный план минимизация перевозка

1. ПОСТАНОВКА ЗАДАЧИ Нефтеперерабатывающий завод получает 4 вида полуфабрикатов: 200 тыс. литров алкилата, 350 тыс. литров бензина прямой перегонки, 250 тыс. литров крекинг бензина, 100 тыс. литров изопентана.

В результате смешивания этих 4-ех компонентов в разных пропорциях образуется 3 сорта авиационного бензина:

Бензин А-2:3:5:2

Бензин В-3:1:2:1

Бензин С-2:2:1:3

Стоимость 1 тыс. литров указанных сортов бензина характеризуется числами: А-120 руб. В-100руб, С-150 руб.

Таблица 1

Определить план смешивания компонентов, при котором будет достигнута максимальная стоимость всей продукции.

Задачу решить симплексным методом, используя язык программирования Turbo C и реализовать на ПЭВМ IBM PC 486

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ Математическая модель в общем виде:

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

Вводятся обозначения для искомой задачи:

m — вид полуфабрикатов,

n — сорта бензина,

a_i — пропорциональное содержание полуфабрикатов в бензине,

b_j — ограничения полуфабрикатов в бензине, тыс.л.

С_ij — стоимость бензина,

x_ij — объем выпуска бензина,

Z — минимальная стоимость всей продукции.

Математическая модель данной ЗЛП:

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

3. МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ Поставлена задача линейного программирования. Найти максимальное значение функции

Z=C1X1+C2X2+…+CnXn

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

a11×1+a12×2+…+a1nxn=b1

a21×1+a22×2+…+a2nxn=b2

…

am1x1+am2x2+amnxn=bm

xj?0(j=1,2,…n)

bi?0(i=1,2,…m)

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

Z=C1X1+C2X2+…+CnXn

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

x1+a1,m+1 xm+1+…+a1nxn=b1

x2+a2,m+1 xm+1+…+a2nxn=b2

…

xm+am, m+1+xm+1+…+amnxn=bm

xj?0(j=1,2,…n)

Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов, чтобы значения линейной формы в задачах на минимум уменьшалось при переходе от одного опорного плана к другому, число шагов для достижения этой цели m? k?2m, где m-число уравнений или размеренность базиса.

Заполняется исходная таблица. После чего производится вычисления в последовательности:

— Подсчитывается Zj-Cj и определяется, не является ли рассматриваемый план оптимальным, т. е. не выполняется ли для всех xj условие: Zj-Cj?0

— Если для некоторого значение ZjCj>0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь, для которого max (Zj-Cj)=Zk-Ck>0, тогда Pk вводится в базис.

— Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: для всех xik>0, тогда Piисключается из базиса.

— Если все, то линейная форма неограниченна снизу.

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

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

Вычисления сводятся в табл.2

Таблица № 2

4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

4.1 Вводятся А, В, С

4.2 Заполняется симплексная таблица

4.3 Вычисляется базис

4.4 Находится опорный план и Z0

4.5 Проверяется условие в (m+1) — строки Zj-Cj<=0 на min

4.6 Если условие выполняется, то выполняется переход на пункт 4.10

4.7 Выбирается вектор Pk по max (Zj-Cj)=Zk-Ck>0

4.8 Выбирается вектор Pl, подлежащий исключению из базиса для которого: для всех xik>0

4.9 Таблица преобразуется продолжением полного исключения и переход на пункт 4.4

4.10 Печать Xopt и Zopt

5. ВЫЧИСЛИТЕЛЬНАЯ СХЕМА Находится первоначальный опорный план методом двойного предпочтения.

Таблица 4

.

Решение данной задачи осуществляется методом потенциалов.

Таблица 5

.

Таблица 6

.

Таблица 7

Так как, то получается оптимальный план на третьем шаге.

.

6. БЛОК-СХЕМА

7. ПРОГРАММА Данная задача линейного программирования реализована посредством MS Excel. Для этого используется процедура Excel «Поиск решения»,

где:

· Установить целевую ячейку — служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу:

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

o Изменяя ячейки — служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку;

o Предположить — используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки;

o Ограничение — служит для отображения списка граничных условий поставленной задачи;

o Добавить — используется для отображения диалогового окна Добавить ограничение;

o Изменить — применяется для отображения диалогового окна Изменить ограничение;

o Удалить — служит для снятия указанного ограничения;

o Выполнить — используется для запуска поиска решения поставленной задачи;

o Закрыть — служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить;

o Параметры — применяется для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения;

o Восстановить — служит для очистки полей окна диалога и восстановления значений параметров по умолчанию.

8. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

8.1 Включить ЭВМ.

8.2 Запустить прикладную программу MS Excel.

8.3 Открыть новый рабочий лист (Вставка/Лист).

8.4 В ячейки диапазона А1: Е4 разместить таблицу стоимости перевозок.

8.5 В ячейки диапазона А10: Е10 ввести следующие формулы:

А10 = СУММ (А6:А9)

В10 = СУММ (В6:В9)

С10 = СУММ (С6:С9)

D10 = СУММ (D6:D9)

Е10 = СУММ (Е6:Е9)

8.6 В ячейки диапазона F6: F10 ввести следующие формулы:

F6 = СУММ (А6: E6)

F7 = СУММ (А7: E7)

F8 = СУММ (А8: E8)

F9 = СУММ (А9: E9)

8.7 В ячейки диапазона G6: G9 ввести значения соответствующие запасам на складах.

8.8 В ячейки диапазона А11: Е11 ввести значения соответствующие потребностям на птредприятиях.

8.9 В ячейку F10 ввести формулу целевой функции = СУММПРОИЗВ (A1:E4;A6:E9).

8.10 Выбрать на панели инструментов Данные/Анализ/Поиск решения.

8.11 Установить целевую ячейку содержащую оптимизируемое значение (F10).

8.12 Установить переключатель Равной минимальному значению, т.к. в поставленной задаче требуется вычислить минимальный объем затрат.

8.13 В поле Изменяя ячейки задать диапазон подбираемых параметров ($A$ 6:$E$ 9).

8.14 Определить набор ограничений. Для этого щелкнуть на кнопке Добавить и ввести следующие ограничения $A$ 10:$E$ 10 = $A$ 11:$E$ 11, $A$ 6:$E$ 9 = целое, $A$ 6:$E$ 9 >= 0, $F$ 6:$F$ 9 = $G$ 6:$G$ 9.

8.15 Щелкнуть на кнопке Выполнить.

8.16 В диалоговом окне Результаты поиска решения установить переключатель в положение Сохранить найденное решение.

8.17 Полученные результаты вывести на печать.

9. РЕЗУЛЬТАТ СЧЕТА ПО ПРОГРАММЕ Результат вычислений:

Оптимальный план:

Целевая функция: Z_опт = 956.

10. ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ В результате решения транспортной задачи по минимизации затрат на перевозку товаров с четырех складов на пять предприятий был получен оптимальный план:

Чтобы затраты на перевозку товара с четырех складов на пять предприятий были минимальны, необходимо таким образом спланировать перевозки:

На первое предприятие 40 т товара с четвертого склада.

На второе предприятие 5 т товара с первого склада и 35 т с четвертого склада.

На третье предприятие 9 т товара с первого склада и 11 т с третьего склада.

На четвертое предприятие 10 т товара с четвертого склада.

На пятое предприятие 25 т товара со второго склада и 5 т с третьего склада.

При таком плане стоимость перевозок составляет 956 рублей.

В результате оптимизации плана получена экономия Z_о — Z_опт =

= 1108 — 56 = 152 рубля.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Ю.Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко «Математическое программирование» М. «Высшая школа», 1980 г.

С.А. Соколицин «Применение математических методов в экономике и организации машиностроительного производства» Л, «Машиностроение», 1970 г.

ЕСПД Схема алгоритмов и программ ГОСТ 19.002 — 80, ГОСТ 19.003−80, издательства стандартов, 1980 г.

Методические указания к курсовой работе по дисциплине «Математические методы», Таганрог, ТАК, 2010 г.