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

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

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

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

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

Таблица 7.8

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

Преподаватели	Почасовая оплата курсов

Решение

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. Что представляет собой целевая функция?

МАКРОСЫ

Макрос – список инструкций, которые Excel может выполнять автоматически. Создавать макросы можно автоматически с помощью макрорекордера или с помощью языка программирования VISUAL BASIC.

Рассмотрим процесс автоматического создания макроса. Для этого выполним команду Сервис – Макрос – Начать запись. Откроется диалоговое окно (рис.8.1).

Рис.8.1. Диалоговое окно Запись макроса

В этом окне вы должны будете определить название макроса (имя макроса – совокупность букв, цифр и символа подчеркивания, начинающаяся с буквы). Макросу можно назначить быструю комбинацию клавиш (для этого необходимо подключить флажок клавишу быстрого вызова и определить саму комбинацию клавиш). Но даже если вы не подключите макрос к пункту меню Сервис и не определите комбинацию клавиш для вызова макроса, то все равно сможете вызывать макрос с помощью команды Сервис – Макрос. Макрос будет создаваться на языке VISUAL BASIC. Теперь давайте определимся, где будет храниться текст макроса. Для этого рассмотрим группу Сохранить. Текст может храниться в данной рабочей книге (пункт Эта книга), в новой книге (пункт Новая книга), либо в специальной рабочей книге макросов (пункт Личная книга макросов).

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

Рассмотрим пример создания следующего макроса.

Необходимо создать макрос, который выделенные значения приводит к числовому формату с двумя знаками после запятой. Значения выводятся зелёным цветом. Размер шрифта – 16, полужирный, курсив.

Для этого выполним команду Сервис – Макрос – Запись макроса.

Откроется диалоговое окно, аналогичное окну, изображённому на рис.8.1.

Определим имя макроса (например, Пример). В открывшемся диалоговом окне можно установить следующие параметры:

1) Подключить флажок Назначить макросу клавишу быстрого вызова, и назначить комбинацию клавиш для быстрого вызова данного макроса;

2) Определить, где сохранять макрос.

Щёлкнем по кнопке OK. Начинаем запись макроса. На экране появляется панель Останов. После окончания записи мы щёлкнем для останова записи. Выполним команду Формат – Ячейки. В диалоговом окне на вкладке Число выбираем из форматов Числовой, число десятичных знаков установим два. На вкладке Шрифт установим начертание полужирный курсив размер шрифта 16, цвет зелёный. Щёлкнем по кнопке OK. Закроем окно Формат ячеек. Остановим запись макроса, щёлкнув по первой кнопке панели Останов.

Теперь можно проверить функционирование макроса. Для этого выделим на рабочем листе область с числовым материалом и запустим макрос Пример. Убедимся, что значения приведены к числовому формату с двумя знаками после запятой. Значения выводятся зелёным цветом, размер шрифта – 16, полужирный, курсив. Запускать макрос можно:

а) с помощью назначенной комбинации клавиш;

б) выполнив команду Сервис – Макрос – Макросы (Alt-F8) и выбрав макрос Пример, щелкнуть по кнопке Выполнить.

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

1. Что представляет собой макрос?

2. Как создать макрос?

3. Как запустить макрос на выполнение?

4. Сколько раз можно выполнять макрос?

5. На какой язык будет автоматически записываться макрос при создании?

ЛАБОРАТОРНАЯ РАБОТА №1