Аннотация

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

Такая задача актуальна в областях связанных с транспортировкой грузов.

САРОВСКИЙ ГОСУДАРСТВЕННЫЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ И ИССЛЕДОВАНИЙ ОПЕРАЦИЙ В ЭКОНОМИКЕ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ на тему:

Решение транспортной задачи с правильным балансом

Студента руководитель работы консультанты работы Зав. кафедрой

г. Саров

2005 г

Оглавление

Введение. 3

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

Метод решения. 5

Язык программирования. 7

Описание алгоритма. 8

Описание основных структур данных. 12

Описание интерфейса с пользователем. 14

Заключение. 16

Литература. 17

Текст программы.. 18

Введение

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

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

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

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1, А2 , ..., Аm , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... , аm. Имеется n пунктов назначения В1 , В2 , ... , Вn подавшие заявки соответственно на b1 , b2 , ... , bn груза. Известны стоимости Сi,j перевозки от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Метод решения

 

1.Составление опорного плана.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ “северо-западного угла” Рассмотрим конкретный примере:

Условия транспортной задачи заданы транспортной таблицей.

 ПН

 ПО

В1 В2 В3 В4 В5

Запасы

аi

А1 10 8 5 6 9 48 А2 6 7 8 6 5 30 А3 8 7 10 8 7 27 А4 7 5 4 6 8 20

 Заявки

 bj

18 27 42 12 26 125

Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки (“северо-западного угла“ таблицы). Будем рассуждать при этом следующим образом. Пункт В1 подал заявку на 18 единиц груза. ............