Для изготовления двух видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице 1.
Таблица 1
Тип сырья Нормы расхода сырья на одно изделие, ед. Запасы сырья, ед.
А Б
I 2 3 12
II 1 1 6
III 2 1 8
Прибыль изделия, ден. ед. 4 1 Х
Решение
Составим экономико-математическую модель задачи.
Переменные:
х1 – количество товаров группы А, ед.;
х2 – количество товаров группы В, ед.
Ограничения:
По использованию сырья I-го вида, усл. ед.:
2х1 + 3х2 12.
По использованию сырья II-го вида, усл. ед.:
х1 + х2 6.
По использованию сырья III-го вида, усл. ед.:
2х1 + х2 8.
Условие не отрицательности переменных:
х10, х20.
Максимальное значение целевой функции, ден. ед.:
F(х) = 4х1 + х2 mах
Система ограничений задачи, решаемой симплексным методом задана в виде неравенств смысла “”, правые части которых вi0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных х3; х4; х5; которые образуют базис и называются базисными переменными. Они определяют объемы неиспользованных ресурсов:
2x1+3x2+x3=12;x1+x2+x4=6;2x1+x2+x5=8.
Решим систему уравнений относительно базисных переменных:
x3=12-(2x1+3x2);x4=6-(x1+x2);x5=8- (2x1+x2).
Функцию цели запишем в виде уравнения F(х) = 0 – (– 4х1 – х2).
Получим первый опорный план. Предположим, что основные переменные в системе уравнений являются свободными и приравняем их к нулю (х1=0, х2=0). Тогда дополнительные переменные (базисные) будут равны объёмам ограничений (х3=12; х4=6; х5=8)
. Следовательно, товары не продаются, а ресурсы не используются, доход равен нулю: f(x)=0. Заносим этот план в первую симплексную таблицу. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположными знаками.
Таблица 2 – Первая симплексная таблица
План Базисные переменные Свободные члены Основные переменные Дополнительные переменные
х1 х2 х3 х4 х5
I х3 12 2 3 1
х4 6 1 1
1
х5 8 2 1
1
Индексная строка f(x) 0 -4 -1
Опорный план, представленный в первой симплексной таблице, не оптимальный, так как. в индексной строке находятся отрицательные коэффициенты: -4; -1.
Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные. За ведущий столбец выберем столбец, соответствующий переменной х1, сравнивания по модулю |-4| >|-1|. Выделим его в таблице 2.
Затем элементы столбца свободных членов симплексной таблицы делим на положительные элементы ведущего столбца