Лабораторная работа № 5 Симплексный метод решения задач линейного программирования

Цель: освоение методов оптимизации производственных процессов.

Задачи: На основании заданных параметров производственных ситуаций решить экономико-математические модели задач симплекс- методом.

Задание.

Ателье занимается пошивом двух видов изделия: пальто и плащи.

Для пошива пальто требуется затратить а₁ кг сырья первого типа, а₂ кг сырья второго типа, а₃ кг сырья третьего типа.

Для пошива плаща требуется затратить а₄ кг сырья первого типа, а₅ кг сырья второго типа, а₆ кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b₁ кг, b₂ кг, b₃ кг соответственно.

Рыночная цена пальто составляет с₁ тыс. руб., а плаща - с₂ тыс.руб.

1) Построить экономико-математическую модель задачи; составить план пошива изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.

2) Составить план пошива изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс-метода решения задачи линейного программирования.

3) Составить план пошива изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде МS Ехсеl.

Пример

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=2	а4=7	b1=560	с1=55
а2=3	а5=3	b2=300	с2=35
а3=5	а6=1	b3=332

1) Математическая модель задачи

Целевая функция F(x₁;x₂)=55x₁+35x₂

Ограничения:

по расходу сырья 1: 2x₁+7x₂  560

по расходу сырья 2: 3x₁+3x₂  300

по расходу сырья 3: 5x₁+x₂  332

не отрицательность количества выпускаемых изделий:

x₁  0

x₂  0

Математическая модель:

F(x₁;x₂)=55x₁+35x_{2 } max

2x₁+7x₂  560

3x₁+3x₂  300

5x₁+x₂  332

x₁  0

x₂  0

2. Графический метод решения задачи

Ответ: пальто необходимо выпускать в количестве 58 шт., плащей в количестве 42 шт. При этом прибыль от их реализации максимальная и составит 4660 тыс. руб.

3. Симплекс-метод решения задачи

1) Сформируем модель задачи:

Переменные величины:

х₁ – пальто, шт.

х₂ – плащ, шт.

Ограничения:

по расходу сырья 1: 2x₁+7x₂  560

по расходу сырья 2: 3x₁+3x₂  300

по расходу сырья 3: 5x₁+x₂  332

не отрицательность количества выпускаемых изделий:

x₁  0

x₂  0

Целевая функция, тыс. руб.

F(x₁;x₂)=55x₁+35x_{2 } max

2) Приведем задачу к каноническому виду, для этого в каждое неравенство вводим дополнительную переменную со знаком плюс: х₃, х₄, х₅

F(x₁;x₂)=55x₁+35x_{2 } max

2 x₁+7x₂ = 560

3x₁+3x₂ = 300

5x₁+x₂ =332

x₁  0

x₂  0

тогда,

F(x₁;x₂)=55x₁+35x₂ +0х₃+0х₄₊0х_5 max

где

х₃ – неиспользованное сырье 1, кг

х₄ – неиспользованное сырье 2, кг

х₅ – неиспользованное сырье 3, кг

Найдем первый опорный план, т.е. первое базисное решение. Для выбора опорного плана запишем матрицу:

х₁ х₂ х₃ х₄ х₅ b₁

1 ограничение 2 7 1 0 0 560

2 ограничение 3 3 0 1 0 300

3 ограничение 5 1 0 0 1 332

Переменные, которые образовали определитель единицы и вошли в базис называются базисными. Это х₃ = 560, х₄ = 300, х₅ = 332.

Переменные, не вошедшие в базис, называют свободными и они всегда равны 0. Это х₁=0, х₂=0.

Подставим полученные значения в функцию

F(x₁;x₂)=55*0 + 35*0 + 0*560 + 0*300 + 0*332=0

3) Запишем первый опорный план задачи в симплексной таблице:

Таблица 1 – Первая симплекс-таблица

БП	СП	Значения БП	х1	х2	х3	х4	х5	Оценочные отношения	Коэффициент
х3	0	560	2	7	1	0	0	280	0,4
х4	0	300	3	3	0	1	0	100	0,6
х5	0	332	5	1	0	0	1	66,4
	Fmax	0	-55	-35	0	0	0

Так как задача на нахождение max значения, то в индексной строке выберем наибольшую по модулю отрицательную оценку (-55) – это столбец с переменной х₁ (таблица 1). Выделяем его. Это разрешающий столбец.

Затем находим оценочные отношения: путем деления столбца «Значение БП» на столбец «х₁»: 560/2 = 280, 300/3 = 100, 332/5 = 66,4 и записываем полученные результаты в столбец «Оценочные отношения». Выбираем из данного столбца наименьшее значение – 66,4, т.к. это значение расположено в третьей строке – выделяем её. Это разрешающая строка.

В последнем столбце «Коэффициент» записываем пересчитывающие коэффициенты: 2/5 = 0,4, 3/5 = 0,6, которые необходимы при пересчете всех невыделенных элементов.

Разрешающую строку делим на 5 (5 – разрешающий элемент, т.к. он попадает на пересечение разрешающей строки с разрешающим столбцом):

332/5 = 166;

5/5 = 1;

1/5 = 0,2;

0/5 = 0;

0/5 = 0;

1/5 = 0,2.

Из базиса выводим х₅ и вводим х_1. Все невыделенные элементы пересчитываем по методу Гаусса:

Для первой строки:

560- (332*0,4) = 427,2

2 -(5*0,4) = 0

7 -(1*0,4) = 6,6

1- (0*0,4) = 1

0- (0*0,4) = 0

0- (1*0,4) = -0,4

Для второй строки

300- (332*0,6) = 100,8

3- (5*0,6) = 0

3 - (1*0,6) = 2,4

0- (0*0,6) = 0

1- (0*0,6) = 1

0- (1*0,6) = -0,6

4)Теперь составим 2 симплексную таблицу

Таблица 2 – Вторая симплекс-таблица

БП	СП	Значения БП	х1	х2	х3	х4	х5	Оценочные отношения	Коэффициент
х3	0	427,2	0	6,6	1	0	-0,4	64,727	2,75
х4	0	100,8	0	2,4	0	1	-0,6	42
х1	55	66,4	1	0,2	0	0	0,2	332	0,08
	Fmax	3652	0	-24	0	0	11

Последняя индексная строка «Fmax» пересчитывается по «правилу прямоугольника»:

0-(332*(-55)/5) = 3652

-55 – (-55/5) = 0

-35 –(1*(-55)/5) = -24

0- (0* (-55)/5) = 0

0- (0* (-55)/5) = 0

0-(-55*1)/5) = 11

Так как в индексной строке присутствует отрицательная оценка, то план не оптимален. Требуется улучшение плана. Выделяем столбец с переменной х₂. Это разрешающий столбец. Затем находим оценочные отношения делением столбца «Значение БП» на столбец «х₂»:

427,2/6,6 = 64,727

100,8/2,4 = 42

66,4/0,2 = 332.

Т.к. значение 42 является минимальным, то строка х₄ – разрешающая.

Из базиса выводим х₄ и вводим х_2.

Пересчитывающий коэффициент: 6,6/2,4 = 2,75; 0,2/2,4 = 0,08.

5)Теперь составим 3 симплексную таблицу.

Строку «х₄» делим на 2,4 (таблица 2). Получаем:

100,8/2,4 = 42

0/2,4 = 0

2,4/2,4 = 1

0/2,4 = 0

½,4 = 0,4

-0,6/2,4 = -0,25

Невыделенные элементы пересчитываем:

По строке «х3»:

427,2- (100,8*2,75) = 150

0- (0*2,75) = 0

6,6-(2,4*2,75) = 0

1-(0*2,75) = 1

0- (1*2,75) = -2,75

-0,4- (-0,6*2,75) = 1,25

По строке х₁

66,4-(100,8*0,08) = 58

1-(0*0,08) = 1

0,2-(2,4*0,08) = 0,008

0-(0*0,08) = 0

0-( 1*0,08) = -0,08

0,2- (-0,6*0,08) = 0,248

Таблица 3 – Третья симплекс-таблица

БП	СП	Значения БП	х1	х2	х3	х4	х5	Оценочные отношения	Коэффициент
х3	0	150,6	0	0	1	-2,75	1,25
х2	35	42	0	1	0	0,4	-0,25
х1	55	58	1	0,008	0	-0,08	0,248
	Fmax

Так как в индексной строке все оценки положительные или равны нулю, план оптимален: F (х1;х2)= F(58;42) = 4660.

Задачи для самостоятельного решения

1 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=3	а4=6	b1=660	с1=35
а2=3	а5=3	b2=320	с2=15
а3=4	а6=2	b3=362

2 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=1	а4=8	b1=460	с1=55
а2=6	а5=2	b2=200	с2=35
а3=5	а6=1	b3=532

3 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=5	а4=7	b1=500	с1=65
а2=5	а5=4	b2=400	с2=35
а3=5	а6=2	b3=332

4 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=6	а4=6	b1=560	с1=48
а2=3	а5=3	b2=350	с2=40
а3=4	а6=2	b3=232

5 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=3	а4=6	b1=510	с1=51
а2=2	а5=4	b2=320	с2=32
а3=4	а6=1	b3=340

6 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=4	а4=7	b1=490	с1=48
а2=3	а5=8	b2=314	с2=29
а3=4	а6=1	b3=347

7 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=7	а4=2	b1=514	с1=45
а2=3	а5=3	b2=320	с2=35
а3=1	а6=5	b3=303

8 вариант

Кол-во сырья для пошива пальто, кг пощшива пальто	Кол-во сырья для пошива плаща, кг	Кол-во сырья каждого типа, кг	Рыночная цена изделия, тыс.руб.
а1=6	а4=5	b1=570	с1=57
а2=4	а5=6	b2=310	с2=36
а3=3	а6=2	b3=342