Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Симплекс метод решения задачи линейного программирования

Название: Симплекс метод решения задачи линейного программирования
Раздел: Рефераты по информатике, программированию
Тип: контрольная работа Добавлен 20:14:13 04 ноября 2010 Похожие работы
Просмотров: 48 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Задача №1 (Симплекс метод решения задачи линейного программирования.)

Найти Fmax = 9x1 + 10x2 + 16x3, при ограничениях:

Запишем задачу в каноническом виде:

F=9x1 + 10x2 + 16x3 →max

Заполним начальную таблицу:

Таблица 0.

0 9 10 16 0 0 0

Отношение,

θ

i Базис
1 0 360 18 15 12 1 0 0 30
2 0 192 6 4 8 0 1 0 24
3 0 180 5 3 3 0 0 1 60
∆j 0 -9 -10 -16 0 0 0
Zj 0 0 0 0 0 0 0

Zj вычисляется по формуле

Оценки (∆j) вычисляются по формуле , где - коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «θ», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент.

Заполняем новую таблицу

Таблица 1.

0 9 10 16 0 0 0

Отношение,

θ

i Базис
1 0 72 9 9 0 1 0 8
2 16 24 1 0 0 48
3 0 108 0 0 - 1 72
∆j 384 3 -2 0 0 2 0
Zj 384 12 8 0 0 2 0

Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.

Столбец становится базисным, то есть единичным.

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «θ»

По минимальному значению определяем направляющую строку.

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.

Таблица 2.

0 9 10 16 0 0 0

Отношение,

θ

i Базис
1 10 8 1 1 0 - 0 ______
2 16 20 0 1 - 0 ______
3 0 96 0 0 - 1 ______
∆j 400 5 0 0 0
Zj 400 14 10 16 0

Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.

Ответ:

Максимальное значение функции Fmax =400 достигается в точке с координатами:

=0

=8

=20

=0

=0

=96

Задача №2 (Метод Литтла)

Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.

Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

, и т.д.)

1 2 3 4 5 6
1 18,87 49,48 51,86 80,51 97,42
2 18,87 32,06 34,48 65,15 84,01
3 49,48 32,06 31,76 61,19 83,20
4 51,86 34,48 31,76 32,14 53,15
5 80,51 65,15 61,19 32,14 22,14
6 97,42 84,01 83,20 53,15 22,14

Предположим что кратчайший путь будет следующим:

т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит

Решение: Первый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)


1 2 3 4 5 6
1 18,87 49,48 51,86 80,51 97,42 18,87
2 18,87 32,06 34,48 65,15 84,01 18,87
3 49,48 32,06 31,76 61,19 83,20 31,76
4 51,86 34,48 31,76 32,14 53,15 31,76
5 80,51 65,15 61,19 32,14 22,14 22,14
6 97,42 84,01 83,20 53,15 22,14 22,14

1 2 3 4 5 6
1 0 30,61 32,99 61,64 78,55
2 0 13,19 15,61 46,28 65,14
3 17,72 0,30 0 29,43 51,44
4 20,10 2,72 0 0,38 21,39
5 58,37 43,01 39,05 10,00 0
6 75,28 61,87 61,06 31,01 0
0 0 0 0 0 0

1 2 3 4 5 6
1 0 30,61 32,99 61,64 78,55
2 0 13,19 15,61 46,28 65,14
3 17,72 0,30 0 29,43 51,44
4 20,10 2,72 0 0,38 21,39
5 58,37 43,01 39,05 10,00 0
6 75,28 61,87 61,06 31,01 0

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).

1 2 3 4 5
1 0 30,61 32,99 61,64
2 0 13,19 15,61 46,28
3 17,72 0,30 0 29,43
4 20,10 2,72 0 0,38
6 75,28 61,87 61,06 31,01

Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.

Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1 2 3 4 5
1 0 30,61 32,99 61,64
2 0 13,19 15,61 46,28
3 17,72 0,30 0 29,43
4 20,10 2,72 0 0,38
6 75,28 61,87 61,06 31,01
0 0 0 0 0,38

1 2 3 4 5
1 0 30,61 32,99 61,26
2 0 13,19 15,61 45,90
3 17,72 0,30 0 29,05
4 20,10 2,72 0 0
6 75,28 61,87 61,06 31,01

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).

1 3 4 5
2 13,19 15,61 45,90
3 17,72 0 29,05
4 20,10 0 0
6 75,28 61,06 31,01

Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1 3 4 5
2 13,19 15,61 45,90
3 17,72 0 29,05
4 20,10 0 0
6 75,28 61,06 31,01
17,72 0 0 0

1 3 4 5
2 13,19 15,61 45,90 13,19
3 0 0 29,05 0
4 2,38 0 0 0
6 57,56 61,06 31,01 31,01

1 3 4 5
2 0 2,42 32,71
3 0 0 29,05
4 2,38 0 0
6 26,55 30,05 0

Шаг 2. Определим оценки нулевых клеток:


Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).

1 3 4
2 0 2,42
3 0 0
6 26,55 30,05

Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1 3 4
2 0 2,42 0
3 0 0 0
6 26,55 30,05 26,55

1 3 4
2 0 2,42
3 0 0
6 0 3,50

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).


1 3
2 0
6 0

Пятый этап.

Остались не задействованными связи 2 – 3 и 6 – 1.

В результате получаем следующую цепочку:

1→ 2→ 3 → 4→ 5→ 6 →1

Длина пути составляет:

L=18,87+32,06+31,76+32,14+22,14+97,42=234,39

это и есть кратчайший путь.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:41:53 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:48:54 28 ноября 2015

Работы, похожие на Контрольная работа: Симплекс метод решения задачи линейного программирования

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150758)
Комментарии (1839)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru