Информатика (стр. 3 )

2.5.  Линейное программирование (ЛП)

Математический подход – основа в задачах планирования. Первые работы в этом направлении принадлежат , который в 1939 г. указал общий метод решения задач линейного программирования (ЗЛП), связанных с составлением оптимального плана при оптимизации производственных процессов и др.

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

Первоначально рассмотрим геометрическое решение ЗЛП, затем – ее решение с использованием специальных средств MS Excel.

Постановка задачи. Предположим, что для производства двух видов строительных изделий (плит и колонн) используются заполнитель, цемент и арматура. При этом на изготовление одной плиты расходуется 3 т заполнителя, 4 т цемента и 3 т арматуры, а на изготовление одной колонны – 1 т заполнителя, 3 т цемента и 4 т арматуры. Обеспеченность заполнителем составляет 30 т, цементом – 52 т и арматурой – 60 т. От реализации одной плиты предприятие имеет прибыль 6 ден. ед., а от реализации одной колонны – 3 ден. ед.

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

Построим математическую модель задачи. Обозначим количество реализуемых плит x, а колонн – x. Очевидно, что на данный производственный процесс нужно 3x+x тонн заполнителя, 4x+3x тонн цемента и 3x+4x тонн арматуры. Общая прибыль от реализации продукции равна 6x+3x ден. ед. Поскольку заполнитель, цемент и арматура не могут расходоваться в количестве, превышающем их имеющийся запас, получим ограничения в виде неравенств:

Помимо этого, следует учесть, что количество единиц продукции всегда неотрицательно, то есть x0, i=1,2, и не может быть дробным.

Общая прибыль от реализации выражается целевой функцией F=6x+3x, наибольшее значение которой надо найти на множестве решений.

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

Построим графики функций

x=30-3x, x=x, x=15-0.75x,

задающих систему ограничений. Все эти функции – линейные, т. е. их графики представляют собой прямые линии. Поскольку для построения прямой достаточно двух точек, выберем два значения Х1 и вычислим для каждой из них значение Х2.

Рисунок 20– Расчетная таблица для построения графиков в режиме значений и формул

Чтобы построить графическую интерпретацию задачи, воспользуемся мастером диаграмм (см. п.1.8). При этом в качестве типа диаграммы следует выбрать «точечную» со значениями, соединенными прямыми без маркеров, а в качестве диапазона – массив ячеек A1:D3.

Рисунок 21 – Построение области допустимых решений

Легко вычислить, что точкой пересечения графиков функций
4x+3x=52 и 3x+4x=60 является точка (4; 12), 3x+x=30 и 4x+3x=52 - точка (7.6; 7.2). Таким образом, на диаграмме можно выделить многоугольник решений, вершинами которого являются точки (0; 0), (0; 15), (4; 12), (7.6; 7.2) и (10; 0).

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

Рассмотрим взаимодействие функции прибыли с уже построенными функциями ограничений. Для этого дополним графическую интерпретацию задачи. Построим ряд линий уровня, образующих так называемый след целевой функции. Линии уровня прибыли являются графиками целевой функции F=6x+3x, построенными при различных значениях F. Поскольку значение F не определено, зададимся несколькими конкретными значениями величины прибыли, чтобы проанализировать ее влияние на поведение целевой функции. Построим, например, линии уровня при F=15, 30 и 45. Можно построить эти линии также как мы строили линии ограничений (добавить на диаграмму три ряда данных) или воспользоваться средствами, предназначенными для рисования. Для этого сначала определим нули (точки пересечения с осями) этих функций.

Для функции 6x+3x=15 таковыми будут точки (2.5; 0) и (0; 5),

для функции 6x+3x=30 – точки (5; 0) и (0; 10),

для функции 6x+3x=45 – точки (7.5; 0) и (0; 15).

Выведем на экран панель инструментов Рисование (Меню: ВидПанели инструментовРисование). Пользуясь инструментом «Линия», проведем все три линии через рассчитанные точки пересечения с осями. Полученные три линии параллельны друг другу, что, впрочем, вполне обоснованно с точки зрения математики, т. к. коэффициент угла наклона у них одинаковый (-6/3). Легко заметить, что при увеличении значения прибыли (а мы хотим, чтобы она была максимальная) линии целевой функции (прибыли) смещается параллельно самой себе в направлении от начала координат. С помощью инструмента «Стрелка» на последней линии уровня прибыли укажем это направление (направление градиента).

Таким образом, можно говорить о том, что при увеличении значения F (прибыли) след целевой функции смещается в направлении градиента (перпендикуляра к линиям уровня). Скопируем одну из линий уровня прибыли (например, последнюю), перемещаем ее в направлении градиента до тех пор, пока она имеет хотя бы одну общую точку с одластью допустимых значений. Последняя общая точка следа целевой функции с многоугольником решений соответствует оптимальному решению ЗЛП. Таким образом, линия уровня, проходящая через эту точку, соответствует графику функции F=6x1опт+3x2опт.

Очевидно, что оптимальное решение данной ЗЛП достигается в вершине многоугольника решений, являющейся пересечением прямых 3x+x=30 и 4x+3x=52. Координаты этой точки можно обозначить как x и x.

Как уже было сказано выше, эти координаты равны 7.6 и 7.2.

Итак, Х1опт=7,6 а Х2опт=7,2

F=6x+3x=6*7.6+3*7.2=67.2.

Однако нетрудно заметить, что найденное решение не удовлетворяет наложенному на управляемые переменные требованию целочисленности. Поэтому можно сделать вывод о том, что в случае данной задачи геометрический метод решения позволяет получать лишь квазиоптимальное решение. Для получения действительного оптимального решения ЗЛП нужно использовать специальные средства, входящие в состав пакета Microsoft Excel, о чем и пойдет речь ниже.

В MS Excel решение ЗЛП можно найти с помощью надстройки «Поиск решения». Перейдем на другой лист текущей книги MS Excel, где зарезервируем две пустые ячейки для значений переменных x и x, а в других ячейках запрограммируем функции – ограничения и целевую функцию так, как они были даны в условии задачи. Данные для решения задачи могут быть размещены, например, так:

Рисунок 22 – Вариант подготовки данных для решения ЗЛП

Ячейки В2 и В3 предназначены для искомых значений переменных. При подготовке данных их можно оставить пустыми. Далее следует вызвать программу «Поиск решения» (Меню: СервисПоиск решения) и сформировать настройки диалогового окна в соответствии с условиями задачи.

Целевая ячейка – ячейка, в которой записана формула для вычисления значения прибыли. Для указания ее адреса достаточно просто щелкнуть по этой ячейке левой клавишей мыши. Изменяемые ячейки – те, что предназначены для варьируемых переменных. Для формирования списка ограничений необходимо активизировать окно «Ограничения» т. е. щелкнуть по нему левой клавишей мыши и затем по кнопке «Добавить». Первые два ограничения – физические, остальные описывают ограничения по запасам сырья.

Рисунок 23 – Настройка окна «Поиск решения»

После этого запускаем «Поиск решения» на выполнение (кнопка «Выполнить»).

Рисунок 24 – Решение ЗЛП

Получаем, что наилучшая с точки зрения максимальной прибыли стратегия производства стройматериалов предполагает выпуск 7 плит и 8 колонн. При этом прибыль от реализации составит 66 ден. ед.

Итак, x=7, x=8 и F=66.

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

2.6.  Транспортная задача

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

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

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

Типовая постановка задачи.

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

Исходными данными для решения задачи являются:

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

Количество строительных конструкций, поставляемых каждым заводом – производителем для данных строек в тот же период времени (в решении задачи – мощности поставщиков).
Важно: суммарное количество изделий, поставляемых заводами строго равно суммарной потребности всех строек, участвующих в задаче. Задача в этом случае является замкнутой.

Стоимость перевозки одной строительной конструкции с одного завода на одну стройку. Этот параметр определен для каждой пары «завод – стройка»

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

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

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

Оптимальное решение – решение, при котором целевая функция принимает оптимальное значение.

Целевой функцией в транспортной задаче является функция затрат на перевозки, которая должна принимать минимальное значение.

Требуется составить план перевозок, соответствующий минимальному уровню затрат на перевозки.

Исходные данные и решение задачи удобнее всего расположить в таблице. Ограничившись для конкретности тремя заводами – поставщиками (ЖБИ-1 ЖБИ-2, ЖБИ-3) и четырьмя потребителями (стройка 1, стройка 2, стройка 3, стройка 4) запишем условия задачи в матрицу перевозок (Таблица 1).

Таблица 1 - Матрица перевозок

	Потребители	Мощности поставщиков
Стройка1	Стройка 2	Стройка 3	Стройка 4
ЖБИ-1	С11 Х11	C12 Х12	C13 Х13	C14 Х14	B1
ЖБИ-2	C21 Х21	C22 Х22	C23 Х23	C24 Х24	B2
ЖБИ-3	C31 Х31	C32 Х32	C33 Х33	C34 Х34	B3
Потребность	A1	A2	A3	A4

Каждая клетка средней части таблицы является пересечением i-той строки и J-того столбца, т. е. соответствует одной паре «завод – стройка». Здесь i (номер строки и номер поставщика) = 1,2,3;

J (номер столбца и номер стройки)=1,2,3,4.

В правом верхнем углу каждой клетки стоит параметр C, характеризующий себестоимость перевозки единицы веса продукции от поставщика к потребителю. В левом нижнем углу стоит параметр X, характеризующий объем перевозки изделий от поставщика к потребителю. Причем значение C– известно (входит в состав исходных данных), а совокупность значений параметра X количество единиц продукции, перевозимой от i-го поставщика к j-му потребителю.

Если обозначить количество потребителей через n, а количество заводов – производителей через m, потребности строек Ai, мощности заводов Bi , математическая постановка задачи выглядит следующим образом:

Стоимость перевозок (целевая функция)

(1)

Ограничения имеют вид:

(2)

; i=1,…,n, (3)

(физические ограничения) (4)

(условие замкнутости задачи) (5)

Требуется организовать перевозки так (т. е. выбрать X, удовлетворяющие системам уравнений (2) и (3)), чтобы суммарные транспортные расходы (формула 1) минимизировались.

Для задачи выбранной размерности (n=3; m=4) затраты на перевозки вычисляются по формуле:

F=C11X+C12X+C13X+C14X+C21X+C22X+C23X+C24X+ +C31X+C32X+C33X+C34X ® min (6)

Сама по себе задача отыскания f смысла не имеет, так как очевидно, что f=0 при X=0. Это тривиальное решение и оно не устраивает, по крайней мере, потребителей. Действительно, необходимо учесть следующие два ограничения:

1. Потребители должны получить всю необходимую им продукцию, т. е.

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

Поскольку эти ограничения должны выполняться одновременно, их следует объединить в одну систему линейных уравнений, причем, с учетом условия замкнутости задачи (выражение 5), набор из этих n+m (для данной задачи 3+4=7) уравнений является избыточным и одно уравнение (любое) можно исключить. Таким образом, имеется система n+m-1 (для данной задачи 3+4-1=6) линейных уравнений c n x m (для данной задачи 3x4=12) неизвестными, т. е. количество неизвестных больше количества уравнений. Как известно из курса математики в таком случае система линейных уравнений имеет множество решений. В приложении к данной задаче любое из них является допустимым, т. к. все ограничения выполняются. Поскольку значения Xij (решение системы) являются аргументами целевой функции, затраты на перевозки для каждого из допустимых решений разные.

С точки зрения минимизации затрат логично предположить, что план перевозок должен содержать минимальное количество перевозок (значений Xij, отличных от нуля), а именно n+m-1 в соответствии с количеством уравнений. План перевозок, отвечающий этим условиям, называется базисным, а участвующие в нем n+m-1 переменных – базисными переменными, остальные переменные являются свободными и, естественно, имеют значения равные нулю.

Рассмотрим пример:

Имеется три завода – поставщика (ЖБИ-1 ЖБИ-2, ЖБИ-3) и четыре потребителя (стройка 1, стройка 2, стройка 3, стройка 4). Запишем условия задачи в матрицу перевозок.

Таблица 2 - Исходные данные

Поставщики	Потребители	Мощность поставщика
Стройка 1	Стройка 2	Стройка 3	Стройка 4
ЖБИ-1	2	3	4	1	100
ЖБИ-2	3	3	5	2	150
ЖБИ-3	3	2	4	5	180
Потребность стройки	80	120	200	30	430

В закрашенной фоном ячейке на пересечении строки «Потребность стройки» и «Мощность поставщика» стоит сумма всех потребностей, которая равна сумме всех мощностей, факт этого равенства следует проверить перед началом решения задачи.

Общая стоимость перевозки F определяется как сумма произведений себестоимостей на объемы перевозок:

F=2X+3X+4X+X+3X+3X+5X+2X+3X+2X+4X+5X

В матрице перевозок (Таблица 1) каждому пересечению строки и столбца (паре «поставщик – потребитель) соответствует два значения: известное – стоимость перевозки одного изделия с данного завода на данную стройку и неизвестное – количество перевозимых изделий. Однако, задача будет решаться средствами MS Excel, а в ячейку MS Excel записать два значения нельзя, поэтому разносим исходные данные и решение в разные таблицы. В данной таблице содержатся исходные данные, поэтому из перечисленных выше двух параметров в центральной части таблицы содержатся только значения Cij (себестоимости перевозок).