Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
Аннотация к работе
Нам приходится в жизни считать(например, деньги), мы постоянно используем(часто не замечая этого) знания о величинах, характеризующих протяженности, площади, объемы, промежутки времени, скорости и многое другое. Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой и экономикой. Математика является языком естествознания и техники и потому профессия естествоиспытателя и инженера требует серьезного овладения многими профессиональными сведениями, основанными на математике. Поэтому в подготовке экономистов широкого профиля изучения математики занимает значительное место. Наряду с моделированием экономистам необходимо изучать теорию оптимизации, которая представлена математическими методами исследования операций, в том числе линейным программированием.Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Целевая функция задачи (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Общие сведения: Программа производит вычисления допустимого начального базиса Поиск начального базиса происходит методом «северо-западного угла»Данная про