Контрольная: Транспортные задачи линейного программирования - текст контрольной. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Контрольная

Транспортные задачи линейного программирования

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Контрольная работа
Язык контрольной: Русский
Дата добавления:   
 
Скачать
Архив Zip, 237 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной работы

Узнайте стоимость написания уникальной работы

9 Лабораторная работа № 5 Телешовой Елизаветы , гр . 726, Транспортные з адачи линейного программирования. 1. Постановка задачи. В некотором царстве , некотором государстве жил-был кот Василий , который очень любил мышей… на обед . А обедал он исключительно в амбаре своего хозяина , да так хорошо , что бедные мыши и носу не могли вы сунуть из своих нор . Но всю жизнь в норе не просидишь , есть то хочется , и стали мыши думать и гадать , как им провести кота Василия и до заветных пищевых ресурсов амбара добраться. В амбаре было 4 мышиных норы : в первой проживало 15 мышей , во второй – 20, в третьей – 10 мышей , а в четвертой – 25 мышей , а также 5 источников пищи , от которых и кормилась вся эта орава мышей : у окорока – 5 мышей , у мешка крупы – 18 мышей , у мешка муки – 17 мышей , у мешка картошки – 22 мыши и у стопки старых газет и журналов эро т ического содержания – 8 мышей. И тут мыши вспомнили , что когда-то в стопке журналов лежала книжка по математическому программированию . Конечно мыши давным-давно успели ее сгрызть , но кое-что из нее они , пока грызли , прочитать успели , в частности , как решат ь транспортные задачи. Считая что – количество мышей из -той норы , питающихся у -того источника пищи , – количество мышей , проживающих в -той норе , – количество мышей , питающихся у -того источника пищи , мыши определили , что для того , чтобы были все они были сыты , необходимо выполнение 2 условий : 1) ; 2) ; ну и конечно Исходя из этих условий они составили математическую модель процесса своего питания : ; ; Ну , и для наглядности нарисовали ее в виде таблицы : Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 18 17 22 8 нора 1 15 нора 2 20 нора 3 10 нора 4 25 В левом верхнем углу каждой ячейки таблицы мыши указали чи сло попавших в лапы кота (в процентах ) по отношению к общему числу мышей из -той норы , питающихся у -того источника пищи . Эти данные они также записали в виде матрицы (в относительных единицах ): . Безусловно , цель мышей – добраться до еды с минимальными потерями по дороге , то есть : . Таким образом : 2. Двойственая задача. Необходимо , конечно , оценить и выгодность передвижения из каждой норы к каждому пищевому ресурсу . Для этого мыши оценили так называемые потенциалы нор ( ) и источников пищи ( ). Так как их цель – минимизировать потери , то сумма потенциалов в каждом случае не должна превышать затрат , т.е . необходимо выполнение следующих условий : (1). Система (1) и будет служить в дальнейшем критерием оптимальности плана. Запишем подробно двойстве нную задачу на основе этого ограничения : ; ; ; ; Критерием двойственной задачи будет максимизация выгоднос ти : 3. Метод последовательной максимальной загрузки выбранных коммуникаций. Первое , что пришло на ум мышам – использовать те источники пищи , доступ к которы м легче , и они решили построить начальный опорный план по методу максимальной загрузки , исходя из формулы : (2). т.е . выбираются те варианты , которые могут о беспечить едой максимальное количество мышей , и эти варианты будут использоваться в соответствии с (2). Поскольку хотят есть все мыши во всех норах , то модель закрытая , т.е. . Общая схема построения начального опорного плана по методу максимальной загрузки такова : 1) Выбираем коммуникацию , которую можно больше всего загрузить. 2) Максимально ее загружаем в соответствии с (2 ). 3) Корректируем объемы производства и потребления на величину выбранной перевозки , вычисляя остатки производства и потребления : ; ; 4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления : если – вычеркиваем -тую строку ; если – вычеркиваем -тый столбец ; 5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты все строки или столбцы В нашем случае это выглядит следующим о бразом : Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 2 0 18 0 17 2 0 22 0 8 0 нора 1 15 0 15 нора 2 20 2 0 18 2 но ра 3 10 2 0 2 8 нор а 4 25 3 0 3 22 Римскими цифрами пронумерован порядок итераций. I . ; ; ; – 4 столбец исключен. II . ; ; ; – 2 столбец исключен. III . ; ; ; – 1 строка исключена. IV . ; ; ; – 5 столбец исключен. V . ; ; ; – 4 строка исключена. VI . ; ; ; – 3 строка и 1 столбец исключены. VII . ; ; ; – 2 строка и 3 столбец исключены. Порассуждав таким образом , мыши получили следующий начальный опорный план : ; . По этому опорному плану коту достанется аж 13 мышей (0,18 часть мыши отдельно вряд ли выживет ). “Жир но ему будет” -, подумали мыши и стали составлять другой опорный план методом северо-западного угла. 4. Метод северо-западного угла. Данный метод очень прост , пункты 1 и 2 в методе максимальной загрузки заменяются на следующий : очередная загружаемая коммуни кация выбирается в левой верхней клетке сохраненной части таблицы , т.е . в северо-западном углу таблицы . Математически это выражается следующим образом : , I – множество номеров пунктов производства ; , J – множество номе ров пунктов потребления ; Последовательно по итерациям метода получаем : I . ; ; ; – 1 столбец исключен. II . ; ; ; – 1 строка исключена. III . ; ; ; – 2 столбец исключен. IV . ; ; ; – 2 строка исключена. V . ; ; ; – 3 столбец исключен. VI . ; ; ; – 3 строка исключена. VII . ; ; ; – 4 столбец исключен. VIII . ; ; ; – 4 строка и 5 столбец исключен ы. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 0 18 8 0 17 5 0 22 17 0 8 0 нора 1 15 10 0 5 10 нора 2 20 12 0 8 12 нора 3 10 5 0 5 5 нора 4 25 8 0 17 8 Получили следующий опорный план : . . Те же самые 13 мышей , и даже хуже предыдущего опорного плана (если у читывать сотые ). Пришлось мышам использовать метод минимальных затрат. 5. Метод минимальных затрат. В этом методе в первую очередь загружаются те коммуникации , в которых затраты на перевозку минимальные . В нашем случае , это те пути , мышиные потери на котор ых минимальны. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 0 18 0 17 0 22 20 18 15 0 8 0 нора 1 15 0 15 нора 2 20 3 0 17 3 нора 3 10 2 0 2 8 нора 4 25 7 2 0 5 18 2 I . ; ; ; – 2 столбец исключен. II . ; ; ; – 1 столбец исключен. III . ; ; ; – 4 строка исключена. IV . ; ; ; – 5 столбец исключен. V . ; ; ; – 3 строка исключена. VI. ; ; ; – 3 столбец исключен. VII. ; ; ; – 2 строка исключена. VIII. ; ; ; – 1 строка и 4 столбец исключены. Опорный план : Целевая функция : Этот опорный план понравился мышам значительно больше , но все равно потери достаточно велики (7 мышей ). Теперь требовалось решить эту задачу и найти оптимальный план . И сделать они это собрались самым точным методом – методом потенциалов. 6. Решение задачи методом потенциалов. Если план действительно оптимален , то система (1) будет выполняться , т.е .: 1) для каждой занятой клетки транспортной таблицы сумма потенциалов долж на быть равна для этой клетки ; 2) для каждой незанятой клетки сумма потенциалов не больше (меньше или равно ) . Построим для каждой свободной переменной плана числа и они должны быть положительны . Так как число потенци алов равно 9, а система состоит из 8 уравнений , то для нахождения какого-либо решения этой системы необходимо первому из потенциалов придать произвольное значение (например : ). Далее последовательно находим значения всех потенциалов . Распишем подробно эту процедуру. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 18 17 22 8 нора 1 15 15 нора 2 20 17 3 нора 3 10 2 8 нора 4 25 5 18 2 Таким образом , после того , как все потенциалы найдены , мо жно искать : Видно , что и меньше нуля , значит существующий опорный план можно улучшить . Поскольку , нужно ввести в базис вектор , соотв етствующий клетке (2; 1), для чего загрузить ее некоторым количеством единиц груза (мышей ). Но , так как мы , увеличивая загрузку (2; 1), нарушаем баланс строк и столбцов распределительной таблицы , то следует изменить объемы поставок в ряде других занятых к л еток . А чтобы число базисных переменных осталось прежним , необходимо вывести из базиса одну переменную . Выводится обычно та переменная , у которой загрузка в цикле минимальна. Строим цикл : (2 ; 1) – начальная точка цикла ; Что характерно , для этой точки (впро чем как и для других ) мы можем построить только один цикл . Каждой клетке цикла приписываем определенный знак : (2 ; 1) – “ +” , (4; 1) – “-” , (4; 4) – “ +” (2; 4) – “-”. Пища Норы окорок мешок крупы мешок муки мешок картошки ж урналы 5 18 17 22 8 нора 1 15 15 нора 2 20 17 3 нора 3 10 2 8 нора 4 25 5 18 2 В клетках с “ +” – увеличиваем загрузку , а в клетках с “-” – уменьшаем . Величина , на которую увеличиваем или уменьшаем всегда одна и она определяется из условия : , где – содержимое клеток с “-”. Таким образом получаем : , а значит из базиса будет выведена (2 ; 4), где в процессе реализации цикла загрузка уменьшится до 0 . Перейдем к новому опорному плану Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 18 17 22 8 нора 1 15 15 нора 2 20 3 17 нора 3 10 2 8 нора 4 25 2 18 5 Определяем Все больше 0, следовательно план оптимальный. . Целевая функция при этом плане : М-да , незначительное улучшение для мы шей . Целых 6 мышей и еще один мышиный хвостик – такова ежедневная дань коту Василию . Но делать нечего , и стали мыши действовать по этому плану. 7. Открытая модель. И все было бы хорошо , но в 3 норе появился дополнительный приплод – 10 мышей , следовательно в ней стало проживать 20 мышей , а количество мышей , питающихся у источников пищи , осталось тем же . Получилась так называемая открытая модель , где : (3) и ее необходимо сбалансировать . Для этого нужно ввести фиктивный пункт потребления с объемом потребления : ; и дополнительные переменные приводящие ограничение-неравенство (3) к виду равенств и понимание как фиктивные перевозки из пунктов производства в фиктивный пункт потребления . Новая математическая модель : ; ; При этом во 2 и 3 норах все мыши должны быть накормлены (во второй – самые умные мыши , а в третьей – большой приплод ), поэтому второе и треть е ограничения – уравнения . В первое и четвертое ограничения добавим новые переменные R 1 и R 4 для уравновешивания системы . А так как этих источников пищи на самом деле нет , то и затраты (потери по дороге ) на них нулевые. В транспортной таблице в последнем с толбце введем еще 2 переменные в (2; 5) и (3; 5) – R 2 и R 3 , чтобы столбец был полностью заполнен , а так как перевозки в этих коммуникациях не должны быть , то наложим на них очень большие штрафы М и включим все новые переменные в целевую функцию : Так как критерий стремится к минимуму , то в оптимальном плане перевозки с самыми большими затратами не должны осуществляться (т.е . ). Напишем новую транспортную таблицу и найдем начальный опорный план методом минимальных затрат. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы R 5 0 18 15 0 17 0 22 10 0 8 0 10 5 0 нора 1 15 5 10 5 нора 2 20 3 0 3 17 нора 3 2 0 12 0 12 8 нора 4 25 10 5 0 5 15 5 Определяем . меньше 0, поэтому существующий опорный план можно улучшить . Поскольку – наибольший , то мы будем вводить в базис вектор , соответствующий клетке (4; 4). Строим цикл и переходим к новому опорному плану. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы R 5 18 17 22 8 10 нора 1 15 5 10 но ра 2 20 3 17 нора 3 2 0 12 8 нора 4 25 5 15 5 Определяем меньше 0, поэтому существующий опорный план можно также улучшить . Теперь мы будем вводить в базис векто р , соответствующий клетке (2; 1). Строим цикл и переходим к новому опорному плану. Пища Норы окорок мешок крупы мешок муки мешок картошки журналы R 5 18 17 22 8 10 нора 1 15 5 10 нора 2 20 3 17 нора 3 2 0 12 8 нора 4 25 2 18 5 Определяем Все больше 0, следовательно план оптимальный. . Целевая функция при этом плане : Этот план чуть хуже предыдущего , к тому же 10 мышей из первой норы остаются голодны ми . Во всяком случае питаются раз в три дня. 8 . Запрещенные перевозки. Но кот Василий тоже не дремал , и , произведя те же операции , что и мыши в свое время , определил оптимальный план их передвижений (см . пункт 6). Посмотрев на него , он сразу решил взять по д особый контроль путь от второй норы к мешку муки и от четвертой норы к мешку крупы . Вскоре мыши это на себе почувствовали , а почувствовав , кинулись составлять новый оптимальный план , пометив эти два маршрута как чрезвычайно опасные буквой М Пища Норы окорок мешок крупы мешок муки мешок картошки журналы 5 18 17 22 8 Нора 1 15 15 Нора 2 20 2 18 Нора 3 10 2 8 Нора 4 25 3 17 5 Видно , что этот план уже является оптимальным. Целевая функция : . Как зыбко мышиное счастье . Стоило коту взяться за дело всерьез , и потери возросли чуть ли не в два раза.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Окей Гугл, как избавиться от трупа?
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru