В производстве пользующихся спросом двух изделий, А и В, принимают участие 3 цеха фирмы. На изготовление одного изделия А 1-й цех затрачивает 7 ч., 2-й цех – 7 ч., 3-й цех – 8 ч. На изготовление одного изделия В 1-й цех затрачивает 13 ч., 2-й цех – 8 ч., 3-й цех – 2 ч. На производство обоих изделий 1-й цех может затратить не более 363 ч., 2-й цех – не более 327 ч., 3-й цех – не более 429 ч.
От реализации одного изделия А фирма получает доход 6 тыс. руб., изделия В – 4 тыс. руб.
Определить оптимальный план производства изделий, обеспечивающий максимальный доход от реализации всех изделий А и В.
Решение
Математическая модель задачи
Переменные задачи:
x1 – количество изделий А, ед;
x2 – количество изделий В, ед.
Тогда затраты времени цехов составят:
7x1+13x2 – затраты 1-го цеха, час;
7x1+8x2 – затраты 2-го цеха, час;
8x1+2x2 – затраты 3-го цеха, час.
Ограничения:
На производство обоих изделий 1-й цех может затратить не более 363 ч., 2-й цех – не более 327 ч., 3-й цех – не более 429 ч., значит, должны выполняться неравенства:
7x1+13x2≤363 (1)
7x1+8x2≤327(2)
8x1+2x2≤429(3)
По смыслу задачи переменные должны быть неотрицательными числами:
xi≥0, i=1,2(4)
Целевая функция:
Доход от реализации изделий (тыс. руб.)
F=6x1+4x2(5)
Таким образом, получена математическая модель задачи:
Найти максимальное значение функции F=6x1+4x2 при условиях:
7x1+13x2≤363 7x1+8x2≤3278x1+2x2≤429xi≥0, i=1,2
Решение задачи графическим методом
Определение области допустимых решений (ОДР)
В неравенствах системы ограничений заменим знаки неравенств на знаки точных равенств и построим соответствующие им прямые.
l1:7x1+13x2=363
x2=36313-713x1
Строим прямую l1 по двум точкам:
x1
-10 60
x2
33,31 -4,38
l2: 7x1+8x2=327
x2=3278-78x1
Строим прямую l2 по двум точкам:
x1
-10 60
x2
49,625 -11,625
l3: 8x1+2x2=429
x2=214,5-4x1
Строим прямую l3 по двум точкам:
x1
40 60
x2
54,5 -25,5
l4: x1=0 – ось ординат
l5: x2=0 – ось абсцисс
Строим полученные прямые (рис. 1).
Рис. 1. Прямые, определяющие неравенства системы органичений
Определяем полуплоскости, удовлетворяющие неравенствам системы ограничений: их пересечение образует область допустимых решений.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству системы ограничений, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты исходному неравенству. Если удовлетворяют, то искомой является та полуплоскость, которой эта точка принадлежит; в противном случае – другая полуплоскость.
Прямая l1
Точка 0;0
Неравенство 7x1+13x2≤363
0+0≤363 – верное
Т.е
. выбираем полуплоскость, содержащую точку (0;0)
Прямая l2
Точка 0;0
Неравенство 7x1+8x2≤327
0+0≤327 – верное
Т.е. выбираем полуплоскость, содержащую точку (0;0)
Прямая l3
Точка 0;0
Неравенство 8x1+2x2≤429
0+0≤429 – верное
Т.е. выбираем полуплоскость, содержащую точку (0;0)
Четвертое и пятое неравенства определяют первую координатную четверть.
Получим область допустимых решений задачи линейного программирования (рис. 2).
Рис. 2. Область допустимых решений
Многоугольник ОABCD – область допустимых решений.
Определение оптитмального решения
Координаты любой точки, принадлежащей ОДР, удовлетворяют неравенствам системы ограничений и условию неотрицательности переменных. Поэтому исходная задача будет решена, если мы сможем найти точку, принадлежащую этой области, в которой целевая функция принимает максимальное значение. Чтобы найти такую точку, построим прямую (линию уровня) 6x1+4x2=h, проходящую через многоугольник решений.
Возьмем h=120 и построим прямую 6x1+4x2=120 по точкам:
x1
0 20
x2
30 0
Вектор c(6;4) служит для определения направления перемещения линии уровня. В качестве вектора направления выберем вектор c1(12;8), сонаправленный вектору c (в масштабах рисунка его удобней использовать), Перемещая линию уровня в направлении вектора c1, получаем, что последней общей точкой ее и области допустимых решений является точка С пересечения прямой l2 и оси абсцисс. (рис. 3).
Рис. 3. Нахождение оптимального плана графическим методом
Для определения координат точки С составим и решим систему уравнений:
7x1+8x2=327 x2=0 ⇔x1=3277 x2=0 ⇔x1=4657 x2=0
Найдем соответствующее значение целевой функции:
Fmax=6∙4657+4∙0=28027.
Таким образом, X*(4657;0) – оптимальный план, при котором целевая функция принимает максимальное значение Fmax=28027.
Т.е., максимальная прибыль, равная 28027 тыс
Задать вопрос
на новый заказ в Автор24.
