ЛР3

Цель работы: Решить задачу линейного программирования симплексметодом.

Ход работы:

Условие задачи:

При откорме каждое животное должно получать не менее 9 ед. белков, 7 ед. углеводов и 13 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:

Стоимость 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, 4, 5 со знаками «-». В результате неравенства преобразуются в строгие равенства.

Так как текущее базисное решение не оптимально (ОКЦФ >0), то сформируем новую симплекс-таблицу и перейдем к новому базисному решению.

1 итерация.

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

Max(| −9| ; | − 7|; |-13| ) = |-13|, значит генеральная строка – х5.

В этой строке так же находим максимальный по модулю отрицательный элемент, который будет разрешающим (ведущим) столбцом.

Max(| −1| ; | − 6|; |0|; |0|;|1| ) = |-6|, значит генеральный столбец – x2

Так как среди свободных членов Bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным. Вместо переменной x5 следует ввести переменную x2.

Итак, генеральный элемент x2x2= -6.

Следующий этап – формирование новой генеральной строки. Для этого необходимо все элементы генеральной строки разделить на генеральный элемент. В результате чего генеральный элемент равен 1 (таблица 2).

−13 х2 = −6 = 2,1666

−1 х2 1 = −6 = 0,1666

−6 х2 2 = −6 = 1

0 х2 3 = −6 = 0

0 х2 4 = −6 = 0

1 х2 5 = −6 = −0,1666

Заполняем все остальные строк, согласно алгоритму: из элемента старой строки вычитается произведение элемента новой генеральной строки на соответствующий элемент генерального столбца.

х3 = −9 − 2,1666 (−2) = −4,666

х3 1 = −3 − 0,1666 (−2) = −2,666

х3 2 = −2 − 1 (−2) = 0

х3 3 = 1 − 0 (−2) = 1

х3 4 = 0 − 0 (−2) = 0

х3 5 = 0 − (−0,1666) (−2) = −0,333

х4 = −7 − 2,1666 (−4) = 1,666

х4 1 = −1 − 0,1666 (−4) = −0,333

х4 2 = −4 − 1 (−4) = 0

х4 3 = 0 − 0 (−4) = 0

х4 4 = 1 − 0 (−4) = 1

х4 5 = 0 − (−0,1666) (−4) = −0,666

ОКЦФ; 1 = 4 − 0,666 8 = 2,666

ОКЦФ; 2 = 8 − 1 8 = 0

ОКЦФ; 3 = 0 − 0 8 = 0

ОКЦФ; 4 = 0 − 0 8 = 0

ОКЦФ; 5 = 0 − 0,1666 8 = −1,333

Найденное базисное решение не оптимально, так как в строке ОКЦФ присутствует положительный результат (2,666).

2 итерация:

Находим снова генеральный столбец и генеральную строку таблицы 3.

Max(|-4,666|; |-1,666|; |2,1666|) = |-4,666|, значит генеральная строка – х3.

Max(|-2,666|; |0|; |1|; |0|; |-0,333|) = |-2,666|, значит генеральный столбец – х1.

Вместо переменной x3 следует ввести переменную x1.

Генеральный элемент равен х1х1= -2,666.

Следующий этап – формирование новой генеральной строки. Для этого необходимо все элементы генеральной строки разделить на генеральный элемент. В результате чего генеральный элемент равен 1 (таблица 4).

−4,666 х1 = −2,666 = 1,75

−2,666 х1 1 = −2,666 = 1

0 х1 2 = −2,666 = 0

1 х1 3 = −2,666 = −0,375

0 х1 4 = −2,666 = 0

−0,333 х1 5 = −2,666 = 0,125

Заполняем все остальные строк, согласно алгоритму: из элемента старой строки вычитается произведение элемента новой генеральной строки на соответствующий элемент генерального столбца.

Базисные переменные, соответствующие остальным строкам, остаются без изменений.

х2 = 2,1666 − 1,75 0,1666 = 1,875

х2 1 = 0,1666 − 1 0,1666 = 0

х2 2 = 1 − 0 0,1666 = 1

х2 3 = 0 − (−0,375) 0,1666 = 0,0625

х2 4 = 0 − 0 0,1666 = 0

х2 5 = 0 − 0,125 0,1666 = 0,1875

х4 = 1,666 − 1,75 (−0,333) = 2,25

х4 1 = −0,333 − 1 (−0,333) = 0

х4 2 = 0 − 0 (−0,333) = 0

х4 3 = 0 − (−0,375) (−0,333) = −0,125

х4 4 = 1 − 0 (−0,333) = 1

х4 5 = 0,666 − 0,125 (−0,333) = −0,625

ОКЦФ; 1 = 2,666 − 1 2,666 = 0

ОКЦФ; 2 = 0 − 0 2,666 = 0

ОКЦФ; 3 = 0 − 0,375 2,666 = −0,999

ОКЦФ; 4 = 0 − 0 2,666 = 0

ОКЦФ; 5 = −1,333 − 0,125 2,666 = −1,666

Найденное базисное решение оптимально, так как в строке ОКЦФ отсутствует положительный результат.

Найдем значение ЦФ в данном базисном решении:

F(1,75 ; 1,875 ; 0; 2,25; 0) = 1,75*4 + 1,875*8 + 0*0+ 2,25*0 + 0*0= 22

Ответ: чтобы обеспечить минимум затрат (22 ед. в день), необходимо дневной рацион составить из 1,75 кг корма 1 и 1,875 кг корма 2.

Сравнение графического метода решения ЗЛП и симплексного метода

На лабораторной №2 было найдено решение данной задачи графическим методом (рисунок 1).

Рисунок 1. График прямых с ОДЗ и вектором целевой функции в Excel

(1,75 ; 1,875) – координата точки В.

Подставляем координаты в линейную функцию:

= 4 1 + 8 2 →

Z=4*1,75+8*1,875=22

Таким образом, при решении одной и той же задачи разными методами, мы получили одинаковый ответ. Это значит, что оба метода решения позволяют находить точные и верные оптимальные решения для ЗЛП.

Вывод: была решена задача линейного программирования симплексметодом.