Предприятие выпускает два вида продукции А и В. Для производства продукции используется сырье трех типов. На изготовление изделия А затрачивается а1, а2, а3 единиц сырья каждого типа. На изготовление изделия В затрачивается b1, b2, b3 единиц сырья каждого типа. Предприятие обеспечено сырьем каждого типа в количестве р1, р2, р3 единиц. Прибыль от реализации единицы изделия А и В составляет с1, с2 денежных единиц соответственно.
1) составить математическую модель задачи;
2) решить задачу графическим методом;
3) решить задачу симплекс-методом;
4) дать экономическую интерпретацию полученных результатов, оценить остатки сырья в случае реализации оптимального плана;
Сырье Изделия Запасы ресурсов
А В
1 5 2 281
2 2 3 320
3 4 6 502
Прибыль от реализации 32 40
Решение
Составим математическую модель задачи
х1 – количество выпускаемой продукции А
х2 – количество выпускаемой продукции В
Так как запасы ресурсов ограничены, то составим неравенства системы ограничений
5x1+2x2≤281 2x1+3x2≤320 4 x1+6x2≤502
x1≥0, x2≥0
По своему экономическому содержанию переменные х1, х2 могут принимать только неотрицательные значения.
F = 32x1 + 40x2 → max - целевая функция (прибыль от производства выпущенной продукции)
Получили задачу линейного программирования – при имеющихся запасах ресурсов и прибыли за единицу продукции, составить такой план, чтобы получить наибольший доход.
Решим задачу графическим методом
Введем систему декартовых координат на плоскости x1О x2, и построим области, описываемые системой ограничений.
Каждое неравенство определяет полуплоскость с границей , задаваемой прямой. Множество решений системы есть пересечение полуплоскостей.
Выпишем систему соответствующих граничных прямых
5x1+2x2=281 (1)
2x1+3x2=320 (2)
4 x1+6x2=502 (3)
Многоугольник ОАВС- область решения задачи
Построим прямую, отвечающую значению функции F=0
Вектор-градиент С (32,40), составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Будем перемещать эту прямую параллельным образом в направлении вектора
С (32, 40)
.
Чтобы получить максимальное решение, двигаем прямую до точки выхода из области допустимых решений обозначенной плоскости.
Прямая Fmax покидает область допустимых решений в точке В, значит, в этой точке достигается наибольшее значение целевой функции.
Точка В образована пересечением линий (1) и (3).
Найдем координаты точки В.
5x1+2x2=281
4 x1+6x2=502 x1=31 x2=63
Координаты точки В (31,63)
F x1, x2=32*31+40*63=3512 максимальное значение целевой функции
Решим задачу симплекс методом
Введем дополнительные переменные х5, х6, х7 – количество неиспользованных ресурсов. Запишем эту задачу в канонической форме
5x1+ 2x2+ x3=2812x1+3x2+ x4 =3204x1+6x2+ +x5=502xi≥0 i=1,2,3,4,5
F = 32x1 + 40x2 → max
В качестве базисных переменных выберем переменные х3, х4, х5, так как они входят только в одно уравнение и с единичным коэффициентом. Составим первый опорный план.
Базис хi
В х1 х2 х3 х4 х5
Х3 281 5 2 1 0 0
Х4 320 2 3 0 1 0
Х5 502 4 6 0 0 1
F 0 -32 -40 0 0 0
Данный план не оптимален, т. к. в индексной строке имеются отрицательные элементы.
Итерация 1
В качестве нового ведущего столбца возьмем столбец с наибольшим по модулю значением. Это второй столбец (выделим цветом) max-32, -40=40
Для определения ведущей строки разделим столбец В на элементы ведущего столбца и найдем наименьшее значение (делим на положительные числа) min{2812, 3203,5026 }=8323
третья строка будет ведущей (выделим цветом )
На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент 6
Базис хi
В х1 х2 х3 х4 х5 biai>0
Х3 281 5 2 1 0 0 281/2=140,5
Х4 320 2 3 0 1 0 320/3=106,6
Х5 502 4 6 0 0 1 502/6=83,7
F 0 -32 -40 0 0 0
Пересчитаем симплекс-таблицу: в новом плане вместо переменной х5, в новый план войдет переменная х2, ведущую строку разделим на 6, на месте разрешающего элемента запишем 1, в остальных клетках столбца х3 запишем нули, остальные элементы таблицы пересчитаем по правилу прямоугольника
Получим новую таблицу
Базис хi
В х1 х2 х3 х4 х5
Х3 341/3 11/3 0 1 0 -1/3
Х4 69 0 0 0 1 -1/2
Х2 251/3 2/3 1 0 0 1/6
F 10040/3 -16/3 0 0 0 20/3
Данный план не оптимален, т