Фирма имеет возможность приобрести не более 15 трехтонных автомашин и не более 22 пятитонных. Отпускная цена трехтонного грузовика – 14000 руб., пятитонного – 25000 руб. Фирма может выделить для приобретения автомашин 218 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Решение
X1 +5x2 при следующих условиях ограничений:
14000 x1 + 25000 x2 <=21800
x1 <= 15
x2 <= 22
Для построения первого опорного плана систему неравенств приведем к каноническому виду путем введения дополнительных переменных. Так как в неравенствах <=, то переменная вводится со знаком:
14000 x1 + 25000 x2 + 1x3 +9x4 + 0x5 =218000
x1 + 0x3 + 1x4 + 0x5 = 15
x2 + 0x3 + 0x4 + 1x5 = 22
x3 , x4 , x5 – базисные переменные (входят только в одно уравнение системы ограничений и притом с единичным коэффициентом). х1, x2 – свободные переменные. Предположим, что они равны 0 и получаем первый опорный план:
х1 = 0, х2 = 0, х3 = 218000, х4 = 15, х5 = 22.
Чтобы произвести расчеты, запишем задачу в табличном виде. При этом необходимо изменить направленность целевой функции (с мах на мin.)
переменные Х1 Х2 Х3 Х4 Х5 Свободный член
Х3 14000 25000 1 0 0 218000
Х4 1 0 0 1 0 15
Х5 0 1 0 0 1 22
Индексная
строка -3 -5 0
Так как в целевой функции есть отрицательные значения, опорный план не является оптимальным, и его необходимо преобразовать. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
1
. Определим ведущую строку и столбец. Поскольку задача решается на минимум, то ведущий столбец выбирают по максимальному по модулю отрицательному числу и индексной строке (это столбец Х2).
Ведущей строкой будет та, у которой частное от деления свободного члена на значение строки будет минимальным (218000/25000 = 15,6; 22/1 = 22). Минимальное значение представлено в строке Х3, она и будет ведущей. На пересечении ведущего столбца и строки стоит число 2500, оно и будет разрешающим элементом. Обозначение ведущей строки меняется на обозначение ведущего столбца (X3 на X2).
переменные Х1 Х2 Х3 Х4 Х5 Свободный член
Х2 14000 25000 1 0 0 218000
Х4 1 0 0 1 0 15
Х5 0 1 0 0 1 22
Индексная
строка -3 -5 0 0 0
2. Формируем следующую симплексную таблицу, исходя из правил:
- Делим ведущую строку на разрешающий элемент. В клетках ведущего столбца (за исключением той, где находится разрешающий элемент) ставим нули.
- Значения остальных клеток нового плана рассчитываем по правилу прямоугольника: В исходной таблице выделяем прямоугольник, вершинами которого служат нужные для вычисления элементы