Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
Краткое сожержание материала:

Размещено на

Министерство образования и науки Российской Федерации

Уральский государственный колледж им. И.И. Ползунова

КП.230105.08. ПЗ

НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ

Пояснительная записка

Руководитель /Е.В. Щанова/

Разработал /Е.А. Ищенко/

Екатеринбург 2011

Содержание

• Введение
• 1. Постановка задачи
• 2. Этапы решения задачи
• 2.1 Математическая модель
• 2.2 Разработка алгоритма
• 2.3 Описание программы
• 2.4 Тестирование программы
• 2.5 Анализ полученных результатов
• Заключение
• Список использованных источников
• Приложение А

Введение

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

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

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

Задачи курсового проекта:

построение математической модели;

разработка алгоритма задачи;

создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi7;

решить задачу созданной программой;

проанализировать результат.

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

1. Постановка задачи

От каждого i-го производителя произведенный им ресурс A_i может перемещаться к j-му потребителю ресурса в объеме, не превышающие B_i. Таким образом, x_ij будет означать перемещение некоторого числа единиц ресурса от i-го производителя к j-му потребителю.

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

Составить оптимальный план перевозок ресурсов от производителя к потребителю с минимальными затратами. Исходные данные указаны в таблице 1.

Таблица 1 - Исходные данные

Матрица стоимости	А1	А2	А3	А4	Производители
В1	6	5	8	7	14
В2	3	6	4	2	12
В3	9	1	3	6	8
Потребители	10	14	6	4

2. Этапы решения задачи

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

При решении транспортной задачи необходимо:

а) обеспечить всех потребителей ресурсами;

б) распределить все произведенные ресурсы;

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

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

Транспортная задача всегда разрешима и имеет:

а) единственное решение;

б) несколько допустимых решений, одно из которых оптимально;

в) несколько допустимых решений и все оптимальны.

Через С_ij обозначим стоимость перемещения единицы ресурса, от i-го производителя к j-му потребителю. Тогда матрица X={x_ij} называется матрицей перевозок или планом перевозок, а матрица C={c_ij} - матрица стоимости.

Строим математическую модель

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

, (1)

где F (x) - целевая функция;

c_ij - коэффициенты матрицы стоимости;

x_{ij -} коэффициенты матрицы перевозок.

(x) _{i j}0, i=, j=

2.2 Разработка алгоритма

1) Задать количество производителей и потребителей;

2) Произвести ввод данных, данные берутся из таблицы 1;

3) следующим шагом строится опорный план для задачи. В программе рассмотрено построение опорного плана методом "северо-западного" угла и методом минимальных элементов;

4) выбирается первый незаполненный элемент опорного плана;

5) от выбранного элемента строится кратчайший прямоугольный замкнутый контур, остальные вершины проходит через заполненные элементы опорного плана. Поворот осуществляется только на 90⁰ и только в заполненных элементах;

6) каждой вершине контура присваивается коэффициент равный соответствующему значение элементу из С={c_ij};

7) каждому коэффициенту в вершине контура строго поочередно присваивается знак "+" или "-" начиная с пустой клетки;

8) выполняется алгебраическое суммирование коэффициентов по всему контуру;

9) пункт 4-8 выполняется для каждого пустого элемента опорного плана;

10) проверяются результаты суммирования по всем контурам на оптимальность;

11) если план перевозок не оптимальный то выполняется перераспределение ресурсов и возвращаемся к пункту 4.

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

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

Если план перевозок не оптимальный, то перераспределение выполняется следующим образом:

а) выбирается контур, для которого нарушено условие оптимальности, если целевая функция стремится к min, то выбирается отрицательный контур. Если таких контуров несколько, то выбирается тот, который больше по модулю;

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

в) проверяется сбалансированность перевозок по столбцам и строкам;

г) заново рассчитывается алгебраические суммы (по стоимости) для всех контуров;

д) проверяется условие оптимальности.

2.3 Описание программы

Код программы был написан в программной среде Borland Delphi7.

Программа состоит из трех окон.

Для запуска программу нужно два раза кликнуть левой кнопкой мыши по файлу "transportnaya zadacha. exe". При запуске программы открывается главное окно "Решение транспортной задачи распределительным методом =)", в котором необходимо выбрать количество потребителей и количество производителей, метод нахождения опорного плана, после этого ввести данные и нажать на кнопку "Рассчитать". Главное окно программы представлено на рисунке 1.

При нажатии кнопки "Рассчитать" происходит вычисление оптимального плана по...