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

Контрольная

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

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

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

закрыть
Категория: Контрольная работа
Язык контрольной: Русский
Дата добавления:   
 
Скачать
Архив Zip, 237 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

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



Лабораторная работа № 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, пока не будут перечеркнуты все строки или столбцы

В нашем случае это выглядит следующим образом:

Пища

VII

VI

V

IV

III

II

I

Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

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 столбец исключены.

Пища

VIII

VII

VI

V

IV

III

II

I

Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

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. Метод минимальных затрат.

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

Пища

VIII

VII

VI

V

IV

III

II

I

Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

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 норах все мыши должны быть накормлены (во второй – самые умные мыши, а в третьей – большой приплод), поэтому второе и третье ограничения – уравнения. В первое и четвертое ограничения добавим новые переменные R1 и R4 для уравновешивания системы. А так как этих источников пищи на самом деле нет, то и затраты (потери по дороге) на них нулевые.

В транспортной таблице в последнем столбце введем еще 2 переменные в (2; 5) и (3; 5) – R2 и R3 , чтобы столбец был полностью заполнен, а так как перевозки в этих коммуникациях не должны быть, то наложим на них очень большие штрафы М и включим все новые переменные в целевую функцию:

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

Пища

-

-

+

+

VII

VI

V

IV

III

II

I

VIII

Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

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

20 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

20

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

20

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




Видно, что этот план уже является оптимальным.

Целевая функция:

.

Как зыбко мышиное счастье. Стоило коту взяться за дело всерьез, и потери возросли чуть ли не в два раза.

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Экономико-математическое моделирование
91Экономическая теория

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

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

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

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


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