Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Математика Математика

Решение транспортной задачи методом потенциалов

Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Ручка "Помада".
Шариковая ручка в виде тюбика помады. Расцветка корпуса в ассортименте, без возможности выбора!
25 руб
Раздел: Оригинальные ручки

Министерство Российской Федерации по атомной энергии Саровский Государственный Физико-Технический ИнститутПолитехникум СарФТИ КУСОВАЯ РАБОТА По специальности– «Программное обеспечение» Тема: Решение транспортной задачи методом потенциалов Студент: Группа: Преподаватель: Дата: 05 Мая Оценка: г. Саров 2005 г. СодержаниеВведение 1. Транспортная задача 1.1 Составление опорного плана 1.2 Метод потенциалов 2. Практическая часть 2.1 Обоснование выбора языка программирования 2.2 Разработка 2.3 Руководство пользователей Заключение Литература Введение Данный курсовой проект представляет собой программу для решения транспортной задачи методом потенциалов. Программа предоставляет пользователю возможность пошагового нахождения оптимального решения. Все промежуточные результаты выводятся на экран, пользователь может следить за ходом решения. Транспортная задача заключается в нахождении такого плана поставок, при котором его цена минимальна. Условия задачи задаются в виде таблицы: поставщик потребитель Запас груза В1 В2 В А1 C11 X11 C12 X12 C1 X1 a1 А2 C21 X21 C22 X22 C2 X2 a2 Аm Cm1 Xm1 Cm2 Xm2 Cm Xm am Потребность в грузе b1 b2 b Матрица (cij)m называется матрицей тарифов. Планом транспортной задачи называется матрица х=(xij)m , где каждое число обозначает количество единиц груза, которое надо доставить из i–го пункта отправления в j–й пункт назначения. 1. Транспортная задача Транспортная задача ставится следующим образом: имеется m пунктов отправления, в которых сосредоточены запасы каких-то однородных грузов. Имеется пунктов назначения подавшие заявки соответственно на груза. Известны стоимости рij перевозки единицы груза от каждого пункта отправления до каждого пункта назначения. Все числа рij, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Далее, предполагается, что (1) где bi есть количество продукции, находящееся на складе i, и aj – потребность потребителя j. Замечание. Если то количество продукции, равное остается на складах. В этом случае мы введем &quo ;фиктивного&quo ; потребителя 1 с потребностью и положим транспортные расходы pi, 1 равными 0 для всех i. Если то потребность не может быть покрыта. В этом случае начальные условия должны быть изменены таким образом, чтобы потребность в продукции могла быть обеспечена. Обозначим через xij количество продукции, поставляемое со склада i потребителю j. В предложении (1) нам нужно решить следующую задачу (математическая модель транспортной задачи): (2) Транспортную задачу мы можем характеризовать транспортной таблицей и таблицей издержек: а1 а b1 . . . bm . . . . . . p11 p1 . . . . . . pm1 pm Допустимый план перевозок будем представлять в виде транспортной таблицы: а1 а b . . . bm . . . . . . Cумма элементов строки i должна быть равна bi, а сумма элементов столбца j должна быть равна aj, и все должны быть неотрицательными. Пример 1. 20 5 10 10 5 15 15 20 5 6 3 5 9 6 4 7 3 5 2 5 3 1 8 Мы получаем следующую задачу: х11 х12 х13 х14 х15 =15, х21 х22 х23 х24 х55 =15, х31 х32 х33 х34 х35 =20, х11 х21 х31=20, х12 х22 х32=5, х13 х23 х33 =10, х14 х24 х34 =10, х15 х25 х35=5; хij 0 для i = 1,2,3; j = 1,2,3,4,5; Такие задачи целесообразно решать при помощи особого варианта симплекс-метода – так называемого метода потенциалов.

Все транспортные задачи имеют оптимальное решение. Если все значение aj и bi в условиях транспортной задачи целочисленные, то переменные xij во всех базисных решениях (а так же и в любом оптимальном базисном решении) имеют целочисленные значения. 1.1 Составление опорного плана Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы, рассмотрим простейший, так называемый способ северо-западного угла. Пояснить его проще всего будет на конкретном примере: Условия транспортной задачи заданы транспортной таблицей. а b 20 5 10 10 5 15 5 6 3 5 9 15 6 4 7 3 5 20 2 5 3 1 8 Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки (&quo ;северо-западного угла&quo ; таблицы). Будем рассуждать при этом следующим образом. Пункт а1 подал заявку на 20 единиц груза. Удовлетворим эту заявку за счёт запаса 15, имеющегося в пункте b 1 , и запишем перевозку 15 в клетке (1,1). После этого дополним заявку за счет заявка пункта b 2, и запишем 5 в клетке (1,2), теперь заявка удовлетворена, но в пункте b 2 осталось ещё 10 единиц груза. Удовлетворим за счёт них заявку пунктов а2 (5 единиц клетка 2,2) и а3 (5 единиц клетка 2,3). На складе b3 есть запас в 20 единиц, за счет его мы удовлетворим оставшиеся заявки а3 (оставшиеся 5 единиц клетка 3,3), а3 (10 единиц клетка 3,4) и а5 (5 единиц клетка 3,5). 5 6 4 7 3 1 8 На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij . 1.2 Метод потенциалов Пусть имеется транспортная таблица, соответствующая начальному решению, хil = для базисного решения переменных, хil = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными pij. Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u1, ,um, в нижнюю строку – значения неизвестных v1, ,v ,. Эти m неизвестных для всех (i, j), соответствующих базисным переменным, должны удовлетворять линейной системе уравнений ui vj = pij. pll plj pl ul . . . . . . . pil pij pi ui . . . . . . . pml pmj pm um vl vj v Для всех базисных решений эта система имеет треугольный вид, ранг её матрицы равен m – 1. Следовательно, систему всегда можно решить следующим способом. Полагают v = 0. Если значения k неизвестных определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет. Переменные ui и vj симплекс - множителями. Иногда они называются также потенциалами, а этот метод решения называют методом потенциалов.

Пример 2. 5 u1 6 4 7 u2 3 1 8 u3 v1 v2 v3 v4 v5 v5 = 0 ® u3 = 8, так как u3 u5 = p35 = 8, ® v4 = -7, так как u3 v4 = p34 = 1, ® v3 = -5, так как u3 v3 = 3, ® u2 = 12 ® v2 = -8, ® v1 = -6 ® u1 = 11. Симплекс – множители нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе). Для определения симплекс – множителей мы вносим на свободные места в таблице значения pўij = pij – ui – vj (коэффициенты целевой функции, пересчитанные для свободных переменных). Если все pўij 0, то базисное решение оптимально. В противном случае мы выбираем произвольное pўab &l ; 0, чаще всего наименьшее. Индексом ab помечено свободное переменное хab , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком . Кроме ячейки (a, b) транспортной таблицы, мы пометим значками – и другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному знаку -. Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку (g, d), где этот минимум достигается. В нашем примере с М = 5 можно выбрать (g, d) = (2, 3); при этом (g, d) определяет базисное переменное, которое должно стать свободным, т.е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода. 20 5 10 10 5 15 15 15 5 5 5- 20 5 10 5- Ї 15 5- 5 5 10 10 0- Ї 15- 5 5 5 0 10- 10 Ї 5 10 5- 5 5 10 10- Ї 5 10 5 5 5 15 5 Копт = 150 Переход к новой транспортной таблице (замена базиса) происходит следующим образом: а). В ячейку (a, b) новой таблицы записывается число М. б). Ячейка (g, d) остается пустой. в). В других ячейках помеченных знаками – или , число М вычитается из стоящего в ячейке числа (-) или складывается с ним ( ). Результат вносится в соответствующую ячейку новой таблицы. г). Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми. 2. Практическая часть 2.1 Обоснование выбора языка программирования Мною был выбран язык программирования urbo Pascal по следующим соображениям: Изучение данного языка в школе Наличие литературы по данному языку программирования 2.2 Разработка Имеется m пунктов отправления А1, А2 , ., Аm , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, . , аm единиц. Имеется пунктов назначения В1 , В2 , . , В подавшие заявки соответственно на b1 , b2 , . , b единиц груза. Известны стоимости Сi,j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Составить программу, которая бы вычисляла оптимальный план перевозки (потенциальный план).

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

1. Решение транспортной задачи методом потенциалов

2. Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов

3. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

4. Решение задач линейной оптимизации симплекс – методом

5. Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

6. Решения смешанной задачи для уравнения гиперболического типа методом сеток
7. Решение задач линейного программирования симплекс методом
8. Решение прикладных задач методом дихотомии

9. Решение экономических задач программными методами

10. Решение задачи линейного программирования симплексным методом

11. Методы решения логистических задач

12. Методы решения логических задач

13. Графический метод решения химических задач

14. Оптимизационные методы решения экономических задач

15. Решения задач линейного программирования геометрическим методом

16. Математические методы в решении экономических задач

Конструктор "Row Boat Kit".
Конструктор для сборки действующей модели «Весельная лодка». Каждый мальчишка, увидев хитроумный механизм, пытается его разобрать, чтобы
317 руб
Раздел: Инженерные, научно-технические
Доска пеленальная "Гном".
Доска для пеленания с жестким деревянным каркасом. Легко устанавливается на перила кроватки, стол, комод или другую устойчивую
789 руб
Раздел: Пеленальные столики, доски
Набор "Водный Мир" №3.
Игрушка для ванной состоит из поля, на котором расположены: водяная мельница для проточной воды (из крана), водяная мельница с ручным
1560 руб
Раздел: Игровые и разнопредметные наборы

17. Совершенствование методов проектирования кораблей и обоснование проектных решений

18. Построение приближенного решения нелинейного уравнения методом Ван-дер-Поля

19. Налоговый контроль: понятие, задачи, формы, виды и методы

20. Постановка и решение транспортной параметрической задачи

21. Метод Винера-Хопфа и его приложения в физических задачах

22. Решение размерных цепей методом полной взаимозаменяемости
23. Решение транспортной задачи с правильным балансом
24. Задача про транспортную систему. Подбор вариантов проезда с учетом кол-ва пересадо, длительности, видов транспорта (самолет, авто, поезд, водн.) (и класса)

25. Решение математических задач в среде Excel

26. Решение оптимизационной задачи линейного программирования

27. Решение обратных задач теплопроводности для элементов конструкций простой геометрической формы

28. Моделирование, как необходимый научный метод познания и его связь с детерминированными и стохастическими методами ИЗУЧЕНИЯ ЛЮБОГО явления или процесса

29. Овладение методикой построения экономико-математических моделей, решение конкретных задач по стратегическому планированию и прогнозированию

30. Решение смешанной задачи для уравнения

31. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

32. О некоторых трудностях, возникающих при решении геометрических задач

Бутылочка для кормления "Avent", 260 мл.
Бутылочка: полипропилен, не содержит бисфенол-А. Соска: силиконовая, не содержит бисфенол-А. Возраст: 0—6 месяцев. При использовании
381 руб
Раздел: Бутылочки
Глобус детский зоогеографический, с подсветкой, 210 мм.
Глобус Земли зоогеографический для детей, с подсветкой. Диаметр: 210 мм. Материал: пластик.
845 руб
Раздел: Глобусы
Настольная игра "Loonacy".
Loonacy (Лунаси) – очень забавная и веселая игра, в которой победит тот, что проворнее и внимательнее. Суть игры заключается в том, чтобы
490 руб
Раздел: Карточные игры

33. Способ устойчивого решения неустойчивых задач и его алгоритм

34. Этапы решения мыслительной задачи

35. Решение управленческих задач

36. Решение обратных задач теплопроводности для элементов конструкций простой геометрическо формы

37. Решение многокритериальной задачи линейного программирования

38. Приемы решения научных задач в русловедении
39. Применение политического дискурс-анализа в решении идеологических задач (На примере медиатизации политических текстов)
40. Использование языка программирования Visual Basic для решения математических задач

41. Математическое моделирование при решении экологических задач

42. Использование Excel для решения статистических задач

43. Использование информационных технологий при решении экономических задач

44. Принципы разработки алгоритмов и программ для решения прикладных задач

45. Решение математических задач с помощью алгоритмического языка Turbo Pascal, Microsoft Excel, пакета MathCAD и разработка программ в среде Delphi

46. Решение математической задачи с помощью математических исследований и помощью специального офисного приложения MS Excel

47. Средства языка программирования Паскаль для решения математических задач

48. Применение неравенств при решении олимпиадных задач

Паста-гель зубная детская "Weleda", 50 мл.
Детский зубной гель с календулой от Weleda разработан специально для детей и обеспечивает естественный уход за молочными зубами,
360 руб
Раздел: Зубные пасты
Качели пластмассовые "Малыш".
В наборе: качели, веревка, пластиковые карабины для регулировки веревок качелей. Материал: пластик. Максимальная нагрузка: 20 кг. Размер:
532 руб
Раздел: Качели
Манеж детский игровой "Динозаврики" (120х100х74 см).
Размер: 120х100х74 см.
679 руб
Раздел: Манежи

49. Методика обучения решению сюжетных задач в курсе математики 5-6 классов

50. Обучение школьников решению составных задач

51. Обучение детей дошкольного возраста решению арифметических задач

52. Педагогическая деятельность. Решение педагогических задач

53. Решение обратных задач динамики

54. Решение статистических задач
55. Методи визначення функції витрат та аналізу ризиків. Метод Монте-Карло
56. Основы решения эконометрических задач

57. Применение линейного программирования для решения экономических задач (оптимизация прибыли)

58. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

59. Решение задач - методы спуска

60. Методы и приемы решения задач

61. Методы решения некорректно поставленных задач

62. Метод выделения единичных вызванных потенциалов из электроэнцефалограммы без использования шаблона

63. Решение задачи методами линейного, целочисленного, нелинейного и динамического программирования.

64. Методы решения задач

Штамп самонаборный "Printer С20-Set", 38x14 мм, синий.
Размер оттиска: 38х14 мм. 4 строк текста, без рамки. Касса шрифта с пинцетом для набора в комплекте. В комплекте: сменная подушка,
492 руб
Раздел: Штемпельная продукция, губочницы
Кошелёк "Pixie Crew" с силиконовой панелью для картинок (чёрный, алфавит).
Повседневные вещи кажутся скучными и однотонными, а тебе хочется выглядеть стильно и быть не как все? "Pixie Crew" сделает твою
799 руб
Раздел: Косметички, кошельки
Бумага "IQ Color", А4, 160 г/м2, 250 листов, черный.
Обладает высокой однородностью цвета и точной нарезкой листа. Применяется для печати на копировально-множительной технике, лазерных и
1124 руб
Раздел: Формата А4 и меньше

65. Метод выделения единичных вызванных потенциалов из электроэнцефалограммы без шаблона

66. Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке

67. Симплекс метод решения задачи линейного программирования

68. Логические задачи и методы их решения

69. Применение методов экономической статистики при решении задач

70. Использование эвристических и экономико-математических методов при решении задач управления
71. Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования
72. Решение дифференциальных уравнений 1 порядка методом Эйлера

73. Система поддержки принятия маркетинговых решений в торговом предприятии на основе методов Data Mining

74. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

75. Математические методы в организации транспортного процесса

76. Метод последовательных уступок (Теория принятия решений)

77. Методы решения систем линейных неравенств

78. Приближённые методы решения алгебраического уравнения

79. Решение дифференциальных уравнений 1 порядка методом Эйлера

80. Итерационные методы решения систем линейных уравнений с неединственными коэффициентами

Плакат электронный "Говорящий Букваренок".
Многим детям понравится представленная оригинальная обучающая игра ''Говорящий Букваренок'', ведь она имеет несколько
429 руб
Раздел: Электронные и звуковые плакаты
Тубус - карта "План покорения МИРА", магнитная, на холодильник.
Подарок заядлому путешественнику. Вы наверняка уже знакомы со знаменитой картой мира, верхний слой которой стирается монетой по принципу
1100 руб
Раздел: Прочее
Маркеры-кисти "Zendoodle. Edding 1340", 10 штук.
Набор фломастеров с гибким наконечником в виде кисточки. Различная толщина линии. Идеально подходит для раскрашивания печатей. Чернила на
664 руб
Раздел: 7-12 цветов

81. Предмет психологии, ее задачи и методы

82. Предмет, метод и задачи бухгалтерского учета (Контрольная)

83. Проблемы и методы принятия решений

84. Методы экспертных оценок при разработке и принятии управленческих решений

85. Модели и методы принятия решений

86. Анализ инвестиционной ситуации. Принятие решений по инвестиционным проектам. Методы оценки эффективности инвестиционных проектов
87. Методология и методы принятия решения
88. Общий аналитический метод решения алгебраических уравнений четвертой степени

89. Решение систем дифференциальных уравнений методом Рунге - Кутты 4 порядка

90. Приближённые методы решения алгебраического уравнения

91. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА

92. Other (Новые представления о задачах и методах гипербарической

93. Математические модели и методы обоснования управленческих решений и сферы их применения в практике управления

94. Модели и методы принятия решения

95. Методы руководства: постановка задач и контроль их выполнения

96. Метод решения уравнений Ньютона - Рафсона

Настольная игра "Запретный Остров. Приключения для смелых!".
Запретный остров – это семейная кооперативная игра, в которой игроки действуют совместно против игры. Вашей команде дерзких искателей
1215 руб
Раздел: Карточные игры
Лоток на 3 отделения, черный.
Применяется для сортировки и временного хранения документов, писем, счетов и другой документации. Неразборный. Количество секций:
352 руб
Раздел: Подставки, лотки для бумаг, футляры
Багетная рама "Bella", 40x50 см (цвет: серебряный + золотой).
Багетные рамы предназначены для оформления картин, вышивок и фотографий. Оформленное изделие всегда становится более выразительным и
651 руб
Раздел: Багетные рамы, для икон

97. Предмет, метод и задачи статистики

98. Формы и методы предъявления задач на уроках физике на материале изучения темы "Изменение агрегатных состояний вещества"

99. Методы анализа управленческих решений

100. Предмет, метод и задачи статистики


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.