 |
Пример решения типовой задачи
|
|
|
|
Предприятию необходимо изготовить два вида продукции А и В,
с использованием трех видов ресурсов R1, R2, R3 количество которых ограничено. Исходные данные задачи представлены в таблице:
| Вид ресурсов | Количество ресурсов, идущих на изготовление единицы продукции | Запасы ресурсов | |
| А | В | ||
| R1 | |||
| R2 | |||
| R3 | |||
| Доходы от реализации продукции |
Требуется составить план выпуска продукции, который дает максимальный доход.
Решение.
Обозначим через х 1 и х 2 количество единиц продукции видов А и В, планируемых к выпуску.
Известно, что доход от реализации единицы продукции А составляет 12 усл. ед. и количество этой продукции - х1. Следовательно, доход от реализации всей продукции А составит 12х1 усл. ед. Аналогично, доход от реализации всей продукции В составит 15х2 усл. ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:
Известно также, что имеющиеся на предприятии ресурсы ограничены. Это обстоятельство в свою очередь необходимо отразить в модели. Предприятие производит продукцию, используя три вида ресурсов. Естественно, что фактический расход никакого вида ресурса не должен превышать запасов соответствующего вида ресурсов на предприятии. Поскольку расход каждого вида ресурсов на единицу каждого вида продукции и запасы ресурсов известны, это обстоятельство отражается в следующих ограничениях:
Смысл первого ограничения состоит в том, что фактический расход ресурса R1 на производство продукции А и В, равный 6х1+6х2 (здесь 6х1 - количество единиц ресурса R1, идущего на изготовление х1 единиц продукции A; 6х2 - количество единиц ресурса R1, идущее на изготовление х2 единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R2 и R3 соответственно.
|
|
|
Количество продукции, выпускаемое предприятием, должно быть величиной положительной или равной нулю (если предприятие определенный вид продукции не производит). Следовательно, в модели должны присутствовать ограничения неотрицательности переменных:
Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:
Начнем решение задачи с построения области допустимых решений (рис.3)
В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х1=0 и х2=0 совпадают с осями координат. Полуплоскости x1>0,x2>0 лежат соответственно справа от оси Oх2 и выше оси Oх1. Множество точек, удовлетворяющих одновременно неравенствам 
представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.
Теперь рассмотрим ограничения задачи. Построим по порядку прямые:
` 6x1+6x2=36 или х1+х2=6 (а)
4х1+2х2=20 или 2х2+х2=10 (б)
4х1+8х2=40 или х1+2х2=10 (в)
и определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:
6x1+6x2<36
4x1+2x2<20
4x1+8x2<40
Для определения полуплоскости решений первого неравенства возьмем произвольную точку плоскости, не лежащую на прямой 6х1+6х2=36, например (0;0), и подставим ее координаты в неравенство 
.
В результате подстановки получили верное числовое неравенство 0< 36, и это означает, что начало координат лежит в полуплоскости решений первого неравенства. Сторона, в которой располагается полуплоскость от прямой, указывается штриховой.
|
|
|
Аналогично строим полуплоскость решений остальных неравенств.
X2
б)
a) N2
в) M
*6
в
 |
0 
N
C x1
6
D
Рисунок 3
Заштрихованная часть плоскости и представляет собой искомый многоугольник допустимых решений задачи (рисунок 3)
Теперь нужно среди точек построенного многоугольника найти такую, в которой целевая функция f =12 x 1+15 x 2 достигает максимального значения. Для этого построим прямую, заданную уравнением 12 х 1+15 х 2=0, которая является линией нулевого уровня функции f.
Направление возрастания линейной функции f =12 x 1+15 x 2 указывает вектор с началом в точке (0;0) и концом в точке М1(12,15), координаты которой равны коэффициентам при соответствующих переменных функции f.
Для нахождения оптимального плана нужно «передвигать» линию нулевого уровня f параллельно самой себе в направлении вектора до точки ее «последней встречи» с многоугольником, которая и является оптимальным планом задачи. В нашем случае это вершина В многоугольника OABCD - точка пересечения прямых (а) и (в). Координаты (
) точки найдем, решив систему уравнений.
откуда х 1*=2, х 2*=4.
Найдем соответствующее значение целевой функции:
усл. ед.
Итак, для обеспечения максимального дохода от реализации готовой продукции предприятию необходимо выпустить 2 ед. продукции вида А и 4 ед. продукции вида В. При таком плане доход от реализации составит 84 усл. ед.
|
|
|
