Контрольное задание № 4.
Решение задач линейного программирования Симплекс-методом.
Условие задачи.
Предприятие производит 3 вида продукции: А1, А2, А3, используя сырье двух видов: В1 и В2. Известны затраты i – го вида на единицу изделия g – го вида aig, количества сырья каждого вида bi (i=1,2), а так же прибыль, полученная от единицы изделия g-го вида cg (g=1,2,3).
1) Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
2) Сколько изделий каждого вида необходимо произвести, чтобы получить максимум товарной продукции?
3) Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли при условии, что необходимо выполнить план выпуска?
X вариант
| Матрица затрат сырья i – го вида на единицу продукции g – го вида A=(aig)
|
| Сырье
| Виды продукции
| Количество сырья
|
| А1
| А2
| А3
|
| В1
|
|
|
|
|
| В2
|
|
|
|
|
| Прибыль от единицы каждого изделия (с1, с2, с3)
|
|
|
|
|
| План выпуска
|
|
|
|
|
Решение задачи.
1) Найдем количество изделий каждого вида, которые нужно произвести для того, чтобы получить максимум прибыли.
|
|
|
|
|
|
|
|
| Найдем наибольшее значение функции прибыли
|
| | | | | | | | | |
| при следующих ограничениях
|
|
|
| x1
| +
|
| x2
| +
|
| x3
| 
|
|
|
|
| x1
| +
|
| x2
| +
|
| x3
|
|
|
|
|
|
| x1
| +
|
| x2
| +
|
| x3
| +
|
| S1
|
|
|
| =
|
|
|
|
| x1
| +
|
| x2
| +
|
| x3
|
|
|
| +
|
| S2
| =
|
|
S1  0 S2 0
|
| Введенные нами переменные S1, S2, называются балансовыми переменными.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
| отношение
|
| | | | | | | | |
| | | | | | | | |
| L
| | | | | | |
|
|
| Разделим элементы строки 1 на 2.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
|
| | | | | | | |
| | | | | | | |
| L
| | | | | | |
| | | | | | | | | |
| От элементов строки 2 вычитаем соответствующие элементы строки 1.
|
| К элементам строки L прибавим соответствующие элементы строки 1, умноженные на 2.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
|
| | | | | | | |
| | | | | | | |
| L
| | | | | | |
| X
| 1
| =
| (
| 0,
| 0,
| 1050,
| 0,
|
| )
|
| L (X 1) = 2100.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
| отношение
|
| | | | | | | | |
| | | | | | | | |
| L
| | | | | | |
|
|
| Разделим элементы строки 2 на 3/2.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
|
| | | | | | | |
| | | | | | | |
| L
| | | | | | |
|
| От элементов строки 1 вычитаем соответствующие элементы строки 2, умноженные на 1/2.
|
|
| К элементам строки L прибавим соответствующие элементы строки 2, умноженные на 2.
|
| | x1
| x2
| x3
| S1
| S2
| свободные члены
|
|
| | | | | | | |
|
| | | | | | | |
|
| L
| | | | | | |
|
| | | | | | | | | | | | | | | | | |
| X
| 2
| =
| (
| 0,
| 100,
| 1000,
| 0,
|
| )
|
| L
| =
|
| | -1/3
| x1
| | -1/3
| S1
| | -4/3
| S2
|
| Сейчас x1=0.
| | Если увеличим значение x1, то значение функции L 
|
| Сейчас S1=0.
| | Если увеличим значение S1, то значение функции L
|
| Сейчас S2=0.
| | Если увеличим значение S2, то значение функции L
|
| Больше не удастся увеличить значение функции L.
|
| Ответ 1):
|
| x1 = 0 x2 = 100 x3 = 1000
|
2) Найдем количество изделий каждого вида, которые нужно произвести для того, чтобы получить максимум товарной продукции.
Найдем значения переменных x1, x2,x3, при которых функция товарной продукции:
принимает максимальное значение, при условии следующих ограничений:
| |
| x1
| +
| | x2
| +
|
| x3
| ≤
| |
| | (1)
|
| |
| x1
| +
|
| x2
| +
| | x3
| ≤
| |
| | (2)
|
x1, x2, x3 ≥ 0
| |
| x1
| +
| | x2
| +
|
| x3
| +
| | s1
| | | | =
| |
| | (1)
|
| |
| x1
| +
|
| x2
| +
| | x3
| | | | +
| | s2
| =
| |
| | (2)
|
x1, x2, x3, s1, s2 ≥ 0
Начальная симплекс-таблица
| БП
| x1
| x2
| x3
| s1
| s2
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
| |
| s2
|
|
|
|
|
|
| |
| Q
|
|
|
|
|
|
| --
|
| БП
| x1
| x2
| x3
| s1
| s2
| Решение
| Отношение
|
| x3
|
| |
| |
|
| |
| s2
|
| |
| |
|
| |
| Q
|
| |
| |
| -1050
| --
|
| БП
| x1
| x2
| x3
| s1
| s2
| Решение
| Отношение
|
| x3
| |
|
| | |
| --
|
| x2
| |
|
| | |
| --
|
| Q
| |
|
| | | -1100
| --
|
Ответ 2): Максимальное значение функции Q(x)=1100 достигается при:
3) Найдем количество изделий каждого вида, которые нужно произвести для того, чтобы получить максимум прибыли при условии, что необходимо выполнить план выпуска.
Найти значения переменных x1, x2,x3, при которых функция прибыли:
принимает максимальное значение, при условии следующих ограничений:
| |
| x1
| +
| | x2
| +
|
| x3
| ≤
| |
| | (1)
|
| |
| x1
| +
|
| x2
| +
| | x3
| ≤
| |
| | (2)
|
| | | x1
| | | | | | | =
| |
| | (3)
|
| | | | | | x2
| | | | =
| |
| | (4)
|
| | | | | | | | | x3
| =
| |
| | (5)
|
x1, x2, x3 ≥ 0
| |
| x1
| +
| | x2
| +
|
| x3
| +
| | s1
| | | | =
| |
| | (1)
|
| |
| x1
| +
|
| x2
| +
| | x3
| | | | +
| | s2
| =
| |
| | (2)
|
| | | x1
| | | | | | | | | | | | | =
| |
| | (3)
|
| | | | | | x2
| | | | | | | | | | =
| |
| | (4)
|
| | | | | | | | | x3
| | | | | | | =
| |
| | (5)
|
x1, x2, x3, s1, s2 ≥ 0
Ищем в системе ограничений базисные переменные.
Из последней системы ограничений можно выделить базисные переменные s1,s2.
Не все уравнения содержат базисные переменные, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Такое решение еще называют решением с искусственным базисом.
Введем в уравнения 3, 4, 5 искусственные неотрицательные переменные r1, r2, r3.
Получим следующую систему ограничений,
| |
| x1
| +
| | x2
| +
|
| x3
| +
| | s1
| | | | | | | | | | | | | =
| |
| | (1)
|
| |
| x1
| +
|
| x2
| +
| | x3
| | | | +
| | s2
| | | | | | | | | | =
| |
| | (2)
|
| | | x1
| | | | | | | | | | | | | +
| | r1
| | | | | | | =
| |
| | (3)
|
| | | | | | x2
| | | | | | | | | | | | | +
| | r2
| | | | =
| |
| | (4)
|
| | | | | | | | | x3
| | | | | | | | | | | | | +
| | r3
| =
| |
| | (5)
|
x1, x2, x3, s1, s2, r1, r2, r3 ≥ 0
с базисными переменными s1,s2,r1,r2,r3.
Целью решения вспомогательной задачи является получение допустимого базисного решения, не содержащего искусственных переменных (r1,r2,r3). Для этого сформируем вспомогательную целевую функцию:
и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит, исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.
Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:
- вычтем из функции G уравнение 3
- вычтем из функции G уравнение 4
- вычтем из функции G уравнение 5
Функция G примет вид:
Теперь мы можем сформировать начальную симплекс-таблицу.
Начальная симплекс-таблица
| БП
| x1
| x2
| x3
| s1
| s2
| r1
| r2
| r3
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
|
|
|
| |
| s2
|
|
|
|
|
|
|
|
|
| |
| r1
|
|
|
|
|
|
|
|
|
| --
|
| r2
|
|
|
|
|
|
|
|
|
| --
|
| r3
|
|
|
|
|
|
|
|
|
| |
| W
|
|
|
|
|
|
|
|
|
| --
|
| G
| -1
| -1
| -1
|
|
|
|
|
| -900
| --
|
| БП
| x1
| x2
| x3
| s1
| s2
| r1
| r2
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
|
|
| |
| s2
|
|
|
|
|
|
|
|
| |
| r1
|
|
|
|
|
|
|
|
| --
|
| r2
|
|
|
|
|
|
|
|
| |
| x3
|
|
|
|
|
|
|
|
| --
|
| W
|
|
|
|
|
|
|
| -1200
| --
|
| G
| -1
| -1
|
|
|
|
|
| -300
| --
|
| БП
| x1
| x2
| x3
| s1
| s2
| r1
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
|
| |
| s2
|
|
|
|
|
|
|
| |
| r1
|
|
|
|
|
|
|
| |
| x2
|
|
|
|
|
|
|
| --
|
| x3
|
|
|
|
|
|
|
| --
|
| W
|
|
|
|
|
|
| -1500
| --
|
| G
| -1
|
|
|
|
|
| -200
| --
|
| БП
| x1
| x2
| x3
| s1
| s2
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
| --
|
| s2
|
|
|
|
|
|
| --
|
| x1
|
|
|
|
|
|
| --
|
| x2
|
|
|
|
|
|
| --
|
| x3
|
|
|
|
|
|
| --
|
| W
|
|
|
|
|
| -2100
| --
|
| G
|
|
|
|
|
|
| --
|
Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Строка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "W"
| БП
| x1
| x2
| x3
| s1
| s2
| Решение
| Отношение
|
| s1
|
|
|
|
|
|
| --
|
| s2
|
|
|
|
|
|
| --
|
| x1
|
|
|
|
|
|
| --
|
| x2
|
|
|
|
|
|
| --
|
| x3
|
|
|
|
|
|
| --
|
| W
|
|
|
|
|
| -2100
| --
|
Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.
Ответ 3):
| Максимальное значение функции прибыли W(x)=
|
|
достигается при:
