ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Постановка задачи

Высшее учебное заведение занимается подготовкой специалистов по 2-м специальностям. В соответствии с имеющимся портфелем заказов необходимо каждый год выпускать не менее 200 специалистов по специальности «Проектирование и производство ЭВМ» (кратко - ЭВМ) и 300 специалистов по специальности «Проектирование и разработка программного обеспечения» (кратко ПО).

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

За подготовку одного специалиста на дневной форме обучения вуз получает 12 млн. рублей, на заочной - 5 млн. рублей. Затраты на подготовку специалиста при дневной форме обучения составляют 8,8 млн. рублей на специальности ЭВМ и 8,5 млн. рублей на специальности ПО. При заочной форме обучения эти затраты составляют 4,5 млн. рублей на специальности ЭВМ и 4,0 на специальности ПО.

Объем финансирования составляет 5500 млн. рублей в год.

Составить план подготовки специалистов, при котором доходы вуза будут максимальными.

 3.2. Построение математической модели

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

x₁ - количество студентов специальности ЭВМ дневной формы обучения;

x₂ - количество студентов специальности ЭВМ заочной формы обучения;

x₃ - количество студентов специальности ПО дневной формы обучения;

x₄ - количество студентов специальности ПО заочной формы обучения.

Тогда x₁+ x₂  – общее количество студентов специальности ЭВМ,
x₃+ x₄ – общее количество студентов специальности ПО (еще раз напомним, что речь идет о студентах одного курса). В соответствии с имеющимися заказами студентов специальности ЭВМ должно быть не менее 200, специальности ПО – не менее 300. Поэтому получаем ограничения

                                             (3.1)

Учтем ограничение, установленное министерством образования на количество студентов заочной формы обучения. x₂+ x₄ – общее количество студентов заочной формы обучения. Поэтому

                                            (3.2)

Стоимость подготовки специалистов составит  млн. рублей. Поскольку объем финансирования ограничен и равен 5500 млн. рублей, то получаем ограничение

                        (3.3)

Очевидно, что все переменные в задаче неотрицательны:

x_j ≥ 0, j = 1,...,4

Суммы, выплачиваемые вузу за подготовку специалистов, а также затраты вуза на их подготовку, известны. Поэтому можно подсчитать доход вуза от подготовки одного специалиста. Он составляет:

§ 12 - 8,8 = 3,2 млн. рублей за подготовку на специальности ЭВМ при дневной форме подготовки;

§ 5 – 4,5 = 0,5 млн. рублей за подготовку на специальности ЭВМ при заочной форме подготовки;

§ 12 - 8,5 = 3,5 млн. рублей за подготовку на специальности ПО при дневной форме подготовки;

§ 5 – 4,0 = 1,0 млн. рублей за подготовку на специальности ПО при заочной форме подготовки;

Поэтому суммарный доход вуза от подготовки всех специалистов будет равен 3,2x₁ + 0,5x₂ + 3,5x₃ + x₄  млн. рублей. Так как доход необходимо максимизировать, то целевую функцию в нашей задаче можно записать так:

L =3,2x₁ + 0,5x₂ + 3,5x₃ + x₄ → min.

Таким образом, математическая модель задачи имеет вид:

                    (3.4)

Решение задачи

Для решения задачи необходимо привести ее математическую модель к канонической форме. Для этого в ограничения ( 3.1) добавим свободные переменные со знаком “-“, а в ограничения (3.2) - свободные переменные со знаком “-“. В результате получим:

Как видно, 3-е и 4-ое ограничения задачи находятся в предпочтительном виде, т. к.  в них содержатся переменные, входящие только в одно уравнение и имеющие коэффициент 1 (это переменные x₇ и x₈). В 1-м и 2-м уравнениях таких переменных нет, т. е. система ограничений не находится в предпочтительном виде. Значит, для решения задачи требуется применить 2-хфазный симплекс-метод.

Построим вспомогательную задачу линейного программирования. Для этого в  1-е и 2-е уравнения введем фиктивные переменные x₉ и x₁₀. Система ограничений после этого будет выглядеть следующим образом:

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

W =x₉ + x₁₀ → min.

Начальный базис вспомогательной задачи составляют переменные:

1) в ограничениях, которые находятся в предпочтительном виде, - те переменные, которые обеспечили предпочтительность этих ограничений (в нашем случае это переменные x₇, x₈);

2) в ограничениях, которые не находятся в предпочтительном виде, - фиктивные переменные (в нашей задаче – переменные x₉, x₁₀).

Разрешим систему ограничений относительно базисных переменных:

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

W  = x₉ + x₁₀ = 200-x ₁-x₂+x₅+300-x₃-x₄+x₆ = 500-x₁-x₂-x₃-x₄+x₅+ x₆ .

Таким образом, вспомогательная задача в симплексной форме будет иметь следующий вид:

W  = 500-x₁-x₂-x₃-x₄+x₅+ x₆ → min,

                   (3.5)

Перенесем коэффициенты симплексной формы (3.5) в симплексную таблицу и приступим к решению задачи:

                   Таблица 3.1

Этой симплексной таблице соответствует начальный базисный план вспомогательной задачи:

Этот план не оптимален, так как целевая функция вспомогательной задачи на минимум, а среди коэффициентов целевой функции (строка W вспомогательной задачи) есть отрицательные. Из отрицательных коэффициентов целевой функции необходимо выбрать максимальный по модулю. Поскольку все отрицательные коэффициенты одинаковы, то можем выбрать любой из них, например, в столбце x₁. Столбец x₁ объявляем ведущим.

Рассчитаем максимально допустимый шаг Θ⁰ вдоль ведущей переменной x₁. Для этого в симплексную таблицу добавим столбец, в который будем заносить результаты расчета шага для каждой базисной переменной. Словами правило расчета можно сформулировать следующим образом: если коэффициент в ведущем столбце больше либо равен нулю, то соответствующий шаг равен бесконечности; иначе он равен отношению соответствующего значения в столбце β к значению в ведущем столбце, взятому с противоположным знаком. Максимально допустимый шаг Θ⁰ вдоль ведущей переменной равен наименьшему из найденных шагов.

Формально это правило можно записать с помощью следующих соотношений

Здесь Θ_i  - шаг, рассчитанный по i-ой строке таблицы; β_i , r_i – элементы i-ой строки таблицы, находящиеся соответственно в столбце β и ведущем столбце таблицы.

Если Θ⁰=∞, то целевая функция неограниченно возрастает (или убывает) на множестве планов задачи. Ее решение в этом случае окончено.

Допустим, что Θ⁰<∞. Строка, содержащая максимально допустимый шаг Θ⁰ (т.е. содержащая наименьшее из найденных чисел), называется разрешающей.

Результаты вычисления максимально допустимого шага для рассматриваемого примера приведены в табл. 3.2.

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

Таким образом, переменная x₉ покидает базис, вместо нее в базис вводится ведущая переменная x₁. Эта операция сопровождается пересчетом симплексной таблицы, который осуществляется по следующим четырем правилам:

Таблица 3.2

xн xб	β	x1	x2	x3	x4	x5	x6	Θ
W	300	-1	-1	-1	-1	1	1
X9	200	-1	-1	0	0	1	0	200
x10	300	0	0	-1	-1	0	1	∞
X7	150	0	-1	0	-1	0	0	∞
X8	5500	-12	-5	-12	-5	0	0

1)  «новый» разрешающий элемент есть число, обратное к «старому» разрешающему элементу, т.е.

Здесь - «новый» разрешающий элемент, r - «старый» разрешающий элемент.

2) «новые» элементы разрешающей строки получаются из «старых» элементов делением на «старый» разрешающий элемент, взятый с противоположным знаком, т.е.

.

Здесь - «новый» элемент разрешающей строки, s - «старый» элемент разрешающей строки.

3) «новые» элементы ведущего столбца получаются из «старых» элементов делением на «старый» разрешающий элемент, т.е.

Здесь - «новый» элемент ведущего столбца, t - «старый» элемент ведущего столбца.

4) Рассмотрим произвольный элемент таблицы, не находящийся ни в ведущем столбце, ни в разрешающей строке. Обозначим его, например, q. Найдем его проекции на ведущий столбец и разрешающую строку. Обозначим их соответственно t и s (см. рисунок ниже).

Пусть - «новый» элемент таблицы. Тогда он находится по формуле

Эту формулу называют правилом прямоугольника. Словами его можно сформулировать так: «новый» элемент симплексной таблицы есть разность между его старым значением и произведением проекций, разделенным на разрешающий элемент.

Применим сформулированные выше правила к рассматриваемому примеру. В результате получим таблицу

Таблица 3.3

xн xб	β	x9	x2	x3	x4	x5	x6
W	300	1	0	-1	-1	0	1
x1	200	-1	-1	0	0	1	0
x10	300	0	0	-1	-1	0	1
x7	150	0	-1	0	-1	0	0
x8	3100	12	7	-12	-5	-12	0

Поскольку фиктивная переменная x₉ покинула базис, ее значение стало равным нулю. Это означает, что она выполнила свою функцию и ее можно исключить из дальнейшего рассмотрения, а соответствующий столбец – из таблицы:

Таблица 3.4

Таким образом, получено новое базисное решение вспомогательной задачи:

Это решение не является оптимальным решением вспомогательной задачи, т.к. по-прежнему в строке W содержатся отрицательные коэффициенты.

Выполняем очередную итерацию. Столбец x₃ объявляем ведущим, по результатам расчета максимально допустимого шага получаем, что разрешающей будет строка x₈:

Таблица 3.5

xн xб	β	x2	x3	x4	x5	x6	Θ
W	300	0	-1	-1	0	1
x1	200	-1	0	0	1	0	∞
x10	300	0	-1	-1	0	1	300
x7	150	-1	0	-1	0	0	∞
x8	3100	7	-12	-5	-12	0

Переменная x₈ покидает базис, вместо нее в базис вводится переменная x₃. Однако количество столбцов в новой таблице не уменьшится: переменная x₈ – свободная, а не фиктивная. В отличие от фиктивной свободная переменная такая же равноправная переменная, как и x₁ – x₄, и поэтому не покидает таблицу после вывода из базиса. После пересчета симплексной таблицы получим:

Таблица 3.6

xн xб	β	x2	x8	x4	x5	x6
W					1	1
x1	200	-1	0	0	1	0
x10					1	1
x7	150	-1	0	-1	0	0
x3					-1	0

Симплексной табл. 3.6 соответствует базисный план вспомогательной задачи

Этот план по-прежнему не оптимален. Столбец x₂ выберем в качестве ведущего и рассчитаем максимально допустимый шаг:

Таблица 3.7

xн xб	β	x2	x8	x4	x5	x6	Θ
W					1	1
x1	200	-1	0	0	1	0	200
x10					1	1
x7	150	-1	0	-1	0	0	150
x3					-1	0

На основании результатов расчета максимально допустимого шага определяем разрешающую строку x₁₀.

После замены в базисе переменной x₁₀ на переменную x₂, пересчета симплексной таблицы и исключения переменной x₁₀ из дальнейшего рассмотрения, получим таблицу:

Таблица 3.8

xн xб	β	x8	x4	x5	x6
W	0	0	0	0	0
x1			1
x2			-1
x7			0
x3	300	0	-1	0	1

Как видно, все искусственные переменные покинули базис и исключены из таблицы. Строка вспомогательной целевой функции W содержит одни нули. Это означает, что решение вспомогательной задачи окончено, первая фаза двухфазного метода завершена, получен базисный план исходной задачи:

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

Искусственная целевая функция с исчезновением фиктивных переменных трансформировалась в нулевую. Поэтому для перехода ко второй фазе симплекс-метода необходимо вернуться к исходной целевой функции. Поскольку исходная целевая функция содержит базисные переменные, их необходимо исключить, выразив через небазисные переменные. С этой целью из последней симплексной таблицы выпишем соотношения, связывающие базисные переменные с небазисными:

Подставляя в исходную целевую функцию вместо переменных x₁, x₂, x₄ соответствующие выражения, получим:

В результате симплексная таблица примет вид:

Таблица 3.9

xн xб	β	x8	x4	x5	x6
W
X1			1
X2			-1
X7			0
X3	300	0	-1	0	1

Из таблицы следует, что план x⁽²⁾ не оптимален, так как среди коэффициентов целевой функции есть отрицательные. Выберем переменную x₄ в качестве ведущей и рассчитаем максимально допустимый шаг:

Таблица 3.10

xн xб	β	x8	x4	x5	x6	Θ
W
x1			1			∞
x2			-1
x7			0			∞
x3	300	0	-1	0	1	300

Переменная x₂ покидает базис, ее заменяет переменная x₄. После пересчета таблицы получим:

Таблица 3.11

xн xб	β	x8	x2	x5	x6
W
X1	200	0	-1	1	0
X4			-1
X7			0
X3			1

Поскольку строка L таблицы не содержит отрицательных элементов, то базисный план

является оптимальным. Решение задачи окончено.

Получено оптимальное решение. Значения основных переменных задачи x₁=200, x₃= , x₄=  обозначают, что для получения максимального дохода вузу ежегодно необходимо выпускать:

§ 200 студентов специальности ЭВМ дневной формы обучения;

§  студентов специальности ПО дневной формы обучения;

§  студентов специальности ПО заочной формы обучения.

При этом доход вуза составит  млн. рублей.

Естественно, требуется найти целочисленной решение, но об этом в разделе 5.