Решить задачу оптимального планирования выпуска продукции симплексным методом при следующих условиях

1. Сформулируем экономико-математическую модель задачи.
Введем неизвестные х1≥0 и х2≥0, соответствующие количествам продукции первого и второго вида, планируемых к производству.
Суммарный расход сырья первого вида будет 6х1 + 3х2;
Суммарный расход сырья второго вида - 5х1 + 10х2;
Суммарный расход сырья третьего вида - 3х1 + 12х2.
Поскольку запасы сырья ограничены, то получаем систему ограничений:
6x1+3x2≤7145x1+10x2≤9103x1+12x2≤948
Целевая функция, соответствующая условиям задачи, будет иметь вид:
Z = 3х1 + 9х2 → max.
2. От общей формы модели переходят к канонической форме путем введения трех дополнительных неизвестных х3, х4 и х5. Дополнительные переменные в ограничениях типа ≤ обозначают недоиспользованные ресурсы. Модель принимает следующий вид:
Z = 3х1 + 9х2 + 0х3 + 0х4 + 0х5 → max
6x1+3x2+x3=7145x1+10x2+x4=9103x1+12x2+x5=948x1≥0,x2≥0,x3≥0, x4≥0, x5≥0
3. Поиск опорного решения и базиса задачи.
Для нахождения опорного решения необходимо основные переменные (переменные, которые были в системе ограничений до приведения ее к каноническому виду, называются основными переменными задачи) приравнять к нулю, тогда дополнительные переменные будут равны соответствующим свободным членам. В нашем примере опорное решение имеет вид:
Хопор={х1=0, х2=0, х3=714, х4=910, х5=948}
Переменные, отличные от нуля в опорном решении называются базисными переменными. Итак, базисными переменными будут
Бх={х3, х4, х5}
4. Построение первой симплексной таблицы.
В литературе существует много способов построения симплексных таблиц (полные и сокращенные) . Мы разберем один из них - способ построения полной симплексной таблицы (табл. 1). Введем следующие обозначения:
I – обозначим номер ограничения;
Бх - базис задачи;
Bi - свободные члены;
Q - симплексное отношение (тета)
На любом этапе задачи базисные переменные всегда равны соответствующим свободным членам. Строки таблицы – это соответствующие коэффициенты при переменных задачи в рассматриваемом ограничении. Последняя строка симплексной таблицы называется С-строка (нижняя, индексная), заполняется по следующему правилу: если задача решается на максимум, то коэффициенты целевой функции заносятся с противоположным знаком, а при решении задачи на минимум знак при коэффициентах не изменяют.
В первой симплексной таблице значение целевой функции равно 0, т. к. значение основных переменных равно 0.
Таблица 1
Первая симплексная таблица
Базис B x1 x2 x3 x4 x5
x3 714 6 3 1 0 0
x4 910 5 10 0 1 0
x5 948 3 12 0 0 1
F(X0) 0 -3 -9 0 0 0
5. Проверка плана на оптимальность.
План считается оптимальным при решении задачи на максимум в том случае, если в индексной строке отсутствуют отрицательные коэффициенты.
В нашем случае план не оптимален, следовательно, необходимо переходить к этапу последовательного улучшения плана.
6. Последовательное улучшение плана.
Последовательное улучшение плана сводится к отысканию нового базиса задачи. Для перехода к новому базису из старого удаляется одна из переменных и вместо нее вводится другая из числа свободных.
Чтобы определить какую из переменных надо ввести в базис необходимо найти разрешающий столбец