Исследование математических операций 2 (стр. 6 из 28)
Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т видов шириной Hi (
). Известна потребность в нестандартных рулонах каждого вида, она равна bi. Возможны n различных вариантов построения технологической карты раскроя рулонов стандартной ширины L на рулоны длиной Hi .Обозначим через aij количество рулонов i-го вида, получаемых при раскрое единицы стандартного рулона по j-му варианту. При каждом варианте раскроя на каждый стандартный рулон возможны потери, равные Pi . К потерям следует относить также избыточные рулоны нестандартной длины li, получаемые при различных вариантах раскроя yij , 
.
В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j-м варианте раскроя. Определим переменную следующим образом: xj - количество стандартных рулонов, разрезаемых по варианту j,
.Целевая функция - минимум отходов при раскрое
. (2.29)
Ограничение на удовлетворение спроса потребителя
,
, 
. (2.30)Пример 2.8. Транспортная задача.
Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij , 
, 
. Запасы грузов у поставщиков равны ai , . Известны потребности каждого потребителя bi , . Будем считать, что суммарные потребности равны суммарным запасам:
.
Требуется составить такой план перевозок, чтобы обеспечить минимальные суммарные затраты при полном удовлетворении потребностей.
Введем переменные хij - количество груза, перевозимого от i-го поставщика j-му потребителю. Ограничения задачи выглядят следующим образом:
потребности всех потребителей должны быть удовлетворены полностью:
(2.31)или в общем виде:
,
груз от поставщика должен быть вывезен полностью:
(2.32)
или в общем виде:
, условие неотрицательности переменных:
,
, Целевая функция - минимизировать суммарные затраты на перевозку:
(2.33)
Количество поставщиков и потребителей в общем случае может быть произвольным.
Мы рассмотрели девять примеров типовых задач линейного программирования. Обобщая их, можно сделать следующие выводы.
1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами.
2. Линейная функция может стремиться как к максимуму, так и к минимуму.
3. Переменные в задачах всегда неотрицательны.
Напомним, что от любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программирования.
Назад | Содержание | Далее
2.3. Графическое решение задачи линейного программирования
Графически способ решения задач линейного программирования целесообразно использовать для:
решения задач с двумя переменными, когда ограничения выражены неравенствами;
решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
Запишем задачу линейного программирования с двумя переменными:
целевая функция:
; (2.34)
ограничения:
; (2.35)
. (2.36)
Каждое из неравенств (2.35) – (2.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
; ( ; х1 = 0; х2 = 0. В том случае, если система неравенств (2.35) – (2.36) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.Областью допустимых решений системы неравенств (2.35) – (2.36) может быть:
выпуклый многоугольник;
выпуклая многоугольная неограниченная область;
пустая область;
луч;
отрезок;
единственная точка.
Целевая функция (2.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значений Z.
Вектор 
с координатами с2 и с1, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z.
Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2.35) – (2.36) и семейство параллельных прямых (2.34), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.
Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.
Для определения данной вершины построим линию уровня
, проходящую через начало координат и перпендикулярную вектору , и будем передвигать ее в направлении вектора до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяет оптимальный план данной задачи.Заканчивая рассмотрение геометрической интерпретации задачи (2.35) – (2.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 2.1 – 2.4. Рис. 2.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 2.3 изображен случай, когда максимум недостижим, а на рис. 2.4. – случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора
, а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения. 
Рис. 2.1. Оптимум функции Z достижим в точке А
Рис. 2.2. Оптимум функции Z достигается в любой точке |АB|
