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

Главная

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

Использование математических и программных средств моделирования при решении задачи минимизации транспортных издержек. Использование метода потенциалов, разработка алгоритма программы на языке программирования Turbo Pascal 7.0. Методы реализации.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Продукцию, сосредоточенную у трех поставщиков - заводов А, В, С необходимо доставить пяти потребителям - складам № 1, 2, 3, 4, 5. Известна стоимость Су единицы продукции от i - го поставщика к j - му потребителю.
Необходимо составить план перевозок, позволяющих вывести всю продукцию, полностью удовлетворить потребности складов и получить минимальные транспортные издержки.
Мощность заводов, потребности складов (в тоннах) и стоимость перевозок (в рублях), смотри табл.1.
Определить оптимальное закрепление заводов к складам, при котором достигается минимизация транспортных издержек.
Задачу решить методом потенциалов, программу написать на языке программирования Turbo Pascal 7.0 и реализовать на ПЭВМ IBM-совместимой машине.
Cij - стоимость перевозки единицы продукции от i-ro завода к j-тому складу
Хij - количество единиц продукции, запланированных к перевозке от i-ro завода к j-тому складу
Zmin - минимальная стоимость перевозок (min транспортные издержки) Математическая модель данной задачи имеет вид:
Z=30X11+32X12+25X13+50X14+23X15+40X21+10X22+12X33+21X24+25X25+21X31+20X31+50X33+18X34+14X35 min
Данная ТЗ решается методом потенциалов.
Первый шаг заключается в нахождении первоначального опорного плана. Он может быть найден с помощью метода минимальной стоимости.
Суть метода минимальной стоимости заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел а; или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
План получается вырожденный каждый раз, когда после нескольких шагов количество продуктов на базе равно в точности потребности потребителя. Если же, либо потребности потребителя не полностью удовлетворены, либо на базе остались неиспользованные продукты, то план получается невырожденный и возникает необходимость в добавлении фиктивных поставщиков или потребителей.
В результате применения метода минимальной стоимости, получается опорный план, близкий к оптимальному.
После получения опорного плана для дальнейших вычислений необходимо воспользоваться методом потенциалов. Для проверки найденного плана ТЗ, необходимо предварительно вычислить числа Ui и Vj , называемые потенциалами и отвечающие исходному плану. Для начала итерационного процесса нужно составить систему потенциалов для Хij > 0 в полученном опорном плане. Для Uj и Vj справедливо равенство Ui + Vj = Сij.
Получается m + n-1 уравнений с m + n неизвестными. Принимая U1 = О, найдем значения остальных неизвестных Uj и Vj.
Затем находится значение Uj + Vj - Сij для всех Хij = 0. Если при решении получается, что для всех Хij = 0 значение Ui + Vj-Cij > 0, то найденный план является оптимальным.
Если для некоторых Хij = 0 значения Ui + Vj-Cij > 0, то найденный опорный план не является оптимальным, то есть не выполняется условие оптимальности
С ij -- С ij < 0. Следовательно, нужно переходить к новому опорному плану и снова проверить его на оптимальность.
Для перехода к новому опорному плану выбирается наибольшее положительное число из всех С ij -- С ij < 0
Чтобы найти вектор, исключаемый из первоначального базиса, можно воспользоваться таким приемом: из клетки, имеющей максимум С ij -- С ij > 0, проводятся линии таким образом, чтобы, начиная движение от данной клетки, двигаясь только под прямым углом и тем клеткам, в которых есть значения, в нее и возвратиться. Первый ход отмечается знаком (+), второй (-), третий (+) и т.д. до конца.
Из клеток со значением (+) выбирается наименьшее значение. Это значение необходимо вычесть из всех клеток со знаком (+) и прибавить к тем клеткам, у которых знак (-). При помощи этого способа получается новый опорный план. Далее снова находятся потенциалы Хij > 0. Этот процесс повторяется до тех пор, пока не получится оптимальный план, то есть пока не будет выполняться критерий оптимальности С ij -- С ij < 0 Вычисления сводятся в таблицу 2.
MATR = ARRAY [1...6, 1...6] OF INTEGER; MASS-ARRAY [1...6] OF INTEGER;
S,W,Z,MIN, МАХ,В1,А1Д, J,M,N,T: INTEGER;
WRITELN; WRITELN; WRITELN; WRITELN;
WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN ('Выполнил студент группы П-10 Коваленко А.Г.')
WRITE ('Введите количество заводов N= '); READ(N);
WRITE ('Введите мощности заводов A[l]:');
FOR I: = 1 TO N DO BEGIN READLN (A[I]);
WRITE ('Введите количество складов M= '); READ(M);
WRITE ('Введите потребности складов B[J]:');.
WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN;
WRITE ('Введите матрицу стоимостей С [I, J]');
WRITELN; WRITELN; WRITELN; WRITELN; WRITELN; WRITELN;
WRITE ('Введите первоначальный опорный план X[I,J]');
IF (X[I,J]<>0) AND (V[J]<>999) THEN U[I]: = C[I,J] - V[J];
IF (X[I,J]<>0) AND (U[I]<>999) THEN V[J]: = C[I,J] - U[I]; END;
WRITELN ('Таблица потенциалов N,W');
MAX: = (U[I] + V[J]) - С [I, J]; K[1]: = I;
IF X[I,J]<>0 THEN Z: = Z + X[I,J]*C[I,J];
WRITELN;WRITELN;WRITELN; WRITELN ('Z-,Z);
IF (S = 0) AND (X[K[I],L[I]]0 THEN X[K[I], L[I]]: = X[K[I], L[I]] + MIN ELSE
X[K[I],L[I]]: = X[K[I],L[I]] - MIN;
2: WRITELN ('Условие оптимальности выполняется ');
WRITELN ('Опорный план - является оптимальным');
введите первоначальный опорный план X[I,J]
V[l] = -4 V[2] = -5 V[3] - 25 V[4] = -7 V[5] - -10
V[l] = 24 V[2] = 23 V[3] = 25 V[4] = 21 V[5] = 18
опорный план - является оптимальным
В результате решения задачи по минимизации транспортных издержек получен оптимальный план
Чтобы достигнуть минимальных суммарных затрат на перевозку продукции от заводов к складам, необходимо произвести такое закрепление перевозок:
От завода А к складу№3 - 500 тонн продукции;
От завода В к складу№2 - 200 тонн продукции;
От завода В к складу№3 - 100 тонн продукции;
От завода С к складу№1-100 тонн продукции;
От завода С к складу№2 - 200 тонн продукции;
От завода С к складу№4 - 200 тонн продукции;
От завода С к складу№5 - 100 тонн продукции.
Минимальные транспортные издержки = 26900 рублей. В результате оптимизации плана перевозок, получили экономию затрат по транспортировке (29700 - 26900) = 2800 рублей.
Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации. курсовая работа [1010,4 K], добавлен 10.08.2014
Описание математических методов решения задачи оптимизации. Рассмотрение использования линейного программирования для решения транспортной задачи. Применение симплекс-метода, разработка разработать компьютерной модели в Microsoft Office Excel 2010. курсовая работа [1,5 M], добавлен 24.05.2015
Решения задачи графическим и программным способами. Описание алгоритма решения графическим способом, укрупненная схема алгоритма. Ввод элементов двумерного массива, вывод преобразованного массива, разработка программы на языке pascal, листинг программы. курсовая работа [115,5 K], добавлен 22.05.2010
Описание алгоритма решения задачи по вычислению суммы элементов строк матрицы с использованием графического способа. Детализация укрупненной схемы алгоритма и разработка программы для решения задачи в среде Turbo Pascal. Листинг и тестирование программы. курсовая работа [446,0 K], добавлен 19.06.2014
История появления и распространения Turbo Pascal - среды разработки для языка программирования Паскаль. Общий вид объявления файлового типа. Входная, выходная и промежуточная информация. Алгоритм решения задачи: словесный алгоритм, блок-схема, программа. курсовая работа [359,4 K], добавлен 05.01.2010
Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание. курсовая работа [241,7 K], добавлен 11.12.2009
Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения. курсовая работа [2,0 M], добавлен 12.02.2013
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Программная реализация решения транспортной задачи курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа: Дефрагментатор файловой системы
Научная работа: Гены в нашей жизни
Курсовая работа по теме Проектирование технологического процесса механической обработки детали 'фланец'
6 Класс По Математике Мерзляк Контрольная Работа
Реферат На Тему Выбор Рекламного Агентства Полного Цикла (Г. Санкт-Петербург)
Один День Из Школьной Жизни Сочинение Повествование
Реферат: Организация центрального управления империи
Курсовая работа по теме Качество питьевой воды нецентрализованного водоснабжения г. Гомеля и Гомельской области
Контрольная Работа Механические Волны
Егэ Русский Язык Оценивание Сочинения
Сочинение: Смысл названия поэмы Н. В. Гоголя Мертвые души
Готовые Дипломные Работы По Ветеринарии
Сочинение О Чем Рассказывает Осеннее Дерево
Реферат: Состояние рынка ценных бумаг в Украине. Скачать бесплатно и без регистрации
Реферат: Семилетняя война 2
Рассказы Пушкина Сочинение
Реферат по теме Что такое садизм?
Курсовая работа: Организационные аспекты менеджмента. Скачать бесплатно и без регистрации
Эссе 19 Век
Цель Лабораторной Работы
Гражданское право в системе права России - Государство и право реферат
Распад Советского Союза - История и исторические личности реферат
Организация работы информационно-статистического отделения - Медицина дипломная работа