12. Компью-Нет

Зам директора по персоналу фирмы «Компью-Нет» должен составить 6 пар-команд из техника-программиста и специалиста по маркетингу для работы по установке компьютерных сетей по индивидуальным требованиям клиентов. Пары составляются из вновь набранных сотрудников, среди которых проведен специальный психологический тест на взаимную совместимость. Индекс совместимости варьирует от 20 (выраженная враждебность) до 1 (возможность дружеских отношений), и для каждой потенциальной пары приведен в таблице.

	Аня	Маша	Катя	Лиза	Ольга	Софья
Иван	3	4	9	18	9	6
Михаил	16	8	12	13	20	4
Павел	8	6	13	1	6	9
Николай	16	9	6	8	1	11
Алексей	8	12	17	5	3	5
Петр	2	9	1	10	5	17

Определите такое распределение по парам, которое обращает в минимум

суммарный индекс совместимости.

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

Задачу (1)-(4) можно преобразовать так, чтобы в ней всегда определять минимум целевой функции, а ограничения (2)-(3) записывать единообразно в виде равенств:

;

(9)

где ,

, , … , . (10)

В этом случае говорят, что ЗЛП записана в каноническом виде.

Для перехода к канонической форме записи ЗЛП производят следующие элементарные преобразования:

1) переходят от поиска максимума функции цели к поиску ее минимума. Для этого достаточно рассмотреть функцию

;

2) ограничения-неравенства (2-3) исходной задачи преобразуют в условия-равенства (9). Для этого, если условие-ограничение имеет вид

,

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

.

Если условие-ограничение имеет вид

,

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

.

Если в системе необходимо преобразовать несколько неравенств, то для каждого из них нужно ввести свою дополнительную переменную. Например, если граничные условия ЗЛП имеют вид

(15)

то для каждого из неравенств (15) вводим новую переменную и преобразуем систему неравенств (15) в систему равенств

где .

Целевая функция представляется в виде

Вводимые дополнительные переменные имеют вполне опре­деленный экономический смысл. Например, если в ограничениях ЗЛП отражается наличие и расход производственных ресурсов, то числовое значение дополнительной переменной означает объем не­использованного ресурса.

Канонический вид ЗЛП также предполагает, что все пере­менные, входящие в условия задачи, неотрицательны: . Если для какого-то из переменных это условие отсутствует, то переменную представляем в виде разности двух новых перемен­ных , где новые дополнительные переменные неотрица­тельны . Таким образом, условия неотрица­тельности распространяются на все переменные, участвующие в за­даче, хотя число переменных возрастает.

Задача. Привести ЗЛП к каноническому виду и записать ее в различных формах

,

.

Решение. Чтобы перейти от ограничений неравенств к огра­ничениям равенствам, введем две дополнительные неотрицательные переменные , одну в каждое неравенство, как бы «уравновешивая» их. В третьем неравенстве-ограничении в правой части находится отрицательное число. Умножим обе части этого неравенства на (–1). Приходим к эквивалентной системе ограниче­ний

.

Преобразуем целевую функцию так, чтобы перейти от поис­ка ее максимума к нахождению минимума. Воспользуемся правилом: . В результате приходим к ЗЛП вида

,

.