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

Цель: научиться решать задачи дискретного программирования.

 

Теоретическое введение

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

В автотранспортном предприятии для перевозок пассажиров используются автобусы различной вместимости. Каждый из автобусов, работая по заданному маршруту, может перевести определенное количество пассажиров. Почасовая оплата с_ij i-му водителю по j-му виду перевозок приведена в табл. 6.1. Составить план работы водителей таким образом, чтобы все плановые перевозки были выполнены, каждый водитель работал только по одному маршруту, а суммарная стоимость почасовой оплаты была минимальной.

Таблица 6.1

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

Водитель	Оплата

 

Решение задачи сводится к реализации следующих этапов:

1. Проверка задачи на сбалансированность.

2. Построение математической модели задачи. Пусть х_ij = 1 в случае работы i-м водителем по j-му маршруту и x_ij = 0 в случае отсутствия перевозок по маршруту. Тогда математическая модель задачи примет вид: целевая функция при ограничениях

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

- подготовка рабочего листа (рис. 6.1), формулы для расчета представлены в табл. 6.2;

Таблица 6.2

Формулы для расчета в задаче о назначениях

Описание	Ячейка	Формула
Ограничения	G11	=СУММ(С11:F11)
	G12	=СУММ(С12:F12)
	G13	=СУММ(С13:F1З)
	G14	=СУММ(С14:F14)
Ограничения	С15	=СУММ(С11:С14)
	D15	=CyMM(D11:D14)
	Е15	=СУММ(Е11:Е14)
	F15	=СУММ(F1:F14)
Функционал качества (стоимость всех занятий)	G17	=СУММПРОИЗВ(С5:F8;С11:F14)

 

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

 

- установка ограничения в окне Поиск решения, как показано на рис. 6.2. Решение задачи представлено на рис. 6.3.

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

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

 

Задания для практической работы

Имеется n водителей и m маршрутов движения автобусов. Стоимость с_ij работы i-м водителем по j-му маршруту приведена в таблицах вариантов. Составить план выполнения перевозок таким образом, чтобы все перевозки были выполнены, каждый водитель работал только на одном маршруте, а суммарная стоимость перевозок была минимальной. Задания представлены в соответствующих таблицах по вариантам [4].

 

Вариант 1

Водитель	Стоимость
Маршрут

Вариант 2

Водитель	Стоимость
Маршрут

Вариант 3

Водитель	Стоимость
Маршрут

Вариант 4

Водитель	Стоимость
Маршрут

Вариант 5

Водитель	Стоимость
Маршрут

Вариант 6

Водитель	Стоимость
Маршрут

Вариант 7

Водитель	Стоимость
Маршрут

Вариант 8

Водитель	Стоимость
Маршрут

Вариант 9

Водитель	Стоимость
Маршрут

Вариант 10

Водитель	Стоимость
Маршрут

Вариант 11

Водитель	Стоимость
Маршрут

Вариант 12

Водитель	Стоимость
Маршрут

6.3. Контрольные вопросы

1. Что изучает дискретное программирование?

2. Укажите этапы решения задач дискретного программирования.

3. Что такое целевая функция?

4. В чем заключается подготовка рабочего листа для решения задач?

5. Как осуществляется установка параметров в окне Поиск решения для задачи дискретного программирования?

6. Укажите основные этапы решения задачи о назначениях.

 

 

ГЛОССАРИЙ

Диапазон ячеек рабочего листа - область, включающая смежные ячейки рабочего листа, которая имеет адрес или имя.

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

Компьютерная модель - модель, которая реализуется и исследуется на компьютере, с использованием соответствующих инструментов и технологий.

Консолидация - объединение данных из одной или нескольких таблиц с выполнением необходимых расчетов.

Макрос - программа на языке программирования, оформленная как процедура SUB, выполняющая заданную последовательность операций на рабочем листе.

Массив - набор данных одного типа.

Математическая модель - модель объекта или процесса, заданная аналитическими выражениями (математическими формулами)

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

Поиск решения - инструмент, включенный в надстройки табличного процессора, который вычисляет заданное значение функции путем подбора значений ее аргументов.

Целевая функция - функция, которая оптимизируется путем подбора ее аргументов.

Linux - открытая операционная система, альтернативная ОС Microsoft Windows.

 

Список литературы

 

1. Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании: учеб. пособие. М..: Финансы и статистика, 2010.

2. Гарнаев А.Ю. Использование MS Excel и VBA в экономике и финансах. – С-Пб.: БХВ – Санкт-Петербург, 2010. – 336 с.

3. Гельман В.Я. Решение математических задач средствами Excel: практикум. СПб.: Питер, 2011.

4. Геращенко И.П. Экономико-математические методы и модели: учебное пособие /И.П. Геращенко, Е.В. Шульга. – Омск: Изд-во Омского экономического института, 2009. – 292 с.

5. Гусева О.Л., Миронова Н.Н. Excel для Windows. Практические работы //Информатика и образование. – 2009. – №2–6.

6. Елисеева И.И. Практикум по эконометрике: учеб. пособие / И.И. Елисеева, С.В. Курышева и др.; под ред. И.И. Елисеевой. М.: Финансы и статистика, 2012.

7. Ильченко А.Н. Экономико-математические методы: учеб. пособие. М.: Финансы и статистика, 2011.

8. Красе М.С., Чупрынов Б.П. Математика для экономистов. СПб.: Питер, 2008 (Серия «Учебное пособие»).

9. Кутуков В.Б. Основы финансовой и страховой математики: Методы расчета кредитных, пенсионных, инвестиционных и страховых схем. М.: Дело, 2010.

10. Матвеев Л.А. Компьютерная поддержка решений. – С-Пб.: Специальная литература, 2010. – 472 с.

11. Овчаренко Е.К., Ильина О.П., Балыбердин Е.В. Финансово-экономические расчеты в Excel. Изд. 3-е. – М.:Филинъ, 2009. – 328 с.

12. Рудикова Л. В. Microsoft Excel для студента / Л.В. Рудикова. – СПб.: БХВ - Петербург, 2009. – 368 с

 

Учебное издание