Решение математических задач
Формулировка и математическая модель транспортной задачи. Необходимое и достаточное условия разрешимости транспортной задачи. Методы построения начального опорного решения задачи. Алгоритм и особенности решения транспортных задач с неправильным балансом.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 19.10.2011 |
| Размер файла | 29,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1. Ход работы
Проанализировав поставленную задачу, мы пришли к выводу, что логика алгоритма решения данного задания сводится к алгоритму смешанной вычислительной структуры.
Листинг разработанной программы приведен ниже.
Program Var31;
Uses CRT;
Const My: array [1..5] of real=(0.189,0.0011,0.211,0.0000143,1.21);
b=-0.00247;
x=0.00111;
Function aa: real;
Var i:byte;
Sum:real;
S:real;
begin
Sum:=0;
For i:=1 to 5 do
begin
If (sqr(My[i]+b)+b)>=0 then
S:=b*My[i]+exp(1/3*ln(sqr(My[i]+b)+b)) else
S:=b*My[i]+(-1)*exp(1/3*ln(abs(sqr(My[i]+b)+b)));
Sum:=S+Sum;
end;
aa:=5.01+Sum;
end;
Var
i:byte;
z:real;
a,s:real;
begin
ClrScr;
Writeln('Ishodnie dannie ->');
For i:=1 to 5 do Writeln('y',i,'-> ',My[i]);
Writeln('_____________________________');
Writeln('x-> ',x);
Writeln('b-> ',b);
Writeln('_____________________________');
a:=aa;
If sqrt(sqr(a)+sqr(b))>a*x then
z:=a*sqr(x)+b*ln(sqr(sin(2*x)))+sqr(b)
else
z:=sqrt(a+cos(sqr((a*x+b))))-sin(abs(b*sqr(x)));
Writeln('Rezultat');
Writeln('a-> ',a:6:5);
Writeln('Z-> ',z:6:5);
end.
2. Транспортная задача
транспортный задача опорный решение баланс
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.
В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.
3. Формулировка транспортной задачи
Однородный груз сосредоточен у m поставщиков. Данный груз необходимо доставить n потребителям. Известны i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков, вектора запросов потребителей и матрицы стоимостей.
В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.
4. Математическая модель транспортной задачи
Переменными (неизвестными) транспортной задачи являются i=1,2,,…,m, j=1,2,…,n - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок.
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью.
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей.
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
Такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи, i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).
Математическая модель транспортной задачи может быть записана в векторном виде.
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной, является вектором-условием задачи и обозначается через. Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая - на (m+j)-м месте, т.е.
5. Необходимое и достаточное условия разрешимости транспортной задачи
Теорема1. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом.
6. Опорное решение транспортной задачи
Опорным решением транспортной задачи называется любое допустимое решение, для которого вектор-условия, соответствующие положительным координатам, линейно независимы.
Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1
Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные - незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку, т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j).
Для того чтобы избежать трудоемких вычислений при проверке линейной независимости вектор-условий, соответствующих положительным координатам допустимого решения, вводят понятие цикла. Циклы также используются для перехода от одного опорного решения к другому.
Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.
Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900.
Теорема3. (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла). Для того чтобы система векторов-условий транспортной задачи были линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл.
Метод вычеркивания
Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.
Пусть допустимое решение транспортной задачи, которое имеет m+n-1 отличную от нуля координату, записано в таблицу. Чтобы данное решение было опорным, векторы-условия, соответствующие положительным координатам, должны быть линейно независимы. Для этого занятые решением клетки таблицы должны быть расположены так, чтобы из них нельзя было образовать цикл.
Строка или столбец таблицы с одной занятой клеткой не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждой строке или в столбце. Следовательно, можно вычеркнуть сначала либо все строки таблицы, содержащие по одной занятой клетке, либо все столбцы, содержащие по одной занятой клетке, далее вернуться к столбцам (строкам) и продолжить их вычеркивание. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов-условий линейно независима, а решение является опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов-условий линейно зависима, а решение не является опорным.
7. Методы построения начального опорного решения
Метод северо-западного угла.
Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель.
Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы.
Теорема4. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.
Теорема5. Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.
8. Переход от одного опорного решения к другому
В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решений. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.
Теорема6. (о существовании и единственности цикла). Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Означенный цикл.
Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным - знак «-».
Теорема7. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, получится опорное решение.
9. Распределительный метод
Один из наиболее простых методов решения транспортной задачи - распределительный метод.
Пусть для транспортной задачи найдено начальное опорное решение и вычислено значение целевой функции на этом решении. По теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением.
10. Метод потенциалов
Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений - нахождение оценок свободных клеток.
11. Особенности решения транспортных задач с неправильным балансом
До сих пор рассматривались транспортные задачи с правильным балансом. Однако на практике чаще встречаются задачи с неправильным балансом. Каковы особенности их решения?
1. Пусть суммарные запасы поставщиков превосходят суммарные запросы потребителей. Очевидно, что в этом случае при составлении оптимального плана перевозок часть запасов поставщиков останется не вывезенной.
Вторая группа уравнений остается без изменения, так как запросы всех потребителей удовлетворяются полностью. Для приведения к канонической форме в неравенства вводят дополнительные переменные.
В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициентами).
Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза.
2. Аналогично в случае, когда суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е., часть запросов потребителей, останется не удовлетворенной. Поэтому вторая группа уравнений системы ограничений (3) транспортной задачи заменяется неравенствами, j=1, 2, … , n.
Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами, равными разности суммарных запросов потребителей и запасов поставщика, и нулевыми стоимостями перевозок единиц груза.
Необходимо отметить, что при составлении начального опорного решения в последнюю очередь следует распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствует наименьшая стоимость перевозок, равная нулю.
12. Алгоритм решения транспортной задачи методом потенциалов
Порядок решения транспортной задачи методом потенциалов следующий.
1. Проверяют выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводят фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок.
2. Строят начальное опорное решение (методом минимальной стоимости или каким-либо другим методом) и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть m+n-1) и убеждаются в линейной независимости векторов-условий (методом вычеркивания).
3. Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы.
4. Вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.
5. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. Далее возвращаемся к пункту 3 алгоритма.
Список использованных источников
1. Брябрин В.М. Программное обеспечение персональных ЭВМ. -М.: “Наука”, 1988.
2. Бородич Ю.С. Паскаль для персональных компьютеров: Спр. пособие. -Мн.: Выш. шк., 1991. -- 365 с.
3. Алкок Д. Паскаль в иллюстрациях: Пер. с англ. -М.: Мир, 1991. -- 192 с.
4. Джонс Ж. Харроу К. Решение задач в системе Turbo Pascal: пер. с англ. -М.: 1991. -- 720 с.
5. Зуев Е.А. Система программирования Turbo Pascal-М.: Радио и связь, 1991. -- 288 с.
6. Бородич Ю.С. Разработка программных систем на языке Паскаль:Спр. пособие. -Мн.: Высш. шк., 1992 -- 143 с.
7. Зуев Е.А. Язык программирования Turbo Paskal 6.0-М.: 1992. -- 298с.
8. Н.Культин. Turb Pascal 7.0 Дюсседорф,Ки-ев,Москва,С-Петербург. 1998.
9. С.И.Молчанова. Основы программирования Турбо-Паскаль7.0.- М. “Аквариум»,АСТ,1999
10. О.А.Маженный. Turb Pascal. Учитесь программировать. «Диалектика».М:СП:Киев,2001.
11.Фаронов В. Turb Pascal 7.0. Учебное пособие. М.,Из-во«Нолидж»,2001.
12.Федоров А.,Рогаткин.Д. Borland Pascal в среде Windows. -Киев: “Диалектика”,1993.- 656 с.
Размещено на Allbest.ru
Подобные документы
Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Математическая формулировка задачи, существующие численные методы и схемы алгоритмов. Интерполирование функции, заданной в узлах, методом Вандермонда. Среднеквадратичное приближение функции. Вычисление интеграла функций по составной формуле трапеций.
курсовая работа [3,4 M], добавлен 14.04.2009Графический и симплексный методы решения ОЗЛП. Построение функции цели, образующая совместно с системой ограничений математическую модель экономической задачи. Нахождение неотрицательного решения системы линейных уравнений. Решение транспортной задачи.
лабораторная работа [322,9 K], добавлен 10.04.2009
