4.1 Цель работы: изучение методики решения математической модели в виде задачи линейного целочисленного программирования с булевыми переменными.
4.2 Теоретическая часть
Важный раздел целочисленной оптимизации составляют математические модели задач с булевыми переменными, т.е. переменными, принимающими только два значения "1", или "0". С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов. Примерами задач данного класса в процессе управления производством служат задачи
· оптимального назначения исполнителей на работы,
· при выборе вариантов комплектующих изделий,
· при выборе типа станка для обработки деталей,
· в задаче закрепления продавцов за товарами различных видов, и т.д.
Для того, чтобы составить матрицу условий задачи необходимо иметь исходные данные: характеристики деятельности любого исполнителя на каждой работе, определяющие значение принятого критерия оптимальности. Так, в задаче закрепления продавцов за товарами должны быть известны доходы каждого продавца от продажи товара любого вида, т.е. должна быть известна матрица
.
Продавцам 
соответствуют строки, а видам товаров 
– столбцы этой матрицы. В задаче требуется определить, за каким продавцом должен быть закреплен тот или иной товар, т.е. ответить на вопрос «будет ли 
-ый продавец продавать 
-ый товар или не будет». Таким образом, искомые неизвестные должны принимать только два значения «да», или «нет». В числовом выражении «1», или «0».
Для составления математической модели введем булевы переменные 
следующим образом: 
, если 
-ый продавец осуществляет продажу -го товара, и 
, если -ый продавец не занят продажей -го товара. В сокращенном виде
, 
.
Запишем булевы неизвестные в виде следующей матрицы
.
Через 
обозначим суммарный доход от продажи всего товара. Тогда
. (4.1)
Так как по условию каждый продавец продает только один вид товара, то
. (4.2)
Так как каждый вид товара реализуется одним продавцом, то
. (4.3)
Таким образом, математическая модель задачи о назначениях состоит в определении неотрицательных целых чисел , удовлетворяющих ограничениям (4.2)-(4.3), для которых целевая функция (4.1) максимальна. Система ограничений задачи показывает, что каждое допустимое решение можно представить матрицей, содержащей по одной единице в каждой строке и каждом столбце, а остальные элементы матрицы равны нулям. Ясно также, что число допустимых решений в задаче равно 
, и поэтому допустимое множество дискретно.
Математическая модель в виде (4.1)-(4.3) представляет собой классический вариант задачи о назначениях. Она относится к линейному целочисленному программированию с булевыми переменными. В принципе комбинаторные задачи приведенного вида могут быть решены полным перебором всехвозможных вариантов допустимых решений. Однако, количество этих вариантов может быть столь большим, что полный перебор невозможно осуществить в реальноне время даже с помощью современных ЭВМ. Так, при 
получим число допустимых решений 
. Если предположить, что компьютер в течение 1с находит 
допустимых решений и для каждого из них вычисляет значение целевой функции, то для решения задачи потребуется 
с, или 
года (
). Таким образом, для решения данной задачи при больших значениях 
перебор допустимых решений неприменим.
Заметим, что математическая модель задачи о назначениях представляет собой частный случай сбалансированной транспортной модели при дополнительном условии целочисленности неизвестных. Поэтому для ее решения может быть применен классический метод решения – метод потенциалов. Для решения задачи можно использовать также венгерский метод и метод ветвей и границ. Однако, при наличии программного обеспечения быстрее и проще использовать информационные технологии.
4.3 Пример выполнения работы
Пусть для определенности n=4, а доходы продавцов от продажи товаров (д.е.) заданы в виде матрицы
.
Продавцам соответствуют строки, а видам товаров – столбцы этой таблицы. Введем булевы переменные:
, 
.
Эти неизвестные представим в виде следующей матрицы
.
Пусть величина 
характеризует суммарный доход от продажи всего товара. Тогда математическая модель задачи имеет вид
(4.4)
при ограничениях на продажу товаров каждым продавцом
, (4.5)
на реализацию каждого вида товара
, (4.6)
а также на условия двоичности неизвестных
. (4.7)
Количество допустимых решений задачи равно 
.
В среде Excel в блоке ячеек B2: E5 поместим доходы продавцов от продажи товаров (см. таблицу 4.1). Блок ячеек B8: E11 предусмотрим для записи оптимального плана закрепления продавцов за товарами. Сначала все ячейки этого блока пустые или равны нулям. В блоки ячеек G8: G11 и B13: E13 поставим число 1 – правые части системы ограничений (4.5)-(4.6). Суммарный доход от продажи товара (4.4) рассчитывается в ячейке F2 в соответствии с формулой
= СУММПРОИЗВ(B2: E5; B8: E11).
В блок ячеек F8: F11 поместим левые части системы (4.5). Для этого в ячейку F8 поместим формулу
= СУММ(B8: E8),
которую протянем на ячейки F9, F10 и F11. В блок ячеек B12: E12 поместим левые части системы (4.6). Для этого в ячейку B12 поместим формулу
= СУММ(B8: B11),
которую протянем на ячейки C12, D12, E12.
Таблица 4.1 – Данные о доходах продавцов от продажи товаров
| A | B | C | D | E | F | G | |
| Доходы продавцов от продажи товаров | |||||||
| Оптимальный план закрепления продавцов за товарами | |||||||
| Т1 | Т2 | Т3 | Т4 | ||||
| П1 | |||||||
| П2 | |||||||
| П3 | |||||||
| П4 | |||||||
Оптимальный план закрепления продавцов за товарами определим с помощью процедуры «Поиск решения», как показано на рисунке 4.1.
Рисунок 4.1 - Обращение к процедуре «Поиск решения» в задаче закрепления продавцов за товарами
Результаты оптимизации представлены в табл.20. В ячейке F2 находятся максимальный суммарный доход, равный 
д.е. В блоке ячеек B8: E11 содержится оптимальное распределение продавцов по товарам, которое дается матрицей
.
По оптимальному плану первый продавец должен продавать второй товар, второй продавец – первый товар, третий продавец – третий товар, четвертый продавец – четвертый товар. Доходы каждого продавца, полученные от продажи своего товара, приведены в таблице 4.2.
Таблица 4.2 - Доходы каждого продавца, полученные от
продажи своего товара
| Продавец | П1 | П2 | П3 | П4 |
| Доход |
На рисунке 4.2 дано схематическое изображение результатов оптимизации
Рисунок 4.2 - Схема закрепления продавцов за товарами
4.4 Техническое обеспечение
4.4.1 Компьютеры и выход в сеть интернета.
4.5 Содержание отчета
4.5.1 Отчет должен содержать следующие пункты:
· задание на работу (приложение 4),
· математическую модель в виде задачи линейного целочисленного программирования с булевыми переменными,
· количество допустимых решений задачи,
· оптимальный план закреплений продавцов за товаром,
· доход каждого продавца от продажи товара,
· диаграмма оптимального плана закреплений продавцов за товаром, выводы по работе.