Метод оптимальных решений

 

Таблица 4.12

Таблица 4.13

№	1	2	3	4
1	-2	0	2	0
2	-2	-2	2	-2
3	0	1	0	1
4	4	0	0	0

 

 

Теперь прибавим 2 к каждому  числу вычеркнутых строк в  преобразованной таблице. Получим  табл. 4.14.

Таблица 4.14

 

 

Вновь сделаем назначение, отметив по порядку нули в табл. 4.14.

Это назначение является полным, так как число отмеченных нулей  равно 4. Получено следующее назначение:

первый ученый назначается  научным руководителем первого  проекта: х₁₁ = 1;

второй ученый — научный  руководитель второго проекта: х₂₂ = 1;

третий ученый — научный  руководитель третьего проекта: х₃₃ = 1;

четвертый ученый — научный руководитель четвертого проекта: х₄₄ = 1.

Время выполнения четырех  проектов: С = 3 + 4 + 2 + 8 = 17.

Данное назначение не единственное. Если во второй строке сначала отметить не второй, а четвертый нуль, получим  следующее назначение (табл. 4.15):

Таблица 4.15

первый ученый руководит  первым проектом: х₁₁= 1;

второй ученый руководит  четвертым проектом: х₂₄ ⁼ 1;

третий ученый руководит  третьим проектом: х₃₃ = 1;

четвертый ученый руководит  вторым проектом: х₄₂ =1;

Время на выполнение проектов не изменилось: 

 

С=3*1+5*1+2*1+7*1=17 

 

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

Заметим, что результат, полученный по венгерскому методу, не изменится, если в алгоритме заменить строки на столбцы, и наоборот. 

 

4.7. Применение  задачи о назначениях к решению  экономических проблем

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

 

4.7.1. Оптимальное  исследование рынка 

 

Группе, исследующей рынок, требуется получить данные из п различных мест. В ее распоряжении имеется п дней, и она предлагает провести по одному дню в каждом месте, проведя по a_j опросов,  . Вероятность успешного опроса в каждом месте деется матрицей Р. Элемент матрицы Р_ijхарактеризует вероятность успешного опроса в течение i-го дня в j-м месте,  , .

Определить время проведения опросов, при котором общее число  опросов максимально.

Решение

Сведем данную задачу к  задаче о назначениях.

Введем величину r_ij = p_ija_j, показывающую число успешных опросов j -м месте в течение i-го дня.

	если в i -й день опрос проводится в j -м месте;
	в противном случае

 

 

Математическая модель задачи имеет следующий вид:        

Функция R характеризует суммарное число опросов. Его нужно максимизировать. Первое и второе ограничения соответствует тому, что в течение одного дня можно находиться только в одном месте. Для расчета модели венгерским методом надо перейти противоположной функции                                   

                                                 

 

4.7.2. Оптимальное  использование торговых агентов  

 

Торговая фирма продает  товары в п различных городах, покупательная способность жителей которых оценивается в b_j условных единиц,  .Для реализации товаров фирма располагает п торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен; доля реализуемых i -м торговым агентом покупательных способностей составляет a_i,  . Как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров?

Решение.

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

Введем параметр с_ij = a_ib_j, характеризующий величину покупательных способностей, реализуемых i-м торговым агентом в j-м городе.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         

Управляющие переменные х_ij,  , , и определяются по формуле

	если в i -й агент напрвлен в j -м город;
	в противном случае

 

     

Первое и второе ограничения  формализуют соответственно условия  о том, что в каждый город направляется один торговый агент, и один торговый агент не может работать в двух городах. Целевая функция С — это сумма реализованных покупательных способностей   всеми торговыми агентами во всех городах. Она должна быть максимальна. Для решения задачи венгерским методом надо, как в предыдущем примере, перейти к противоположной функции. 

 

Задачи  и упражнения к главе 4

1. Найти начальное решение транспортной задачи методом северо-западного угла:  

 

№	1	2	3	4	Предложение
1	7	8	1	2	160
2	4	5	9	8	140
3	9	2	3	6	200
Спрос	120	80	190	110

 

 

2. Найти начальное решение  транспортной задачи методом  минимального элемента (транспортная  таблица задачи 1).

3. Найти начальное решение  транспортной задачи методом  Фогеля (транспортная таблица задачи 1).

4. Найти оптимальное решение  транспортной задачи, начальное  решение получено методом северо-западного  угла (транспортная таблица задачи 1).

5. Найти оптимальное решение  транспортной задачи, начальное  решение получено методом минимального  элемента (транспортная таблица  задачи 1).

6. Найти начальное решение  транспортной задачи, своим методом  (транспортная таблица задачи 1).

7. Решить задачу 1 симплекс  методом.

8. Решить задачу о назначениях  венгерским методом, Матрица времен приведена ниже

9. Решить задачу о назначениях  венгерским методом, Матрица времен приведена ниже

10. Решить задачу о назначениях  венгерским методом, Матрица времен приведена ниже

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                         Презентация.

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

Среди огромного числа проблем, которые волнуют всех, требуя незамедлительного  решения, основополагающей становится организация и обеспечение процесса становления личности, способной  адекватно ориентироваться, свободно избирать свою позицию и действовать  в современном конфликтном, динамично  меняющемся мире. Интеграция ориентирована  на подготовку выпускника к жизни  в современном обществе, к достойному выбору собственной жизненной и  профессиональной позиции; способствует развитию креативности, коммуникативных  способностей.

Актуальность проблемы обосновывается необходимостью изменения структуры  и содержания школьных курсов в рамках профильного обучения. Сложившаяся  школьная система не решает многие проблемы профильного обучения: пока нет достаточного научного обоснования  определённого и готового к реализации содержания профильного обучения, не определён эталонный и просто необходимый уровень общей и  предпрофессиональной компетентности, достаточный для продолжения  образования. Все, связанное с профильным обучением, находится сегодня в  стадии становления.

В классах или образовательных  учреждениях разного профиля  и предметы должны иметь разное содержание. Эта идея все ещё не находит  своего места в практике. В школах России появляется все больше и больше профильных классов. Профилируются  и сами школы. Однако почти всюду  это происходит по одному и тому же сценарию: увеличивается число  часов на профильные предметы, вводятся дополнительные предметы, ради этого  урезаются часы остальных, но почти  никакого влияния на их содержание этот процесс не оказывает. В результате ученики математического класса и гуманитарной гимназии изучают  одну и ту же математику - разница  лишь в том, что в первом случае все теории доказываются и задачи решаются трудные, а во втором никакие  теоремы не доказываются, некоторые  не упоминаются вовсе, решаемые задачи примитивны и неинтересны.

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

Цель работы:

показать пути совершенствования  математической подготовки и развития навыков моделирования реальных процессов учащихся профильных классов;

отразить прикладные возможности  математики.

1 Основы математического  моделирования

Учителю интеграция предметов позволяет  воспитывать у ребят охоту  к целенаправленному преодолению  трудностей на пути познания. Новые  функции педагога главным образом  определяются необходимостью чёткого  представлять структуру учебной  деятельности и свои действия на каждом этапе от возникновения замысла  до полного его осуществления.

Приведём пример простейшей математической модели. Представим себе, что нужно  определить площадь пола комнаты. Реальный объект - пол комнаты - заменяется абстрактной

математической моделью - прямоугольником.

Математическая модель, основанная на некотором упрощении, никогда  не бывает тождественна рассматриваемому объекту, не передаёт всех его свойств  и особенностей, а является его  приближённым отражением. Однако в  результате замены реального объекта  соответствующей ему моделью  появляется возможность математически  сформулировать задачу его изучения и воспользоваться для анализа  его свойств математическим аппаратом, который не зависит от конкретной природы данного объекта. Этот аппарат  позволяет единообразно описать  широкий круг фактов и наблюдений, провести их детальный количественный анализ, предсказать, как поведёт  себя объект в различных условиях, т.е. прогнозировать результаты будущих  наблюдений.