 |
Решение задачи Симплекс методом
|
|
|
|
Задача
В ресторане изготавливают 2 коктейля с использование апельсинового сока и Campari (вермут). Менеджер ресторана считает, что за неделю в ресторане может быть реализовано до 150 порций коктейля: для приготовления 1-ого коктейля под названием «Campari Orange» (апельсиновый сок, Campari) требуется около 100 мл. апельсинового сока и 150 мл. Campari, а для приготовления 2-ого коктейля под названием «Шот коктейль» (апельсиновый сок, Campari, сок лимона, мятный сироп) требуется около 200 мл. апельсинового сока и 100 мл. Campari. Ресторан может получать до 20 литров сока в неделю, и не меньше 3 литров Campari (для того чтобы поставщики продолжали сотрудничать с нашим рестораном необходимо заказывать не меньше 3 литров Campari).
Если прибыль от продажи «Campari Orange» составляет 3 у.е., а от «Шот коктейль»- 4 у.е.
Вопрос: Сколько коктейлей каждого вида следует произвести в неделю?
Данная задача придумана на основе практической деятельности. Все данные являются действительными.
Математическая постановка
X1 – кол-во коктейля «Campari Orange»
X2 – кол-во коктейля «Шот коктейль»
F(x) = 3X1+4X2 => max
Ограничительные условия:
X1+X2 
150
0.1X1+0.2 X2 20
0.15X1+0.1 X2 
3
X1 0, X2 0
Решение задачи Графическим способом
X1+X2 150
0.1X1+0.2 X2 20
0.15X1+0.1 X2 3
X1 0, X2 0
Заменим знаки неравенства на знаки равенства, построим прямые соответствующие уравнениям.
1. Построение границы 1
X1+X2 =150 – прямая линия
| X1 | ||
| X2 |
2. Построение границы 2
0.1X1+0.2 X2 =20 – прямая линия
| X1 | ||
| X2 |
3. Построение границы 3
0.15X1+0.1X2 =3 – прямая линия
| X1 | ||
| X2 |
|
|
|
Многоугольник ABDCE является областью допустимых решений этой задачи.
Построим линию уровня целевой функции
F(x) = 3X1+4X2 =0
| X1 | ||
| X2 | -30 |
Построим градиент, вектор, направление которого покажет max. скорость роста этой функции.
g (3; -4)
Передвинем линию уровня целевой функции в направлении градиента
Координаты точки E- оптимальный план
Точка В получена пересечением 1 и 2 границы
X1+X2 =150
0.1X1+0.2 X2 =20
Выразим X1
X1= 150- X2
0.1*(150- X2)+ 0.2 X2 =20
(0.1*150)-0.1X2 +0.2 X2 =20
15+0.1X2 =20
X2 =50
Подставляем X2 в одно из уравнений
X1 +50=150
X1 =100
X1 =100
X2 =50
F(x*)=100*3+50*4=300+200=500
Ответ: оптимальный план X1 =100, X2 =50. Max. значение функции 500
Решение задачи с помощью MathCAD
Решение задачи Симплекс методом
F= 3X1+4X2 => max
X1+X2 150
0.1X1+0.2 X2 20
0.15X1+0.1 X2 3
X1,…X2>0
Приведем системe ограничений к каноническому виду, путем введения неотрицательных переменных и затем преобразуем неравенство в равенство.
x1 + x2 + x3 = 150
0.1 x1 + 0.2 x2 + x4 = 20
0.15 x1 + 0.1 x2 - x5 = 3
В уравнении 3 нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную R1
F= 3X1+4X2 -MR1
x1 + x2 + x3 = 150
0.1 x1 + 0.2 x2 + x4 = 20
0.15 x1 + 0.1 x2 - x5 + R1 = 3
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | R1 | П | q |
| x3 | |||||||||
| x4 | 1/10 | 1/5 | |||||||
| R1 | 3/20 | 1/10 | -1 | ||||||
| F | -3 | -4 | - | ||||||
| оценка | -1 | -2/3 | -1 | - | - |
Разделим элементы строки 3 на 3/20
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | R1 | П | q |
| x3 | |||||||||
| x4 | 1/10 | 1/5 | |||||||
| R1 | 2/3 | -20/3 | 20/3 | ||||||
| F | -3 | -4 | - | ||||||
| оценка | -1 | -2/3 | 20/3 | -20/3 | - | - |
От элементов строки 1 отнимает соответствующие элементы строки 3.
|
|
|
От элементов строки 2 отнимает соответствующие элементы строки 3, умноженные на 0.1.
От элементов строки L отнимает соответствующие элементы строки 3, умноженные на -3.
От элементов строки W отнимает соответствующие элементы строки 3, умноженные на -3/20.
Элементы столбца r1 можно не пересчитывать, так как переменная r1 больше не является базисной
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/3 | 20/3 | - | |||||
| x4 | 2/15 | 2/3 | - | |||||
| х1 | 2/3 | -20/3 | - | |||||
| F | -2 | -20 | - |
За ведущий выберем столбец 5, так как -20 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.
За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 5.
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/3 | 20/3 | 39/2 | |||||
| x4 | 2/15 | 2/3 | ||||||
| х1 | 2/3 | -20/3 | - | |||||
| F | -2 | -20 | - |
Разделим элементы строки 1 на 20/3
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/20 | 3/20 | 39/2 | 39/2 | ||||
| x4 | 2/15 | 2/3 | ||||||
| х1 | 2/3 | -20/3 | - | |||||
| F | -2 | -20 | - |
От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 2/3.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на -20/3.
От элементов строки L отнимает соответствующие элементы строки 1, умноженные на -20.
За ведущий выберем столбец 2, так как -1 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.
За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/20 | 3/20 | 39/2 | |||||
| x4 | 1/10 | -1/10 | ||||||
| х1 | ||||||||
| F | -1 | - |
|
|
|
Разделим элементы строки 2 на 1/10
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/20 | 3/20 | 39/2 | |||||
| x4 | -1 | |||||||
| х1 | ||||||||
| F | -1 | - |
От элементов строки 1 отнимает соответствующие элементы строки 2.
От элементов строки 3 отнимает соответствующие элементы строки 2.
От элементов строки L отнимает соответствующие элементы строки 2, умноженные на -1.
| Ц | Базис | x1 | x2 | x3 | x4 | x5 | П | q |
| x3 | 1/5 | -1/2 | - | |||||
| x2 | -1 | - | ||||||
| х1 | -10 | - | ||||||
| F | - |
|
|
|
