Зададим столбец свободных членов:

Реализуем решение задачи, с помощью встроенных функций:

Ответ: точка (0, 0, 3)-точка максимума, f(x)=24

Вывод: результат, полученный при помощи графического, метода полностью совпадает с результатом решения симплекс-методом и подтверждается решением при помощи встроенных функций в пакете MathCAD 14.

Транспортная задача

Формулировка транспортной задачи.

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице.

Таблица 4.1.

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(), вектора запросов потребителей

В=() и матрицы стоимости .

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

Математическая модель транспортной задачи.

Переменными (неизвестными) транспортной задачи являются i=1,2,,…,m, j=1,2,…,n - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид

.

Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:

, i=1,2,…,m.

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

, j=1, 2, … , n.

Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:

, (1)

, i=1,2,…,m , (2)

, j=1, 2, … , n, (3)

, i=1,2,,…,m, j=1,2,…,n (4)

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

.

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

Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

Свойство системы ограничений транспортной задачи.

Теорема Ранг системы - условий транспортной задачи равен N=m+n-1.

Опорное решение транспортной задачи.

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1

Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные - незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная , которой соответствует вектор-условие .

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

Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рис1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

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

Метод северо-западного угла.

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

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

1. если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj, ;

2. если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki, ;

3. если , то и исключается либо i-й поставщик,

, k=1, 2, …, n, kj, , либо j-й потребитель, ,

k=1, 2, …, m, ki, .

Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы.

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

Метод минимальной стоимости.

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,…,m, j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Переход от одного опорного решения к другому.

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

Метод потенциалов.

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений - нахождение оценок свободных клеток.

Теорема. (признак оптимальности опорного решения). Если допустимое решение Х=(), i=1,2,,…,m, j=1,2,…,n транспортной задачи является оптимальным, то существует потенциалы (числа) поставщиков , i=1,2,,…,m и потребителей , j=1,2,…,n, удовлетворяющие следующим условиям:

+= при >0, (12)

+ при =0. (13)

Группа равенств (12) += при >0 используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например -+= или -=, если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

Данная система уравнений имеет m+n неизвестных , i=1,2,,…,m и , j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Числа называются оценками свободных клеток таблицы или векторов-условий транспортной задачи, не входящих в базис опорного решения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (k, l) таблицы, соответствующую max{}=. Если 0, то решение оптимальное. Если же >0, то для соответствующей клетки (k, l) строят цикл и улучшают решение, перераспределяя груз = по этому циклу

Задание №6

Для заданной матрицы издержек С, вектора столбца запасов А в пунктах отправления и вектора - строки потребностей В в пунктах назначения решить транспортную задачу и составить отчет по следующим пунктам:

· осуществить математическую запись транспортной задачи;

· решить задачу с помощью программы MathCAD

Запишем исходные данные

Решим задачу, используя ручной метод

Проверим, закрыта ли модель

Следовательно, модель закрыта.

7Размещено на http://www.allbest.ru/

Содержатся отрицательные оценки, следовательно, план неоптимальный.

Для улучшения плана построю цикл.

Полученный план является оптимальным.

Транспортные расходы:

Ответ: оптимальный план перевозок

Минимальная стоимость перевозок - 900.

Проверим результаты решения с помощью программы Mathcad 14:

Зададим начальные условия:

Определим модель задачи:

Модель закрытая.

Запишем формулу для функции стоимости перевозок:

Вывод: Результат, полученный ручным способом решения транспортной задачи абсолютно сходится с решение, полученным в программе MathCAD.

Заключение

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

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

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

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

В данной курсовой были реализованы все поставленные цели, решены и рассмотрены все основные задачи, также были проанализированы результаты и сделаны соответствующие выводы:

1. Для решения данной задачи самыми эффективными являются Метод Фибоначчи, Метод деления отрезка пополам и Метод Ньютона.

2. Наиболее точным и наиболее эффективным является метод Ньютона, этот метод считает за наименьшее количество итераций; самым неэффективным методом является метод дробления шага, нашедший минимум функции за 17 итераций

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

4. Результат, полученный ручным способом решения транспортной задачи, абсолютно сходится с решение, полученным в программе MathCAD.

Список литературы

1. Амосов А. А. , Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров: Учеб. пособие. - М.: Высш. шк., 1994.

2. Лесин В. В., Лисовец Ю. П. Основы методов оптимизации. - М.: Изд-во МАИ, 1998.

3. Пантелеев А. В., Летова Т. А. Методы оптимизации в примерах и задачах. - М.: Высш. шк., 2002.

3. Реклейтис Г., Рейвиндран А., Рэгодел К. Оптимизация в технике. - М.: Мир, 1986. Т.1.

4. Вычислительные методы. Методические указания к выполнению контрольных заданий, лабораторных и курсовых работ. - М.: МГАПИ, 2000.

Размещено на Allbest.ru