Компьютер
<<  Задача о назначениях Компьютер в жизни школьника  >>
Картинок нет
Картинки из презентации «Задача о назначениях» к уроку информатики на тему «Компьютер»

Автор: user. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока информатики, скачайте бесплатно презентацию «Задача о назначениях.ppt» со всеми картинками в zip-архиве размером 107 КБ.

Задача о назначениях

содержание презентации «Задача о назначениях.ppt»
Сл Текст Сл Текст
1Задача о назначениях. Венгерский метод 10= 8 – 1 = 7 > 0 ?31 = 13 – (4 + 21) =
решения задачи о назначениях. Малофеевой 13 – 25 = -12 < 0 ?33 = 16 – (4 + 9) =
Екатерины гр. ММ-61. 16 – 13 = 3 > 0 ?42 = 15 – (-17 + 10) =
2Возможные варианты задачи о 15 + 7 = 22 > 0 ?43 = 13 – (-17 + 9) =
назначениях: Ресурсы. Потребители. 13 + 8 = 23 > 0 ?44 = 19 – (-17 + 7) =
Критерий эффективнос-ти. Рабочие. Работа 19 +10 = 29 > 0.
(рабочие места). Время выполнения (мин). 11Цикл для ?11 : После перераспределения
Автомобили. Маршруты. Объём перевозимой груза строим новую таблицу с найденным
продукции. Станки. Работа (участки). Мин. решением.
время или макс. производительность. 12Найденный план является оптимальным:
3Задача о назначениях. Решим задачу как x13=1;x22=1;x34=1;x41=1 L(x) = 9+4+11+4=28
транспортную: Пример: Пусть имеется 4 y.e. Таблица с третьим решением. b1=1.
сотрудника фирмы, которых необходимо b2=1. b3=1. b4=1. a1=1. 2 0. 10. 9 1. 7.
закрепить за выполнением 4х работ. a2=1. 15. 4 1. 14. 8. a3=1. 13. 14. 16. 11
Известны производительности каждого из 1. a4=1. 4 1. 15. 13. 19.
сотрудников по каждой работе: 13Венгерский метод решения задачи о
4Строим первое опорное решение: b1=1. назначениях. Алгоритм решения: 1. Решаем
b2=1. b3=1. b4=1. a1=1. 2 1. 10. 9. 7 1. задачу на минимум. Цель данного шага –
a2=1. 15. 4 1. 14. 8. a3=1. 13. 14 0. 16. получение максимально возможного числа
11 1. a4=1. 4 0. 15. 13 1. 19. нулей в матрице С. Для этого находим в
51). Проверяем открытая или закрытая матрице С в каждой строке минимальный
транспортная задача по формуле: 4=4 => элемент и вычитаем его из каждого элемента
транспортная задача закрытая 2). Проверяем соответствующей строки. Аналогично в
первое опорное решение на оптимальность каждом столбце вычитаем соответствующий
методом потенциалов. Количество минимальный элемент. Если задана не
заполненных клеток должно равняться квадратная матрица, то делаем её
выражению: m + n-1. если недостаёт квадратной, проставляя стоимости равными
заполненных клеток, то в 1 из пустых максимальному числу в заданной матрице.
клеток вводим нулевую поставку груза. 142. Если после выполнения первого шага
4+4-1=7. можно произвести назначения, то есть в
6Для заполненных клеток выполняется каждой строке и столбце выбрать нулевой
соотношение: ui + vj = Cij. u1 + v1=2 u1 элемент, то полученное решение будет
=0 u1 + v4=7 u2= -6 u2 + v2=4 u2= -6 u3 + оптимальным. Если назначения провести не
v2=14 u3 = 4 u3 + v4=11 u4 = 2 u4 + v1 =4 удалось, то переходим к третьему шагу. 3.
v1 = 2 u4 + v3=13 v2 = 10 u1 =0 v3 = 11 v4 Минимальным числом прямых вычёркиваем все
= 7. нули в матрице и среди не вычеркнутых
7Подсчитаем оценки ?ij свободных клеток элементов выбираем минимальный, его
по формуле: Если все ?ij не отрицательны, прибавляем к элементам, стоящим на
то план оптимален. Если же существуют пересечении прямых и отнимаем от всех не
?ij<0, то необходимо улучшить первый вычеркнутых элементов. Далее переходим к
опорный план, перераспределив поставки. шагу 2. Венгерский метод наиболее
?ij= Cij – (ui + vj). ?12 = 10 – (0 +10) = эффективен при решении транспортных задач
10 – 10 = 0 ?13 = 9 – (0 + 11) = 9 – 11 = с целочисленными объемами производства и
-2 <0 ?21 = 15 – (-6 +2) = 15 + 4 = 19 потребления.
>0 ?23 = 14 – (-6 + 11) = 14 – 5 = 9 15Пример: Дана матрица: 2 10 9 7 15 4 14
>0 ?24 = 8 – (-6 + 7) = 8 – 1 = 7 >0 8 13 14 16 11 4 15 13 19. Решим её
?31 = 13 – ( 4 + 2) = 13 – 6 = 7 >0 ?33 венгерским методом. 1.найдём в каждой
= 16 – (4 + 11) = 16 – 15 = 1 >0 ?42 = строке минимальное значение и вычтем его
15 – (2 + 10) = 15 – 12 = 3 >0 ?44 = 19 из каждого элемента данной строки. 2 10 9
– (2 + 7) = 19 – 9 = 10 >0. 7 15 4 14 8 13 14 16 11 4 15 13 19. 0 8 7
8Вывод: первый план не является 5 11 0 10 4 2 3 5 0 0 11 9 15. Получим
оптимальным. Для его улучшения найдём матрицу:
клетку с наибольшей по абсолютной величине 162.Назначение сотрудников провести
отрицательной ?ij и составим цикл нельзя. Выберем в каждом столбце матрицы
перераспределения поставок. Составляем минимальный элемент и вычтем его из
цикл для ?13: После перераспределения каждого элемента данного столбца: 0 8 7 5
груза строим новую таблицу с найденным 11 0 10 4 2 3 5 0 0 11 9 15. 0 8 2 5 11 0
вторым решением. + 1-. 1- +. 1. 1. 5 4 2 3 0 0 0 11 4 15. 3.Назначение
9Таблица со вторым решением. b1=1. провести нельзя. Минимальным числом прямых
b2=1. b3=1. b4=1. a1=1. 2. 10. 9 1. a2=1. вычеркнем все нули в матрице. Среди не
15. 4 1. 14. a3=1. 13. 14 0. a4=1. 4 1. 7. вычеркнутых элементов выберем минимальный.
8. 16. 11. 15. 13. 19. Прибавим его к элементам, стоящим на
10Проверяем решение на оптимальность. пересечении прямых и вычтем из всех не
u1+v3=9 u1= 0 u1+v4=7 u2= -6 u2+v1=15 u3= вычеркнутых элементов. Получим матрицу:
4 u3+v2=4 u4= -17 u3+v2=14 v1= 21 u3+v4=11 Назначения проведены: 1й сотрудник
v2= 10 u4+v1=4 v3= 9 u1=0 v4= 7 Решение не выполняет 3ю работу; 2й-выполняет 2ю
оптимально, т.к. ?11 <0, работу; 3й-выполняет 4ю работу;
=>составляем цикл для ?11. ?11 = 2 – (0 5й-выполняет 1ю работу. 0 8 2 5 11 0 5 4 2
+ 21) = 2 – 21 = - 19 < 0 ?12 = 10 – (0 3 0 0 0 11 4 15. 0 8 0 3 11 0 3 2 4 5 0 0
+ 10) = 10 – 10 = 0 = 0 ?23 = 14 – (-6 + 0 11 2 13.
9) = 14 – 3 = 11 > 0 ?24 = 8 – (-6 + 7)
Задача о назначениях.ppt
http://900igr.net/kartinka/informatika/zadacha-o-naznachenijakh-260666.html
cсылка на страницу

Задача о назначениях

другие презентации на тему «Задача о назначениях»

«Ракетные войска стратегического назначения» - Какую роль в становлении РВСН сыграл Петр I? Пользуясь дополнительной информацией составьте каталог ракет стратегического назначения. Из дополнительной информации выберите технические характеристики СК «Тополь – М»5. Ракетные войска стратегического назначения. Выделите особенности национальной техники.

«Назначение компьютерных сетей» - Развитие умений самостоятельной работы с информацией. Развитие познавательного интереса, творческой активности, воспитание информационной культуры. Компьютерные сети. Простейшая компьютерная сеть. Назначение компьютерных сетей. Крупные локальные сети объединяются в глобальные сети. Глобальные сети — охватывают большие территории: страны, континенты.

«Назначение и устройство компьютера» - Структура компьютера. Flash Drive USB Накопители. В н е ш н я я п а м я т ь. Устройства в ы в о д а. Принципы фон неймана. В чем заключается принцип фон Неймана? В памяти компьютера х р а н я т с я данные и программы. Карты памяти. Аналогия между компьютером и человеком. Устройства в в о д а. Объём ОЗУ может быть от 4 до 64 Мбайт.

«Компьютер и его назначение» - В оперативной памяти ПК находится операционная система, драйверы устройств, исполняемые программы. И как следствие, общая производительность ПК в основном определяется скоростью процессора. Накопитель на жестком магнитном диске (HDD). Накопитель на компакт-дисках (CD-ROM drive). Звуковая карта (Sound card).

«Управление компьютером» - Системное ПО отвечает за управление аппаратными ресурсами, а так же осуществляет непосредственный диалог с пользователем. Прикладное ПО представляет собой систему, предназначенную для решения задач определенного класса. Програмное управление компьютером. Файловая система включает в себя: Различают два основных вида ПО: Системное программное обеспечение и прикладное программное обеспечение.

«Удаленное управление ПК» - DameWare NT Utilities 5.5.0.2. Программы для удаленного устройства. Вариант RealVNC Personal Edition предлагает ряд дополнительных возможностей. Atelier Web Remote Commander 5.59. Из явных недостатков можно выделить отсутствие справки. EMCO Remote Desktop Professional 4.0. Средств для удаленной установки модуля TightVNC Server не имеется.

Компьютер

49 презентаций о компьютере
Урок

Информатика

130 тем
Картинки