Реализация программного модуля, на встроенном языке программирования Visual Basic for Application (VBA)

Введение

Целью данной курсовой работы является реализация программного модуля, на встроенном языке программирования Visual Basic for Application (VBA), для автоматизации решения транспортной задачи в сетевой постановке.

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

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

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

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

·  к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

·  общее количество стрелок должно быть на единицу меньше числа вершин;

·  стрелки не должны образовывать замкнутый контур.

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

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

Сущность транспортной задачи состоит в определении оптимального плана перевозок некоторого одного груза из m пунктов отправления в n пунктов назначения.

Условия транспортной задачи заданы в виде картосхемы, на которой условно изображены поставщики, потребители и связывающие их дороги, указаны величины запасов груза  и потребностей в нем , а также числа являющиеся показателями принятого в задаче критерия оптимальности (тарифы, расстояния и т.п.), то говорят, что транспортная задача поставлена в сетевой форме (рисунке 1).

Рисунок 1 – транспортная задача поставлена в сетевой форме.

Описанную картосхему будем называть транспортной сетью. Пункты расположения поставщиков и потребителей будем изображать кружками, и называть вершинами (узлами) сети, запасы груза будем записывать в кружках положительными, а потребности — отрицательными числами. Дороги, связывающие пункты расположения и потребления груза и другие пункты, будем изображать линиями, и называть ребрами (дугами, звеньями) сети. При изображении транспортной сети реальный масштаб не соблюдается. На сети могут быть изображены вершины, в которых нет ни поставщиков, ни потребителей. Наличие таких вершин не повлияет на способ решения, если считать, что запасы (потребности) груза в них равны нулю.

Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях. Далее  используется метод потенциалов.

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

Решение задачи на сети начинается с построения начального опорного плана.

Опорный план должен удовлетворять следующим требованиям:

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

2)  к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

3)  общее количество стрелок должно быть на единицу меньше числа вершин;

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

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

Для этого вычисляют потенциалы. Одной из вершин (например, вершине I) присвоим некоторое значение потенциала (например, равное 0). (Для большей наглядности потенциалы заключают в рамки.) После этого, двигаясь по стрелкам, определяют потенциалы остальных вершин, руководствуясь правилом: если стрелка выходит из вершины, то к потенциалу этой вершины прибавляем показатель C_ij критерия оптимальности, если же направление стрелки противоположно, то C_ij вычитаем.

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