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