Содержание Введение1. Формулировка проблемы в практической области2. Построение моделей транспортной задачи3. Реализация алгоритма программы
Руководство пользователя
Заключение
Список используемой литературы
Введение
Линейноепрограммирование (ЛП) — наука о методах исследования и нахождения экстремумов линейнойфункции, на неизвестные которой наложены линейные ограничения. То есть, задачалинейного программирования, это нахождение минимального или максимальногозначения линейной функции с учётом системы из линейных уравнений-ограничений.Всё вместе это даёт математическую модель, какого-либо экономического процесса.
Экономико-математическаямодель — этоматематическое описание экономического процесса или объекта. Такие моделииспользуются для исследований и анализа экономических процессов.
Все задачи линейного программирования можно разделить наследующие группы:
· задачи обиспользовании ресурсов, сырья, планирования производства;
· задачисоставления рациона
· Задачи обиспользовании мощностей, загрузке оборудования
· Задачи о раскроематериалов
· Транспортныезадачи
Их рассмотрение здесь неприведено, так как не является необходимым для данного проекта.
Но надо представлятьобщую задачу линейного программирования (ОЗЛП), так как для составленияалгоритма необходимо понимать математический смысл решения задачи. Ниже,приведено математическое описание общего вида задачи линейногопрограммирования. Геометрическиобласть допустимых решений такой задачи можно представить как многогранник в nмерном пространстве
/>
Пример геометрическогопредставления области допустимых решений задачи, где F — линия целевой функции,F=0 начальное положение функции, F=Fmax оптимальное положениефункции, A, B, C, D, E — вершины многоугольника.
Причём, как правило,оптимальное решение это одна из его вершин. А поиск оптимума выражается впереходе от одной вершины к другой и выборе оптимальной.
Рассмотрена основная теоремы линейного программирования, изкоторой следует, что если задача линейного программирования имеет оптимальноерешение, то оно соответствует хотя бы одной угловой точке многогранника решенийи совпадает, по крайней мере, с одним из допустимых базисных решений системыограничений. Там же был указан путь решения любой задачи линейногопрограммирования: перебрать конечное число допустимых базисных решений системыограничений и выбрать среди них то, на котором функция цели принимаетоптимальное решение. Геометрически это соответствует перебору всех угловыхточек многогранника решений. Такой перебор в конце концов приведет коптимальному решению (если оно существует), однако его практическоеосуществление связано с огромными трудностями, так как для реальных задач числодопустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых допустимых базисных решений можносократить, если производить перебор не беспорядочно, а с учетом измененийлинейной функции, т.е. добиваясь того, чтобы каждое следующее решение было«лучше» (или, по крайней мере, «не хуже»), чем предыдущее,по значениям линейной функции (увеличение ее при отыскании максимума F-> max, уменьшение — при отыскании минимума F-> min).
1. Формулировкапроблемы в практической области
Отимизация выбора распределение(транспортировка) продукции, находящейся на складах, попредприятиям-потребителям с целью, определения наиболее экономичного планаперевозки продукции одного вида из нескольких пунктов отправления впункты их назначения.
Цель работы – определение метода расчета планаперевозки продукции со
склада попредприятиям-потребителям, при котором обеспечивается минимальные транспортныерасходы на перевозку всей продукции.Формальная(математическая постановка задач)
Задача о размещении(транспортная задача) Это задача, в которой работы и ресурсы измеряются водних и тех же единицах. В таких задачах ресурсы могут быть разделены междуработами, и отдельные работы могут быть выполнены с помощью различныхкомбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) являетсяраспределение (транспортировка) продукции, находящейся на складах, попредприятиям-потребителям. Дана система из m линейных уравнений и неравенств сn переменными:
a11x1+a12x2+…+a1nxn≤ b1
a21x1+a22x2+…+a2nxn≤ b2
ak1x1+ak2x2+…+aknxn≤ bk
am1x1+am2x2+…+amnxn≤ bm1
и линейная функция
F=c1x1+c2x2+…+cnxn (2)
Необходимо найти такоерешение (план) системы
X=(x1,x2….,xj….,xn) (3)
где
xj
при котором линейнаяфункция F (2) принимает оптимальное), есть максимальное или минимальное взависимости от задачи) значение. При этом система (1) — система ограничений, а функция F (2) — целевая функция (функция цели).Анализпостановки задач и обоснования метода решенияАнализируя исходные условия задачи, следует отнести ее кзадачам линейного программирования, в частности, к задачам о принятиирешений… Наша задача является однокритериальной так как у нас представленыскалярные величины Для решения задачи по оптимальному плану перевозки продукцииисользуем метод решения транспортных задач методом потенциалов.2. Построение моделей транспортнойзадачи
задачапрограмма модель
Теоретическоевведение. Задача о размещении (транспортная задача) –это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. Втаких задачах ресурсы могут быть разделены между работами, и отдельные работымогут быть выполнены с помощью различных комбинаций ресурсов. Примером типичнойтранспортной задачи (ТЗ) является распределение (транспортировка) продукции,находящейся на складах, по предприятиям-потребителям.
Стандартная транспортнаязадача определяется как задача разработки наиболее экономичного плана перевозкипродукцииодного вида из нескольких пунктов отправления в пунктыназначения. При этом величина транспортных расходов прямо пропорциональнаобъему перевозимой продукции и задается с помощью тарифов на перевозку единицыпродукции
Особенностиэкономико-математической модели транспортной задачи:
— система ограниченийесть система уравнений (т.е. транспортная задача задана в канонической форме);-коэффициенты при переменных системы ограничений равны единице или нулю;- каждаяпеременная входит в систему ограничений два раза.
Критерий оптимальности формулируется следующим образом: базисноераспределение поставок оптимально тогда и только тогда, когда оценки всехсвободных клеток неотрицательны. Циклом в матрице называется ломаная свершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы,удовлетворяющую условиям:
· ломаная должнабыть связной, т.е. из любой ее вершины можно попасть в любую другую вершину позвеньям ломаной;
· в каждой вершинеломаной встречаются два звена, одно из которых располагается по строке, другое- по столбцу.
Циклом пересчета называется такой цикл в таблице сбазисным распределением поставок, при котором одна из его вершин лежит всвободней клетке, остальные — в заполненных. Цикл пересчета называется означенным,если в его вершинах расставлены знаки "+" и "-" так, что всвободной клетке стоит знак "+", а соседние вершины имеютпротивоположные знаки.
Исходные параметрымодели транспортной задачи
1) n– количество пунктов отправления, m – количество пунктов назначения.
2) ai– запас продукции в пунктеотправления Ai (i=1, n) [ед. прод.].
3)bj– спрос на продукцию в пунктеназначения Bj (j=1,m) [ед. прод.].
4)cij– тариф (стоимость) перевозки единицыпродукции из пункта отправления ai в пункт назначения bj [руб./ед. прод.].
Искомые параметрымодели транспортной задачи
1) xij– количество продукции, перевозимойиз пункта отправления ai в пункт назначения bj [ед. прод.].
2) L(x)– транспортные расходы на перевозку всей продукции [руб.].
Этапы построениямодели
I. Определениепеременных.
II. Проверкасбалансированности задачи.
III. Построениесбалансированной транспортной матрицы.
IV Задание целевойфункции.
V Задание ограничений.
Целевая функция представляет собой общиетранспортные расходы на осуществление всех перевозок в целом. Первая группаограничений указывает, что запас продукции в любом пункте отправления долженбыть равен суммарному объему перевозок продукции из этого пункта. Вторая группаограничений указывает, что суммарные перевозки продукции в некоторый пунктпотребления должны полностью удовлетворить спрос на продукцию в этом пункте.Наглядной формой представления модели транспортной задачи является транспортнаяматрица (табл. 4.1).
Таблица 4.1Общий видтранспортной матрицы
Пункты
отправления, A1
Пункты потребления, Bj
Запасы,
ед. прод.
B1
B2 … Bm
A1
c11, [руб./ед. прод.]
c12 …
c1m
a1
A2
c21
c22 …
C2m
a2 … … … … … …
An
Cn1
Cn2 …
Cnm
an
Потребность
ед. прод.
b1
b2 …
bm
/>
Из модели (4.1) следует,что сумма запасов продукции во всех пунктах отправления должна равнятьсясуммарной потребности во всех пунктах потребления, т.е.
/>. (
Если (4.2) выполняется,то ТЗ называется сбалансированной (закрытой), в противном случае – несбалансированной(открытой). В случае, когда суммарные запасы превышают суммарныепотребности, необходим дополнительный фиктивный (реально несуществующий) пункт потребления, который будет формально потреблятьсуществующий излишек запасов, т.е.
/>.
Если суммарныепотребности превышают суммарные запасы, то необходим дополнительный фиктивныйпункт отправления, формально восполняющий существующий недостаток продукции впунктах отправления:
/>.
Для фиктивных перевозоквводятся фиктивные тарифы />, величина которых обычноприравнивается к нулю />. Но в некоторых ситуацияхвеличину фиктивного тарифа можно интерпретировать как штраф, которымоблагается каждая единица недопоставленной продукции. В этом случае величина /> можетбыть любым положительным числом.
Задача о назначениях – частный случай ТЗ. В задаче оназначениях количество пунктов отправления равно количеству пунктов назначения.Объемы потребности и предложения в каждом из пунктов назначения и отправленияравны 1. Примером типичной задачи о назначениях является распределениеработников по различным видам работ, минимизирующее суммарное время выполненияработ.
Переменные задачи о назначениях определяютсяследующим образом
/>
3. Реализацияалгоритма программы
Программа написана впрограммной среде C++ Builder 6.0. Для реализации всех методовпрограммы используются следующие библиотеки:
vcl.h> — библиотека визуальныхкомпонентов(внешнее оформление программы)
В программе определены иинициализированы следующие переменные и массивы:
massiv1[5][5] – массив мощностей поставщиков ипотребителей
massiv2[5][5] — массив поставок
massiv3[5][5] – массив значений матрицы оценок
massiv4[5][5], massiv5[5][5] — дополнительные массивы
Всю работу программыможно разбить на четыре основных шага: считывание данных в виде матрицы, заполнениезначений методом северо-западного угла, решение таблицы и вывод результата.
Руководствопользователя
Опрограмме. Программа позволяет проверитьправильность решения транспортных задач или же сделать за вас всю рутиннуюработу при решении этих задач. Программа позволяет загружать таблицы из файла (*.dat)или создавать новую таблицу, путём создания ячеек таблицы. Программа работаетна любой IBM совместимой машине при 32 Мб ОЗУ и 1 Мб свободного места на диске,на любом процессоре старше 486 и ОС Windows 98\2000\XP.
Описание программы. Программа имеет удобный и понятныйинтерфейс, благодаря которому быстро осваивается пользователем. При запускепрограммы открыто окно ввода значений.
Программа позволяетзагружать/сохранять файлы описания таблиц в формате *.dat. Они представляют собой текстовые файлы с параметрамиисходной задачи. Если файл описания загружен, он отобразится в окне настранице. Если это так, можно жать кнопку запуска расчётов.
После просмотрарезультатов необходимо очищать элементы интерфейса нажатием на кнопку меню «Сбросить».После каждого решения нужно очищать введенные данные, в противном случаепрограмма неправильно посчитает поставленную задачу.
Описание работыпрограммы. Дляначала работы нужно загрузить файл с помощью команды Файл>Открыть.
Выбранный файлотобразится в окне. В этом же окне можно изменить данные в соответствии стребуемой задачей. Между значениями и в конце каждой строки должен стоять знакпробела.
Сохранение значенийоуществляется командой Файл->Сохранить.
После внесениянеобходимых значений нужно нажать кнопку “Запустить”. После этого можно будетувидеть решение.
Когда распределениепоставок будет оптимальным алгоритм программы заканчивает свое решение. Функцияцели () и количество шагов подсчитывается автоматически.
После этого необходимонажать кнопку “сброс” для восстановления исходных параметров программы.
Для выхода из программынужно воспользоваться командой Файл->Выход.
Заключение
В заключении хотелось бырассказать о применении нашей программы в решении транспортныхпроблем.Многопользовательская система с гибкой настройкой прав и полномочий,позволяющая автоматизировать бизнес-процессы транспортно-экспедиционнойкомпании. Простой интуитивно понятный интерфейс с богатой функциональностью,позволяющий регистрировать, обрабатывать и контролировать заказы нагрузоперевозки (автоперевозки и т.п.), решать транспортные задачи, вести журналучета транспорта. Разработанная нами программа для транспортных компанийпозволяет быстро и удобно решать задачи транспортной логистики. Все сотрудникикомпании могут одновременно работать в программе, владеть актуальнойцентрализованной информацией и оперативно взаимодействовать, обладая заранееопределенными правами и полномочиями в системе егистрация заказовсопровождается подробным заданием условий оказания услуг по организациитранспортных перевозок. Все расчеты и вычисления осуществляются автоматическипо заранее сформированным тарифам, формулам, правилам.
Список используемойлитературы
1. Экономико-математические методы и прикладные модели. Финстатинформ М.,1997
2. Абчук В.А., Экономико-математические методы. Санкт-Петербург Союз,1999
3. Советов Б.Я, Яковлев С.А., Моделирование систем. Практикум. М. Высшаяшкола,1999
4. Замков О.О., Толстопятенко А.В., Черемных Ю.Н., Математические методыв экономике. М.ДИС, 1997.