ЛР№3 Гареева
.pdfФГБОУ ВО
Уфимский Государственный Авиационный Технический Университет
Кафедра АСУ
Отчет по
лабораторной работе №3
«Решение задач линейного программирования симплекс-методом»
по дисциплине «Методы оптимизации»
Вариант 6
Выполнила: ст. гр. ПИ-226 Гареева Диана Радиковна
Проверила: Кондратьева Ольга Владимировна
Уфа 2022
Цель работы: Решить задачу линейного программирования симплексметодом.
Ход работы:
Условие задачи:
При откорме каждое животное должно получать не менее 9 ед. белков, 7 ед. углеводов и 13 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:
Питательные |
Количество единиц питательных веществ на 1 кг |
|
вещества |
корма 1 вида |
корма 2 вида |
Белки |
3 |
2 |
Углеводы |
1 |
4 |
Протеин |
1 |
6 |
Стоимость 1 кг корма первого вида – 4 д.е., второго – 8 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость.
Решение задачи:
Пусть х1 – количество кг 1 корма, х2 - количество кг 2 корма.
Чтобы добиться минимальных затрат на дневной рацион, нужно общую стоимость рациона можно выразить в виде линейной функции:
= 4 1 + 8 2 →
Дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений:
3 1 + 2 2 ≥ 9,1 + 4 2 ≥ 7,1 + 6 2 ≥ 13,1 ≥ 0,
{2 ≥ 0.
Преобразуем задачу в приведенную каноническую форму.
3 1 + 2 2 + 3 = 9,1 + 4 2 + 4 = 7,1 + 6 2 + 5 = 13.
Построим исходную таблицу симплекс-таблицу. Столбцами буду все переменные, присутствующие в математической модели: x1, x2, x3, x4, x5.
В ячейках записываются коэффициенты при этих переменных.
Количество строк соответствуют количеству ресурсов, а в последней строке
– оценки коэффициентов целевой функции.
Базисные |
Свободные |
x1 |
x2 |
x3 |
x4 |
x5 |
переменные |
члены bj |
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
9 |
3 |
2 |
1 |
0 |
0 |
|
|
|
|
|
|
|
x4 |
7 |
1 |
4 |
0 |
1 |
0 |
|
|
|
|
|
|
|
x5 |
13 |
1 |
6 |
0 |
0 |
1 |
|
|
|
|
|
|
|
ОКЦФ |
- |
4 |
8 |
0 |
0 |
0 |
|
|
|
|
|
|
|
Единичной подматрице соответствуют x3, x4, x5 , то есть x3, x4, x5 – базисные переменные, а начальное базисное решение равно :
x3=9, x4=7, x5=13.
Так как текущее базисное решение не оптимально (ОКЦФ >0), то сформируем новую симплекс-таблицу и перейдем к новому базисному решению.
1 итерация.
Найдем генеральный столбец:
Max(4;8)=8, то есть генеральный столбец – х2.
Найдем генеральную строку:
Min( 29 ; 74 ; 136 ) =74 , значит генеральная строка – х4.
Итак, генеральный элемент = 4.
Следующий этап – формирование новой генеральной строки. Для этого необходимо все элементы генеральной строки разделить на генеральный элемент. В результате чего генеральный элемент равен 1.
Заполняем все остальные строк, согласно алгоритму: из элемента старой строки вычитается произведение элемента новой генеральной строки на соответствующий элемент генерального столбца.
Базисные переменные, соответствующие остальным строкам, остаются без изменений.
Базисные |
Свободные |
x1 |
|
x2 |
|
x3 |
x4 |
x5 |
|
|
переменные |
члены bj |
|
|
|
|
|
|
|
|
|
x3 |
9 − 2 1,75= |
3 |
− 2 0,25= 2,5 |
2 − 2 |
1= 0 |
1 − 2 0= 1 |
0 − 2 |
0 − 2 |
0= 0 |
|
|
5,5 |
|
|
|
|
|
|
0,25= -0,5 |
|
|
x1 |
1,75 |
|
|
0,25 |
1 |
|
0 |
0,25 |
|
0 |
x5 |
13 − 6 1,75 |
1 |
− 6 |
0,25= - |
6 − 6 |
1=0 |
0 − 6 0= 0 |
0 − 6 |
1 − 6 |
0=0 |
|
= 2,5 |
0,5 |
|
|
|
|
0,25=-1,5 |
|
|
|
ОКЦФ |
- |
4 |
− 8 |
0,25= 2 |
8 − 8 |
1=0 |
0 − 8 0= 0 |
0 − 8 |
0 − 8 |
0=0 |
|
|
|
|
|
|
|
|
0,25=-2 |
|
|
Найдем значение целевой функции в этом базисном решении. F(1,75 ; 0; 5,5 ; 0; 2,5) = 1,75*4 + 0*8 + 5,5*0 + 0*0+ 2,5*0 = 7
Найденное базисное решение не оптимально, так как в строке ОКЦФ присутствует положительный результат.
2 итерация:
Находим снова генеральный столбец и генеральную строку данной таблицы.
Базисные |
Свободные |
x1 |
x2 |
x3 |
x4 |
x5 |
переменные |
члены bj |
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
5,5 |
2,5 |
0 |
1 |
-0,5 |
0 |
|
|
|
|
|
|
|
x1 |
1,75 |
0,25 |
1 |
0 |
0,25 |
0 |
|
|
|
|
|
|
|
x5 |
2,5 |
-0,5 |
0 |
0 |
-1,5 |
0 |
|
|
|
|
|
|
|
ОКЦФ |
- |
2 |
0 |
0 |
-2 |
0 |
|
|
|
|
|
|
|
Max(2;0;0;-2;0) = 2, значит генеральный столбец – х1.
Min( 5,52,5 ; 1,750,25 ; −0,52,5 ) = -5, значит генеральная строка – х5. Генеральный элемент равен -0,5.
Базисные |
Свободные |
x1 |
x2 |
x3 |
|
x4 |
x5 |
|
переменные |
члены bj |
|
|
|
|
|
|
|
x3 |
5,5 −2,5*(- |
2,5 − 2,5 1 = 0 |
0 − 2,5 0 |
1 − 2,5 0 |
= 1 |
−0,5 − 2,5 |
0 |
− 2,5 0= |
|
5)=18 |
|
= 0 |
|
|
3 = −8 |
0 |
|
x1 |
1,75 − 0,25 |
0,25 − 0,25 1 |
1-0,25*0=1 |
0-0,25*0=0 |
|
0,25- |
0-0,25*0=0 |
|
|
(−5) = −0,5 |
= 0 |
|
|
|
0,25*3=-0,5 |
|
|
x2 |
−5 |
1 |
0 |
0 |
|
3 |
|
0 |
ОКЦФ |
- |
2 − 2 1= 0 |
0 − 2 0=0 |
0 − 2 0=0 |
−2 − 2 |
0 |
− 2 0=0 |
|
|
|
|
|
|
|
3=-8 |
|
|
Найдем значение ЦФ в данном базисном решении:
F(-0,5 ; -5 ; 18;0;0) = -0,5*4 + (-5)*8 + 18*0+ 0*0 + 0*0= -42
Найденное базисное решение оптимально.
Значение ЦФ уменьшилось: на первой итерации 7, а на второй – (-42).
В графическом методе значение целевой функции равнялось 22, а при решении симплекс-методом - -42, т.е. значение уменьшилось.
Вывод: была решена задача линейного программирования симплексметодом.