2.3 Решение задачи планирования производства симплекс-методом
Введем базисные переменные и преобразуем исходную задачу к виду:
Z= 40x1 + 30x2 + 0x3 + 0x4 + 0x5 > max
Решим систему уравнений относительно базисных переменных: x3, x4, x5.
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,240,180,251)
"right">Таблица 2.3.1Итерация № 0
Базис |
Сб |
X1 |
X2 |
X3 |
X4 |
X5 |
Свободные члены |
Отношение |
|
X3 |
0 |
4 |
1 |
1 |
0 |
0 |
240 |
240/4 |
|
X4 |
0 |
2 |
3 |
0 |
1 |
0 |
180 |
180/2 |
|
X5 |
0 |
1 |
5 |
0 |
0 |
1 |
251 |
251/1 |
|
Z |
-40 |
-30 |
0 |
0 |
0 |
0 |
- |
При составлении исходной симплекс таблицы (Табл. 2.3.1), коэффициенты при переменных функции ?? записываются с противоположными знаками, а свободный член со своим знаком.
Сб - вектор, составленный из координат соответствующих базисных переменных.
Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
Ведущий столбец X1, так как -40 - наименьшее отрицательное число.
За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим.
"right">Таблица 2.3.2Разрешающий элемент 4
Базис |
Сб |
X1 |
X2 |
X3 |
X4 |
X5 |
Отношение |
||
X3 |
0 |
4 |
1/4 |
1/4 |
0 |
0 |
60 |
60 |
|
X4 |
0 |
2 |
3 |
0 |
1 |
0 |
180 |
90 |
|
X5 |
0 |
1 |
5 |
0 |
0 |
1 |
251 |
251 |
|
Z |
-40 |
-30 |
0 |
0 |
0 |
0 |
- |
От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 2.
От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на 1.
От элементов строки ?? отнимаем соответствующие элементы строки 1, умноженные на -40 (Табл. 2.3.2)
Заменяем базисную переменную X3 на X1
"right">Таблица 2.3.3Итерация № 1
Базис |
Сб |
X1 |
X2 |
X3 |
X4 |
X5 |
Свободные члены |
Отношение |
|
X1 |
0 |
1 |
0,25 |
0,25 |
0 |
0 |
60 |
240 |
|
X4 |
0 |
0 |
2,5 |
-0,5 |
1 |
0 |
60 |
24 |
|
X5 |
40 |
0 |
4,75 |
-0,25 |
0 |
1 |
191 |
40,21 |
|
Z |
0 |
-20 |
10 |
0 |
0 |
2400 |
0 |
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты (Табл. 2.3.3).
За ведущий выберем столбец 2, так как -20 наименьший элемент в ?? строке.
За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.
Разрешающий элемент 2,5
Разделим элементы строки 2 на 2,5(Табл. 2.3.3).
"right">Таблица 2.3.4
Базис |
Сб |
X1 |
X2 |
X3 |
X4 |
X5 |
Свободные члены |
Отношение |
|
X1 |
0 |
1 |
0,25 |
0,25 |
0 |
0 |
60 |
240 |
|
X4 |
20 |
0 |
1 |
-0,2 |
0,4 |
0 |
24 |
24 |
|
X5 |
40 |
0 |
4,75 |
-0,25 |
0 |
1 |
191 |
40,21 |
|
Z |
0 |
-20 |
10 |
0 |
0 |
2400 |
0 |
От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на 0,25.
От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на 4,75.
От элементов строки ?? отнимаем соответствующие элементы строки 2, умноженные на -20
"right">Таблица 2.3.5
Базис |
Сб |
X1 |
X2 |
X3 |
X4 |
X5 |
Свободные члены |
|
X1 |
0 |
1 |
0 |
0,3 |
-0,1 |
0 |
54 |
|
X2 |
20 |
0 |
1 |
-0,2 |
0,4 |
0 |
24 |
|
X5 |
40 |
0 |
0 |
0,7 |
-1,9 |
1 |
77 |
|
Z |
0 |
0 |
6 |
8 |
0 |
2880 |
X2 = (54, 24, 77, 0, 0)
??(X2) = 40*54 + 30*24 = 2880 (Табл. 2.3.5).
Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом).
- Введение
- 1. теоретическая часть
- 1.1 Определение основных понятий математического моделирования и характеристика этапов создания математической модели
- 1.2 Характеристика типовых задач математического моделирования и подходов к их решению
- 1.3 Определение и характеристика линейного программирования
- 1.4 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования
- 1.5 Основные этапы, особенности и методы решения транспортной задачи
- 2. Практическая часть
- 2.1 Составление математической модели задачи планирования производства
- 2.2 Решение задачи планирования производства геометрическим способом
- 2.3 Решение задачи планирования производства симплекс-методом
- 2.4 Решение задачи планирования производства с помощью табличного процессора MS Excel
- 2.5 Составление математической модели транспортной задачи
- 2.6 Нахождение опорного плана транспортной задачи методом северо-западного угла
- 2.7 Нахождение опорного плана транспортной задачи методом наименьшего элемента
- 2.8 Решение транспортной задачи методом потенциалов
- 2.9 Решение транспортной задачи при помощи табличного процессора Excel
- Заключение
- 1.1. Математическое моделирование и численные методы
- 4.Основные методы решения задач моделирования
- Моделирование как наука. Роль математического моделирования в процессе принятия решения.
- 4.Экономико-математические методы. Методы моделирования.
- 1 Методы математического моделирования
- 3. Математические методы моделирования
- Основные этапы решения задач с использованием математического моделирования.
- 21.2. Методы математического моделирования