Решение транспортных задач - Курсовая работа

Нам приходится в жизни считать(например, деньги), мы постоянно используем(часто не замечая этого) знания о величинах, характеризующих протяженности, площади, объемы, промежутки времени, скорости и многое другое. Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой и экономикой. Математика является языком естествознания и техники и потому профессия естествоиспытателя и инженера требует серьезного овладения многими профессиональными сведениями, основанными на математике. Поэтому в подготовке экономистов широкого профиля изучения математики занимает значительное место. Наряду с моделированием экономистам необходимо изучать теорию оптимизации, которая представлена математическими методами исследования операций, в том числе линейным программированием.Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Целевая функция задачи (1.1) выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи i=1,2,…,m; j=1,2,…,n, удовлетворяющее системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее минимум целевой функции (1.1). Такая задача называется задачей с правильным балансом, а ее модель-закрытой. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом.Особенности решения транспортных задач с неправильным балансом: 1.Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. то необходимо ввести фиктивного (n 1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц грузаЕсли в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец(потребитель).Если допустимое решение , i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков i=1,2,…,m и потребителей j=1,2,…,n, удовлетворяющее следующим образом: Группа равенств (2.1) используется как система уравнений для нахождения потенциалов. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы. Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи. Для этого находят клетку (l,k) таблицы, соответствующую . Если же , то для соответствующей клетки (l,k) строят цикл и улучшаю решение, перераспределяют груз по этому циклу.На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Так как его запасы меньше запросов первого потребителя , то в клетку (1,1) записываем перевозку и исключаем из рассмотрения первого поставщика. Так как его запасы , меньше запросов первого потребителя , то записываем в клетку (2,1) перевозку и исключаем из рассмотрения второго поставщика. Так как его запасы больше запросов первого потребителя , то записываем в клетку (3,1) перевозку и исключаем из рассмотрения первого потребителя. Так как его запасы меньше запросов второго потребителя , то в клетку (3,2) записываем перевозку и исключаем из рассмотрения третьего поставщика.Входные данные вводятся с клавиатурыИнформация выводится на экран в виде таблицы с введенными данными и допустимый начальный базис

В1 50 В2 40 В3 30 В4 20 В5 10

А1 10 10 - - - -

А2 20 20 - - - -

А3 30 20 10 - - -

А4 40 - 30 10 - -

А5 50 - - 20 20 10Общие сведения: Программа производит вычисления допустимого начального базиса Поиск начального базиса происходит методом «северо-западного угла»Данная про

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1. ОБЩАЯ ЧАСТЬ 8

1.1 Математическая постановка задачи 8

1.2 Алгоритм решения задачи 11

1.3 Блок-схема (алгоритм решения) 25

2. Формы входной информации 27

3. Формы выходной информации 28

4. Инструкция для пользователя 29

5. Инструкция для программиста 30

ЗАКЛЮЧЕНИЕ 33

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

ПРИЛОЖЕНИЕ А 35