Лаб_работа_2

Лабораторная работа № 2. Решение задач целочисленного программирования

Цель работы

Ознакомиться с методами решения задач целочисленного линейного программирования в MS Excel 2007.

Методические указания Под задачей целочисленного программирования понимается

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

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

целочисленной задачей линейного программирования, если же хотя бы одна зависимость нелинейна, целочисленной задачей нелинейного

программирования.

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

оптимизация раскроя;

оптимальное проектирование машин и оборудования;

оптимизация системы сервиса и технического обслуживания

машинно-тракторного парка и т.п.

Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами дискретного (целочисленного) программирования:

f x1 , x2 ,...,xn						n			max min ,
					c j x j
						j 1
n		, bi , i
aij x j								1, m,
j 1
x j	0,	j 1, n,
	целые, j						p n .
x j						1, p,

Если p n , то задачу называют полностью целочисленной, если p n , то частично целочисленной.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используют метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета MS Excel 2007 (надстройка Поиск решения находится на вкладке Данные (рис. 1)) .

Рис. 1. Данные/ Поиск решения

Если данная надстройка не установлена, то необходимо проделать следующую последовательность действий:

нажать на кнопку Настройка панели быстрого доступа (рис. 2) и выбрать Другие команды…;

Рис. 2. Настройка панели быстрого доступа

в диалоговом окне Параметры Excel выбрать Надстройки и нажать на кнопку Перейти (рис. 3);

Рис. 3. Окно Параметры Excel

в диалоговом окне Надстройки установить галочку Поиск решения (рис. 4.); ОК; ОК.

Рис. 4. Окно Надстройки

Дискретная оптимизация средствами MS Excel проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи – линейная или нелинейная).

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

Рис. 5. Полученное сообщение надстройки Поиск решения

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

Мебельное предприятие выпускает книжные полки, тумбу под телевизоры и три вида наборов мебели. Характеристики каждого вида продукции приведены в таблице 1. При условии получения максимальной прибыли объем товарной продукции в денежном выражении должен составить не менее 459,31 тыс. руб.

Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен, поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели вида 2 – от 7 до 10 тыс. шт. Спрос на наборы мебели видов 1 и 3 неограничен, и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, количество которого и

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

Оптимизировать производственную программу предприятия.

Таблица 1

					Вид продукции
Показатель		Набор мебели				Книжные	Тумба под
	1		2		3	полки	телевизор
Оптовая цена, тыс. руб.	7,2		14,3		26,9	0,243	1,5
Прибыль от реализации, тыс.	2,4		4,5		8,9	0,06	0,45
руб.

										Таблица 2
Наименование			Количество					Вид продукции
					Набор мебели				Книжные	Тумба под
оборудования			, шт.
					1	2		3	полки	телевизор
Линия раскроя древесно-			2		0,068	0,096		0,207	0,018	0,042
стружечных плит
Гильотинные ножницы			1		0,045	0,080		0,158	0,011	0,035
Линия облицовки			2		0,132	0,184		0,428	0,020	0,060
Линия обрезки кромок			2		0,057	0,082		0,230	0,010	0,028
Лаконаливная машина			2		0,063	0,090		0,217	0,010	0,032
Полировальные станки			4		0,170	0,280		0,620	0,020	0,096
Решение.
Экономико-математическая модель задачи.
Переменные: x1, x2, x3, x4, x5 – объем продукции каждого вида.
Каждая машина работает в две смены, эффективное время работы –
3945 ч. Определим фонд времени работы оборудования каждого типа (ч):
2	3945 = 7890			(линия раскроя),
1	3945 = 3945			(гильотинные ножницы),
2	3945 = 7890			(линия облицовки),
2	3945 = 7890			(линия обрезки кромок),
2	3945 = 7890			(лаконаливная машина),
4	3945 = 15780			(полировальные станки).

Целевая функция:

f X 2,4x1 4,5x2 8,9x3 0,06x4 0,45x5 max .

Ограничения:

по объему товарной продукции (тыс. руб.)

7,2x1 14,3x2 26,9x3 0,243x4 1,5x5 459,31;

по фонду времени оборудования (ч)

0,068x1 0,096x2 0,207x3 0,018x4 0,042x5 7890, 0,045x1 0,080x2 0,158x3 0,011x4 0,035x5 3945, 0,132x1 0,184x2 0,428x3 0,020x4 0,060x5 7890, 0,057x1 0,082x2 0,230x3 0,010x4 0,028x5 7890, 0,063x1 0,090x2 0,217x3 0,010x4 0,032x5 7890, 0,170x1 0,280x2 0,620x3 0,020x4 0,096x5 15780;

по сбыту продукции (шт.)

x1 10000,

7000 x2 10000,

x3 10000, x4 10000,

4000 x5 7000,

x1, x2 , x3 , x4 , x5 0,

x1, x2 , x3 , x4 , x5 целые числа.

Экранные формы, задание переменных, целевой функции, ограничений и граничных условий целочисленной задачи представлены на рисунке 6.

Рис. 6. Экранные формы в режиме просмотра формул

При решении задач целочисленного программирования в MS Excel необходимо вводить условие целочисленности. Добавляя ограничения, следует выбрать опцию целое в раскрывшемся списке Ограничение (рис. 7)

Рис. 7. Введение ограничения целочисленности переменных

На рисунке 8 приведено заполненное диалоговое окно Поиск решения. Решение показано на рисунке 9.

Рис. 8. Введены все условия задачи

Рис. 9. Решение найдено Ответ. Для получении максимальной прибыли (164166 руб.)

необходимо произвести: 10002 набора мебели вида 1; 10000 наборов вида 2; 10490 наборов вида 3; 4000 тумб под телевизор. Книжные полки в этом месяце производить не нужно.

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

Некоторое предприятие выпускает две марки элитных часов (n=2), которые имеют условные названия: «Банкир» и «Президент». Для

изготовления часов «Банкир» требуется 50 гр. золота и 30 гр. платины, а для изготовления часов «Президент» требуется 40 гр. золота и 50 гр. платины (m=2). Предприятие продает часы «Банкир» по цене $1500 за 1 шт., а часы «Президент» – по цене $2100 за 1 шт. Запасы драгоценных металлов на складе предприятия ограничены следующими значениями: золота – 1,5 кг и платины – 1,8 кг. Требуется определить оптимальную партию часов «Банкир» и «Президент», которую может изготовить предприятие с целью получения максимальной прибыли.

Решение.

Экономико-математическая модель задачи.

Переменные: x1, x2 – количество часов соответственно марки «Банкир» и «Президент».

Целевая функция:

f X 1500x1 2100x2 max .

Ограничения:

50x1 40x2 1500,

30x1 50x2 1800,

Для решения данной задачи предварительно необходимо построить на плоскости множество допустимых альтернатив, для чего воспользуемся программой MS Excel 2007.

На одной диаграмме следует построить 3 графика линейных функций:

f1 1500 / 40 50 / 40x1 150 / 4 5 / 4x1, f2 1800 / 50 30 / 50x1 36 3 / 5x1,

где в качестве зависимой переменной y с соответствующим индексом используется вторая переменная данной задачи. В качестве третьей функции следует использовать целевую линейную функцию (рис. 10)

f3 76650 / 2100 1500 / 2100x1 36,5 5 / 7x1,

которая соответствует некоторому значению целевой функции.

Рис. 10. Экранные формы в режиме просмотра формул Для построения графиков необходимо воспользоваться мастером

диаграмм (Вставка/ Точечная).

Рис. 11. Вставка/ Точечная

После редактирования свойств диаграмма примет вид, показанный на рисунке 12.

Рис. 12. Результат построения графиков функций ограничений и целевой функции для задачи о часах

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

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

Для более наглядного представления линии целевой функции изменим содержащуюся в ячейке В15 формулу на формулу: f3 36 5 / 7x1 , которую

скопируем в ячейки С15:Н15. Новая формула означает параллельный сдвиг прямой линии, соответствующей целевой функции задачи о часах. В результате этого изменится построенная диаграмма, которая будет иметь следующий вид (рис. 13).

Рис. 13. Графическое решение задачи о часах

Из данной диаграммы видно, что оптимальное решение задачи достигается в точке А, координаты которой равны: x1 0, x2 36 . При этом оптимальное значение целевой функции равно: fopt $75600 .

Таким образом, оптимальная партия изготовления часов, обеспечивающая максимум общей стоимости готовой продукции, должна состоять только из 36 шт. часов марки «Президент». От изготовления часов марки «Банкир» предприятию следует отказаться. При этом будет обеспечено максимальное значение стоимости продукции $75600 .

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

(рис. 14).

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

Результаты решения исходной задачи показаны на рисунке 15.

Рис. 15. Результаты количественного решение задачи о часах с помощью надстройки Поиск решения

Анализ полученных результатов решения задачи двумя различными методами показывает их полное совпадение. Дополнительно можно заметить, что запасы платины используются полностью, а 60 гр. золота останутся неиспользованными.

Варианты заданий для самостоятельной работы

В соответствии с вариантом задания решить задачу целочисленного линейного программирования. Для задач с двумя переменными проиллюстрировать полученные отсечения графически.

Задание 1. Издательский дом «Садовод» издает два журнала; «Пчеловод» и «Сад и огород», которые печатаются в трех типографиях: «Типография МК», «Полиграф» и «Труд», где общее количество часов, отведенное для печати одной тысячи экземпляров ограничены и представлены в следующей таблице.

				Ресурс
		Время печати 1000 зкз.		времени,
Типография				отведенный
				типографией,
		«Пчеловод»	«Сад и огород»	час
Типография МК		6	8	80
Полиграф		4	6	120
Труд		4	5	70
Оптовая цена,		22	25
руб./шт.

Спрос на журнал «Пчеловод» составляет 12 тыс. экз., а на журнал «Сад и огород» - не более 14 тыс. экз. в месяц.