Учебное_пособие_по_Excel1. В инженерных и экономических расчетах

• Название: В инженерных и экономических расчетах
• Дата: 21.05.2022
• Размер: 4.49 Mb.
• Имя файла: Учебное_пособие_по_Excel1.doc
• Тип: Учебное пособие; #541241
• страница: 17 из 29

7.4. Решение задач дискретного программирования

Дискретное программирование изучает экстремальные задачи, в которых на искомые переменные накладывается условие дискретности, а область допустимых решений конечна. Это, прежде всего, задачи с физической неделимостью многих факторов и объектов расчета. К дискретному программированию относят также ряд задач целочисленного программирования, в которых искомые переменные принимают только целочисленные значения (например, задача о планировании штатного расписания) или логические, булевы значения – нуль или единица (например, задача о назначениях). Рассмотрим решение задачи о назначениях.

Пример 7.4. Задача о назначениях

Каждый преподаватель может провести определенные виды занятий. Почасовая оплата c_ij i-му преподавателю по j-му виду занятий приведена в таблице 7.8.

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

Таблица 7.8

Стоимость выполнения работы

Преподаватели	Почасовая оплата курсов
	1	2	3	4
1	350	420	610	200
2	890	130	650	900
3	430	520	600	720
4	830	610	780	470

Решение

1. 
   Проверка задачи на сбалансированность. Задача является сбалансированной, так как количество преподавателей соответствует числу возможных видов занятий. В случае несбалансированности задачи необходимо ввести недостающее число фиктивных преподавателей (строчек) или видов занятий (столбцов).
   
2. 
   Построение математической модели задачи. Пусть x_ij=1 в случае выполнения I-м преподавателем j-го вида занятий, и x_ij= 0 – в случае невыполнения вида занятий. Тогда математическая модель задачи примет вид:
   

а) найти минимум функционала:



б) при следующих ограничениях:



Решение задачи с помощью надстройки Поиск решения:

• 
  подготовку рабочего листа осуществляем в соответствии с рис. 7.14, устанавливаем ограничения в окне Поиск решения, как показано рис. 7.15;
  
• 
  в окне Параметры поиска решения необходимо также установить флажок Линейная модель;
  
• 
  решение задачи представлено на рис. 7.16.
  

Рис. 7.14. Подготовка рабочего листа для решения задачи о назначениях



Рис. 7.15 Установка параметров в окне Поиск решения
для задачи о назначениях



Рис. 7.16. Решение задачи о назначениях

КОНТРОЛЬНЫЕ ВОПРОСЫ К РАЗДЕЛУ 7

1. 
   Каково назначение надстроек Поиск решения и Подбор параметра?
   
2. 
   Как установить надстройки Поиск решения и Подбор параметра?
   
3. 
   Какие задачи решаются с помощью подбора параметра?
   
4. 
   Какие задачи можно решить, используя Поиск решения?
   
5. 
   Какие отчеты о поиске решения можно получить для анализа решения?
   
6. 
   Что представляет собой целевая функция?