Задачи с булевыми переменными

Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные x_j могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми.

Помимо задания требования целочисленности (см. подразд. 1.3) при вводе условия задач с булевыми переменными необходимо:

• для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных;

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

Рисунок 1.19. Добавление условия единичной верхней границы значений

переменных некоторой задачи с булевыми переменными

Работа № 2

ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП (ТРАНСПОРТНАЯ ЗАДАЧА).

Цель: научиться методам решения двухиндексных задач линейного программирования на ЭВМ, рассмотреть основные типы задач – транспортная задача, задача о назначении.

Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам, рассмотренным работе 1.

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

ПРИМЕР 2.1.Из трех складов, имеющих некоторый продукт в количествах 50т, 60т, 70т, необходимо его доставить в три магазина в количествах 40т, 85т, 55т. Стоимости перевозки 1т продукта из склада i в магазин j заданы в виде матрицы С={c_ij} размерностью 3x3. Спланировать перевозки так, чтобы их общая стоимость была минимальной.

2 1 5

С = 3 4 3

4 6 6

Ввод исходной информации

Готовим таблицу в Еxcel как показано на рис.2.1.

	А	В	С	D	E	F	G
	переменные	огранич.
	целые	xi1	xi2	xi3	лев.часть	знак	пр.часть
	х1j
	x2j
	x3j
	лев.часть
	знак
	пр.часть						баланс
	тарифы	xi1	xi2	xi3
	х1j
	x2j				ЦФ	напр
	x3j					мин

Рисунок 2.1. Исходные данные транспортной задачи

Ячейки В3:D5 (выделены синим цветом) предназначены для переменных, в ячейках G3:G5 содержатся ограничения по мощностям (наличие товара на складе), ячейки В8:D8 содержат ограничения по спросу, в ячейках В11:D13 находятся коэффициенты матрицы С={c_ij}.

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

Формулы для экранной формы транспортной задачи

Таблица 2

Объект математической модели	Выражение в Excel
Переменные задачи	В3:D5
Формула в целевой ячейке E13	=СУММПРОИЗВ(B3:D5;B11:D13)
Ограничения по строкам в ячейках E3, E4, E5	=СУММ(B3:D3) =СУММ(B4:D4) =СУММ(B5:D5)
Ограничения по столбцам в ячейках B6, C6, D6	=СУММ(B3:B5) =СУММ(C3:C5) =СУММ(D3:D5)
Суммарные запасы и потребности в ячейках G7, F8	=СУММ(G3:G5) =СУММ(B8:D8)

Дальнейшие действия (аналогично проведенным в работе 1) производятся в окне "Поиск решения", которое вызывается из меню "Сервис". Окно "Поиск решения" после ввода всех необходимых данных транспортной задачи представлено на рис.2.2.

Рисунок 2.2. Окно "Поиск решения" транспортной задачи

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

Рисунок 2.3. Экранная форма двухиндексной задачи (курсор в целевой ячейке Е13)

В рассмотренном примере суммарное наличие товара на всех складах совпадает с общей потребностью, поэтому в "Поиске решения" (рис.2.2) мы использовали знак равенства B6:D6=B8:D8 (удовлетворить потребности) и E3:E5=G3:G5 (вывести весь товар) – такая транспортная задача называется закрытой. В случае избытка товара второе условие необходимо записывать со знаком ≤ , тогда в результате решения у каких-то поставщиков останутся излишки товара. В случае дефицита товара первое условие необходимо записывать со знаком ≤ , тогда в результате решения какие-то потребители окажутся частично неудовлетворенны (открытые задачи).

ПРИМЕР 2.2.Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 500 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:

Карьер	Строительный объект
		а
	31-а

Задание 2.1. Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.

Значение неизвестного параметра а взять равным номеру варианта.

Рассмотрим еще один вид задач, сводящихся к ЗЛП – задачу о назначениях.

ПРИМЕР 2.3.Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Рабочие	Станки
С1	С2	С3	С4
Р1	2,3	1,9+а/20	2,2	2,7
Р2	1,8+а/20	2,2	2,0	1,8+а/20
Р3	2,5	2,0	2,2	3,0
Р4	2,0	2,4	2,4–а/20	2,8

Задание 2.2. Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?

Значение неизвестного параметра а взять равным номеру варианта.

Обозначим за x_ij, i=1,2,3,4; j=1,2,3,4 - переменные, которые принимают значения 1, если i-й рабочий работает на j-м станке. Если данное условие не выполняется, то x_ij = 0. Целевая функция есть:

2,3x₁₁+(1,9+а/20)x₁₂+2,2x₁₃+2,7x₁₄+(1,8+а/20)x₂₁+2,2x₂₂+2x₂₃+(1,8+а/20)x₂₄+

+2,5x₃₁+2x₃₂+ 2,2x₃₃+ 3x₃₄+ 2x₄₁+ 2,4x₄₂+ (2,4–а/20)x₄₃+ 2,8x₄₄→ min.

Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть

x₁₁+ x₁₂+ x₁₃+x₁₄=1;

x₂₁+ x₂₂+ x₂₃+x₂₄=1;

x₃₁+ x₃₂+ x₃₃+x₃₄=1;

x₄₁+ x₄₂+ x₄₃+x₄₄=1.

Кроме этого, каждый станок обслуживает только один рабочий:

x₁₁+ x₂₁+ x₃₁+x₄₁=1;

x₁₂+ x₂₂+ x₃₂+x₄₂=1;

x₁₃+ x₂₃+ x₃₃+x₄₃=1;

x₁₄+ x₂₄+ x₃₄+x₄₄=1.

Кроме того, все переменные должны быть целыми и неотрицательными: x_ij ≥0, x_ij – целые. (используйте 1.5).

Работа № 3