Задача №30
Для производства различных изделий А и В используются три вида сырья. На изготовление единицы изделия А требуется затратить сырья первого вида 10кг., сырья второго вида 5кг., сырья третьего вида 4кг. На изготовление единицы изделия В требуется затратить сырья первого вида 9кг., сырья второго вида 11кг., сырья третьего вида 15кг.
Производство обеспечено сырьём первого вида в количестве 1870кг., сырьём второго вида в количестве 1455кг., сырьём третьего вида в количестве 1815кг. Прибыль от реализации единицы готового изделия А составит 7руб., а изделия В 9руб.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Решить задачу симплексным методом путём преобразования симплекс-таблиц.
Дать графическое решение задачи.
Решение:
Формализуем условия задачи: обозначим количество единиц произведённого товара А за х, товара В – за у. Тогда требуется максимизировать функцию w=7х+9у при следующих ограничениях:
10х+9у1870 (ограничения по количеству сырья 1-ого вида)
5х+11у1455 (ограничения по количеству сырья 2-ого вида)
4х+15у1815 (ограничения по количеству сырья 3-его вида)
х0 (естественные ограничения на единицы товара)
у0
Перепишем полученную задачу линейного программирования в канонической форме:
-7х-9у -> min (ЗЛП в канонической форме – задача на минимум, найдя минимум данной функции, мы найдём максимум требуемой величины - прибыли)
Ограничения – равенства => вводим дополнительные переменные a, b, c 0, такие что
10х+9у+а=1870
5х+11у+b=1455
4х+15у+c=1815
Выбираем в качестве базисных переменных a,b,c, т.к. соответствующие им столбцы в матрице ограничений линейно независимы. Записываем симплекс-таблицу:
x
y
a
b
c
w
0
-7
-9
0
0
0
a
1870
10
9
1
0
0
b
1455
5
11
0
1
0
c
1815
4
15
0
0
1
Эта таблица прямо, но не двойственно допустима => для нахождения оптимального решения надо сделать преобразование базиса: выбираем первый столбец таблицы, отношение 1870/10 минимально среди 1455/5 и 1815/4 => в качестве ведущего выбираем элемент (1,1). Делаем замену базиса, получим:
x
y
a
b
c
w
1309
0
-2.7
0.7
0
0
x
187
1
0.9
0.1
0
0
b
520
0
6.5
-0.5
1
0
c
1067
0
11.4
-0.4
0
1
В нулевой строке по-прежнему есть отрицательный элемент, значит, решение не оптимально. Снова делаем преобразование базиса: ведущий элемент (2,2) (аналогично выбираем минимальное среди отношений 187/0.9 520/6.5 и 1067/11.4, минимальное - 520/6.5)
x
y
a
b
c
w
1525
0
0
32/65
27/65
0
x
115
1
0
11/65
-9/65
0
y
80
0
1
-1/13
2/13
0
c
155
0
0
31/65
-114/65
1
Итак, получили прямо и двойственно допустимую таблицу, а значит, значения х=115 и у=80 оптимальны.
Ответ: план производства, обеспечивающий максимальную прибыль, таков: требуется произвести 115 единиц товара А и 80 единиц товара В.
Графическое решение:
Серым заполнена область, в которой лежат все наши допустимые решения, т.е. те, которые удовлетворяют ограничениям задачи. Красным цветом выделена линия уровня целевой функции, стрелкой указано направление роста целевой функции (вектор градиента). Смещая линию уровня в указанном направлении, мы увеличиваем значение целевой функции. При этом, дойдя до крайней точки закрашенного множества, мы получим максимальное допустимое ограничениями значение целевой функции. Соответствующие значения x=115, y=80, что подтверждает решение, полученное симплекс-методом.
Задача №33.
На трёх базах А, А, А имеется однородный груз в количестве 250т. на А, 200т. на А и 150т. на А. Полученный груз требуется перевезти в пять пунктов: 180т. в В, 120т в В, 90т. в В, 105т. в В и 105т. в В.
Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:
Спланировать перевозки так, чтобы их общая стоимость была минимальной.
Решение:
Составляем транспортную таблицу (в левом нижнем углу