2.2. Решение задачи линейной оптимизации средствами Excel и Mathcad

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

F = C_jX_j  max (min, сonst),

а_ij X_j  b_i,

d_j  X_j  D_j,

i = 1, m; j = 1, n.

Задача линейного программирования является достаточно распространенной задачей принятия оптимальных решений. Аналитический метод решения за­дач линейного программирования заключается в сле­дующем:

– найти вершины области допустимых решений (ОДР) как точки пересечения ограничений;

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

Вершина, в которой целевая функция приобретает опти­маль-ное (максимальное или минимальное) значение, счита­ется оптимальной вершиной. Координаты этой вершины и являются искомыми опти­мальными значениями переменных.

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

Рассмотрим следующий пример. Требуется определить, в каком количестве надо выпускать про­дукцию четырех типов (Прод₁, Прод₂, Прод₃, Прод₄), для изготовления которой требуются ресурсы трех видов: трудовые, сы­рье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нор­мой расхода. Нормы расхода, прибыль, получаемая от реализации единицы каждого типа продукции, а также наличие располагаемого ресурса приведены в табл. 2.1.

Таблица 2.1

Условия задачи линейного программирования

№ пп	A	B	C	D	E	F	G
1	Ресурс	Прод1	Прод2	Прод3	Прод4	Знак	Наличие
2	Прибыль	60	70	120	130	Мax	–
3	Трудовые	1	1	1	1		16
4	Сырье	6	5	4	3		110
5	Финансы	4	6	10	13		100

Составим математическую модель, для чего введем следующие обозначения:

Х_j – количество выпускаемой продукции j-го типа, j =14 ;

b_i – количество располагаемого ресурса i-гo вида, i = 13 ;

a_ij – норма расхода i-гo ресурса для выпуска единицы продукции j-гo типа;

с_j – прибыль, получаемая от реализации единицы продукции j-гo типа.

Затем приступим к составлению модели. Как видно из табл. 2.1, для выпуска единицы Прод₁ требуются шесть единиц сырья, значит, для выпуска всей продукции Прод₁ необходимо 6x_i единиц сырья, где x_i – количество выпускаемой продукции Прод₁. С учетом того что для других видов про­дукции зависимости аналогичны, ограничение по сырью будет иметь вид

6х₁ + 5х₂ + 4х₃ + 3х₄  110.

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

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

F = 60x₁ + 70x₂ + 120x₃ + 130x₄  max;

x₁ + x₂ + x₃ + x₄  16;

6x₁ + 5x₂ + 4x₃ + 3x₄  110;

4x₁ + 6x₂ + 10x₃ + 13x₄  100;

x_j  0; j = 14.

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

Алгоритм симплекс-метода сводится к следующему:

1) записать задачу в канонической форме;

2) разделить переменные на базисные и свободные;

3) выразить базисные переменные через свободные переменные;

4) проверить неотрицательность базисных переменных;

5) выразить функцию цели f через свободные переменные;

6) вычислить полученное базисное решение и функцию цели f на нем, приравняв к нулю свободные переменные.

Если все коэффициенты свободных переменных имеют один знак, то задача решена.

Если нет, то определить включаемую в число базисных новую переменную.

Вернуться к п. 3 и повторять все этапы, пока не будет получен необходимый результат.

Реализация симплекс-метода в Excel осуществлена с использованием надстройки «Поиск решения».

Для решения задачи необходимо:

– создать форму для ввода условий задачи;

– указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки);

– ввести исходные данные;

– ввести зависимость для целевой функции;

– ввести зависимости для ограничений;

– указать назначение целевой функции (установить целевую ячейку);

– ввести ограничения;

– ввести параметры решения для задачи линейного программирования.

Реализация симплекс-метода в пакете Mathcad может быть осуществлена с помощью операторов символьных вычислений.

Систему ограничений записывают после набора оператора Given. Для записи знака равенства в уравнениях необходимо использовать комбинацию клавиш «Ctrl» и «=». Далее необходимо использовать оператор Find (x₁, x₂, …, x_M) , в скобках которого указаны все базисные переменные, а стрелка набирается при помощи клавиш «Ctrl» и «>». Аналитическое решение получают с помощью команды «Live Symbolics» из меню.

Пример:

Given

2 * х1 + 4 * х2 – 2*х3 + у1 = 400

0.6 * x1 + 0.2 * x2 + y2 = 65

2 * x1 + 4 * x2 + y3 = 1000

x3 + y4 = 250

–0.5 * x1 – 0.5 * x3 + 0.25 * y1 + 100

Find (x₂,y₂ y₃ y₄) –0.5 * x1 – 0.1 * x3 + 0.05 * y1 + 45

–2 * x3 + y1 + 600

–1 * x3 + 250

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