Пример задачи линейного программирования: задача использования ресурсов, её графическое решение
От общей задачи линейного программирования - к частной
На этом уроке будем учиться решать полностью сформулированную задачу линейного программирования - задачу использования ресурсов и наполнять содержанием основные определения, с которыми ознакомились на уроке "Задача линейного программирования: определения, модели, примеры, основные теоремы".
В экономико-математических моделях задачи линейного программирования численные решения вводят как неизвестные. Эти неизвестные в наиболее часто встречающихся задачах - о производстве - обозначают, например, виды продукции, которые следует производить в определённом количестве, чтобы получить максимальный доход, или чтобы стоимость их производства была минимальной. Неизвестные обычно записывают в виде буквы x с нижним индексом.
Система ограничений в задаче линейного программирования представляет собой систему линейных неравенств и (или) уравнений. Каждое неравенство или уравнение задаёт ограничение запасов одного из производственных факторов - вида сырья, времени, рабочей силы или чего-либо другого. Коэффициенты при неизвестных, записываемые обычно в виде буквы a с нижними индексами, обозначают количество производственного фактора, расходуемого для производства единицы соответствующего вида продукции. Это количество должно быть заранее известно.
Таким образом, система ограничений записывается в виде
Другой обязательный элемент модели задачи линейного программирования - функция цели. Как и система ограничений, она так же линейна. В функции цели присутствуют те же неизвестные, а коэффициенты при них, обычно записываемые в виде буквы c с нижними индексами, могут обозначать заранее известный доход от реализации единицы соответствующего вида продукции, а могут, как в задачах о расходе производственнных мощностей или в задаче о питании, обозначать расходы. Записывается функция цели в следующем виде:
.
Если функция цели задаёт доходы, то в задаче требуется найти максимум этой функции, если задаёт расходы, то требуется найти минимум.
Каждый вариант численных значений неизвестных, который удовлетворяет системе ограничений задачи линейного программирования, называется планом или программой. Показателем эффективности плана является всё та же функция цели. В каждой задаче линейного программирования может быть только одна функция цели. План, который соответствует максимуму или минимуму (то есть, в общем случае, оптимуму) функции цели, называется оптимальным планом.
Переменные в задаче использования ресурсов
Для изготовления двух видов продукции 
и 
требуется
четыре вида ресурсов (сырья): 
,
, 
,
. Запасы
сырья - соответственно 
, 
,
, 
единицы.
Доход от реализации одной единицы продукции
равен 
у. е.,
а доход от реализации одной единицы продукции
равен 
у. е.
Требуется получить наибольший доход от изготовления продукции и
, то есть, узнать, сколько единиц
и сколько единиц
нужно изготовить из имеющегося запаса сырья, чтобы получить максимальный доход.
Запишем задачу использования ресурсов в виде математических соотношений. Для удобства сначала запишем все данные в виде таблицы.
| Виды сырья | Запасы сырья | Виды продукции | |
|
|
||
|
|
 |
 |
|
|
 |
 |
|
|
 |
 |
|
|
 |
 |
| Доход от реализации одной единицы продукции | |
|
|
Система ограничений в задаче использования ресурсов
Количество единиц продукции
обозначим через 
, а
количество единиц продукции -
через 
.
Тогда на основании таблицы запишутся неравенства (ограничения):
В самом деле, для изготовления каждой единицы продукции
необходимо единиц сырья
, а для изготовления
единиц требуется
единиц сырья
. Для изготовления
единиц продукции
требуется
единиц сырья
. Так как запасы
сырья составляют
, то расход не может
превышать .
В результате получим первое неравенство 
.
Из остальных строк таблицы составили ещё 3 неравенства приведённой выше системы.
Что является решением задачи использования ресурсов
Доход от реализации единиц
продукции по
у. е. за
каждую единицу составляет 
у. е.,
аналогично доход от реализации
единиц продукции по
у. е.
за каждую единицу составит 
у. е.
Тогда суммарный доход от реализации обоих видов продукции и
запишется в виде
. В задаче
требуется вычислить максимальный доход, то есть найти 
.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример решения задачи графическим методом
Задача. Для изготовления столов и шкафов используется два вида древесины:
и
. Для изготовления
одного шкафа используется 
древесины и
древесины
. Для изготовления
одного стола используется 
древесины и
древесины
. Доход мастерской
от производства одного стола составляет 12 у. е., от производства одного шкафа - 15 у. е.
Определить, сколько столов и сколько шкафов должна изготовить мастерская, чтобы обеспечить
наибольшую рентабельность их производства, если в распоряжении мастерской имеется древесины
, а
древесины 
.
Решение. Составим таблицу.
| Вид древесины | Вид изделия | ||
| стол | шкаф | запасы | |
|
0,15 | 0,2 | 60 |
|
0,2 | 0,1 | 40 |
| Доход | 12 | 15 | |
Количество столов обозначим через ,
количество шкафов - .
Тогда из таблицы легко составить систему ограничений 
:
и функцию цели 
:
.
Найдём максимум C при условиях .
Для удобства неравенства
умножим на 100. Получим
,
где
.
Сокращая первое неравенство на 5, а второе на 10, получим
Далее, для упрощения вычислений введём масштаб 1:100, то есть, в правых частях последней системы неравенств отбросим по два нуля, тогда система запишется в виде
,
где
.
, найти 
.
На нашем сайте есть уроки Системы линейных неравенств и выпуклые множества точек и Графический метод решения задач линейного программирования. Дальнейшее решение задачи ведётся по схеме, изложенной на этих уроках.
Строим многоугольник решений системы. Для этого построим на координатной
плоскости прямые, заданные уравнениями системы. Для этого надо знать какие-либо две точки этой
прямой. Ищем точки пересечения каждой прямой с осью абсцисс, подставляя значение
в соответствующее
уравнение. Затем ищем точки пересечения каждой прямой с осью ординат, поставляя значение
. Ясно, что решениями
системы могут быть только положительные решения. Поэтому многоугольником решений будет четырёхугольник 
.
Теперь ищем значение максимума функции цели. Линейная форма 
геометрически означает семейство параллельных между собой прямых. Среди прямых этого семейства
есть опорные прямые mn и MN. Это такие прямые, которые имеют с многоугольником
хотя бы одну точку и многоугольник целиком лежит по одну сторону от этой прямой. Как видно из
рисунка, прямая mn является опорной, так как она касается многоугольника в точке О
и многоугольник целиком лежит правее (или выше) этой прямой. Прямая MN также является
опорной, так как имеет с многоугольником общую точку В и многоугольник целиком лежит
левее (или ниже) этой прямой. Из рисунка видно, что функция цели достигает максимума в точке B (80, 240) (не
забываем про масштаб). Подставляя координаты точки в функцию цели, имеем
.
Таким образом, максимум дохода в сумме 4560 у. е. мастерская получит, если изготовит 80 столов и 240 шкафов.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
| Назад<<< | Листать | Вперёд>>> |
Поделиться с друзьями
