Задача линейного программирования: нахождение оптимального плана

 

 

2 Практическая часть 

2.1 Построение математической модели задачи 

     Фирма рекламирует свою продукцию через 4 СМИ:

     1) Телевидение

     2) Радио

     3) Газеты

     4) Афиши

     Пусть х₁ –это телевидение, х₂ – радио, х₃ – газеты и х₄ – афиши.

     Тогда увеличение прибыли от использования всех 4 видов СМИ будет записан как целевая функция:

     F(x)=11 х₁+3 х₂+7 х₃+4 х₄ →max    

     Составим  ограничения:

По  распределению полного рекламного бюджета:

     1 х₁+1 х₂+ 1 х₃+1 х₄≤500000      

     По  распределению рекламного бюджета на телевидение:

     х₁≤200000       

По  распределению рекламного бюджета  на афиши:

     1 х₄≤100000          

По  распределению рекламного бюджета  на радио

1 x₂≥100000

Неотрицательности:

     х₁, х_2, x_3, x₄≥0       

     Таким образом, модель задачи имеет вид:

     F(x)= 11 х₁+3 х₂+7 х₃+4 х₄ →max     
 
 

2.3 Решение задачи симплекс методом на максимум 

     Приведем  математическую модель к канонической форме:

     F(x)= 11 х₁+3 х₂+7 х₃+4 х₄+0* х₅+0* х₆+0* х₇+0* х₈+y₁ →max 
 

     Выберем в качестве базисных переменных х₅, х₆, x₇ y₁ Остальные х₁, х₂, x₃, x₄ являются небазисными. 
 

     Заполнение  симплексной таблицы, в таблице 2 будет расписана «нулевая» итерация. 

     Таблица 2 – Итерация 0

 

     В базис записываются базисные переменные (х₅, х_6, х₇ y₁). В столбик С коэффициенты базисных переменных из целевой функции. В столбике В – свободные числа (правые числа ограничений). Над переменными х_1, x₂, х₃, х₄, x₈, расположены коэффициенты этих переменных из целевой функции. Под этими двумя переменными записаны коэффициенты из ограничений при этих переменных. В нижней строке записана целевая функция и относительные оценки всех переменных.

     Расчет  целевой функции:

     -100000М=-1*0+0*500000+0*200000+0*100000+(-M)*100000

     Расчет  относительных оценок:

     -10=-1*10+0*1+0*1+0*0+(-M)*0

     -M-3=-1*3+0*1+0*0+0*0+(-M)*1

     -7=-1*7+0*1+0*0+0*0+(-М)*0

     -4=-1*4+0*1+0*0+0*1+(-М)*0

     М=-1*0+0*0+0*0+0*0+(-М)*(-1)

     Так как минус –M-3 по модулю больше чем минус -10, -7, -4 и М поэтому столбик с переменной х₂ является главным.

     Для того чтобы найти главную строку надо числа столбца В разделить на соответствующие им коэффициенты главного столбика.

     500000=500000/1

     100000=100000/1

     Наименьшим  числом является 100000. Поэтому главной строкой является строка с переменной y₁. Главный элемент равен 1.

     Строим  новую таблицу 3, в которой будет итерация 1. Для того чтобы пересчитать таблицу, сначала надо х₂ переместить в базис, а y₁ – уходит из нашей таблицы. 

     Таблица 3 – Итерация 1

 

     Вместо  главного элемента записывается 1, а  для пересчета главной строки, её надо разделить на главный элемент.

     0=0/1

     0=0/1

     0=0/1

     -1=-1/1

     100000=100000/1

     Главный столбец убирается из нашей таблицы.

     А остальные ячейки вычисляются по правилу прямоугольника.

     400000=500000*1-1*100000

     1=1*0-(-1)*1

     Расчет  целевой функции:

     300000=0*400000+0*200000+0*100000+3*100000

     Расчет  относительных оценок:

     -10=-1*10+0*1+0*1+0*0+3*0

     -7=-1*7+0*1+0*0+0*0+3*0

     -4=-1*4+0*1+0*0+0*1+3*0

     -3=-1*0+0*1+0*0+0*0+3*(-1)

     Так как -10 является самой отрицательной относительной оценкой, то столбик с переменной х₁ является главным.

     Для того чтобы найти главную строку надо числа столбца В разделить на соответствующие им коэффициенты главного столбика.

     400000=400000/1

     100000=100000/1

     Наименьшим  числом является 100000. Поэтому главной строкой является строка с переменной х₆. Главный элемент равен 1.

     Строим  новую таблицу 4, где будет итерация 2. Для того чтобы пересчитать таблицу, сначала надо х₁ переместить в базис, а х₆ – переходит на его место. 

     Таблица 4 – Итерация 2

 

     Вместо  главного элемента записывается 1, а  для пересчета главной строки, её надо разделить на главный элемент

     200000=200000/1

     Главный столбец делится на минул главный элемент.

     -1=1/-1

     А остальные ячейки вычисляются по правилу прямоугольника.

     200000=400000*1-200000*1

     Расчет  целевой функции:

     2300000=-1*0+0*200000+10*200000+0*100000+3*100000

     Расчет  относительных оценок:

     10=-1*0+0*(-1)+10*1+0*0+3*0

     -7=-1*7+0*1+10*0+0*0+3*0

     -4=-1*4+0*1+10*0+0*1+3*0

     -3=-1*0+0*1+10*0+0*0+3*(-1)

     Наименьшим  числом является -7, поэтому главным столбцом является столбик с переменной х₃.

     Для того чтобы найти главную строку надо числа столбца В разделить на соответствующие им коэффициенты главного столбика.

     200000=200000/1

     Наименьшим  числом является 200000.Поэтому главной строкой является строка с переменной х₅. Главный элемент равен 1.

     Строим  новую таблицу 5, где будет итерация 3. Для того чтобы пересчитать таблицу, сначала надо х₃ переместить в базис, а х₅ – переходит на место х₃.

     Таблица 5 – итерация 3