Для производства двух видов изделий A1 и A2 предприятие использует три вида сырья B1,

Для производства двух видов изделий A1 и A2 предприятие использует три вида сырья B1, B2, B3 . Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. Прибыль от реализации одного изделия каждого вида равна c1, c2 , а общее количество сырья равно b1, b2, b3 . Считая, что изделия могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий будет максимальной. а) составить математическую модель задачи линейного программирования, решить её графически; б) перейти к канонической модели и решить её симплекс-методом, преобразованием симплекс-таблиц; в) для стандартной модели задачи составить двойственную модель и решить её, используя теоремы двойственности; г) выполнить проверку решений в пакете Excel.

Решение.
1. Составим математическую модель задачи линейного программирования и решим её графически.
Пусть необходимо выпустить продукцию вида A1 в количестве x1 , вида A2 в количестве x1 , тогда ограничения имеют вид:
По сырью S1: 5x1+4x2≤40,
по сырью S2: 5x1+2x2≤35,
по сырью S3: x1+4x2≤24.
Так как количество продукции неотрицательно, то x1≥0 и x2≥0.
Доход определяется как F=3x1+2x2, который необходимо максимизировать.
Математическая модель имеет вид
F=3x1+2x2⟶max
5x1+4x2≤40,5x1+2x2≤35,x1+4x2≤24,x1≥0 ,x2≥0
Построим область допустимых решений (ОДР). Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штриховкой).
L1: 5x1+4x2=40 ⇒ x2=10-1,25x1
x1
x2
0 10
8 0
L2: 5x1+2x2=35 ⇒ x2=17,5-2,5x1
x1
x2
0 17,5
7 0
L3: x1+4x2=24 ⇒ x2=6-0,25x1
x1
x2
0 6
24 0
Получили ОДР – это многоугольник ABCDE
Рассмотрим целевую функцию задачи F=3x1+2x2⟶max. Построим прямую,, отвечающую значению функции F=3x1+2x2=0. Вектор градиента целевой функции равенg=(3;2)T; также изобразим его на рисунке. Значения целевой функции во всех точках любой прямой, перпендикулярной этому вектору, одинаковы, а при сдвиге указанной прямой в направлении вектора g=(3;2)T значения целевой функции увеличиваются

. Используя чертеж, находим, что наибольшее значение целевой функции в пятиугольнике ABCDE достигается в точке D – точке пересечения прямых 1 и 2. Находим координаты этой точки:
C:5x1+4x2=405x1+2x2=35⇒x1=6x2=2,5
Максимальное значение целевой функции F=3x1+2x2 достигается при x1=6 и x2=2,5 и равно Fmax=F6;2,5=3*6+2*2,5=23
Таким образом, для получения максимального дохода необходимо выпустить 6 ед. продукции вида A1и 2,5 ед. продукции вида A2 , доход при этом будет равен 23 ед.
Определим остатки сырья.
Предполагаемый расход сырья B1 (в запасах 40 ед.):
5*6+4*2,5=40 ⇒остаток сырья составит 0 ед.
Предполагаемый расход сырья B2 (в запасах 35 ед.):
5*6+2*2,5=35 ⇒остаток сырья составит 0 ед.
Предполагаемый расход сырья B3 (в запасах 24 ед.):
6+4*2,5=16 ⇒остаток сырья составит 8 ед.
Проверка решения в MS Excel
2. Перейдём к канонической модели и решим её симплекс-методом, преобразованием симплекс-таблиц.
Изначально модель имеет стандартный вид
F=3x1+2x2⟶max
5x1+4x2≤40,5x1+2x2≤35,x1+4x2≤24,x1≥0 ,x2≥0
Каноническая модель имеет вид
F1=-3x1-2x2⟶min
5x1+4x2+x3=40,5x1+2x2+x4=35,x1+4x2+x5=24,x1≥0,x2≥0,x3≥0,x4≥0,x5≥0
Внесём коэффициенты в таблицу
Базис B x1
x2
x3
x4
x5
x3
40 5 4 1 0 0
x4
35 5 2 0 1 0
x5
24 1 4 0 0 1
F1
0 3 2 0 0 0
В таблице с1 = 3, с2 =2 ,max{3;2} = 3, неизвестная x1 перейдёт в базисную