Решение задач симплекс методом (стр. 2 из 4)
Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.
Элементы целевой строки оптимального плана называются двойственными оценками, которые определяют величину изменения прибыли при изменении запасов сырья на I ед.
ЗАДАЧА 2
Требуется определить минимальную по стоимости смесь сырья для изготовления пищевых концентратов, которые должны содержать питательные вещества (П). Эти вещества содержаться в сырье (М) в различных сочетаниях. Содержание питательных веществ в сырье и готовом продукте, а также цена на каждый вид сырья показаны в таблице.
| Питательные вещества | Виды сырья | Минимальное содержание (единиц) питательных веществ в готовом продукте | ||
| M1 | М2 | М3 | ||
| П1 | 1 | 1 | 0 | 50 |
| П2 | 4 | 1 | 3 | 140 |
| П3 | 1 | 4 | 1 | 127 |
| П4 | 0 | 3 | 2 | 80 |
| Цена за единицу сырья, руб. | 8 | 12 | 10 | |
Виды используемого сырья условно обозначены через М1, М2, М3; содержание питательных веществ в сырье и готовом продукте обозначены П1, П2, П3, П3.
Исходные условия задачи выражаются неравенствами:
1х1 + 1х2 + 0х3 ≥ 50
4х1 + 1х2 + 3х3 ≥ 140
1х1 + 4х2 + 1х3 ≥ 127
0х1 + 3х2 + 2х3 ≥ 80
F= 8х1 + 12х2 + 10х3 = min
Умножив обе части неравенств на -1, получим систему с другим направлением знака неравенств:
-1х1 - 1х2 - 0х3 ≥ -50
-4х1 - 1х2 - 3х3 ≥ -140
-1х1 - 4х2 - 1х3 ≥ -127
0х1 - 3х2 - 2х3 ≥ -80
F = 8х1 + 12х2 + 10х3 = min
Преобразуем неравенства в эквивалентные равенства с помощью дополнительных неизвестных. Симплексные уравнения будут следующими:
-50 = -1х1 - 1х2 - 0х3 + 1х4 + 0х5 + 0х6 + 0х7
-140 = -4х1 - 1х2 - 3х3 + 0х4 + 1х5 + 0х6 + 0х7
-127 = -1х1 - 4х2 - 1х3 + 0х4 + 0х5 + 1х6 + 0х7
-80 = 0х1 - 3х2 - 2х3 + 0х4 + 0х5 + 0х6 + 1х7
F = 8х1 + 12х2 + 10х3 + 0х4 + 0х5 + 0х6 + 0х7 = min
Записанные уравнения отличаются от тех, которые нами рассматривались выше, тем, что коэффициенты при основных неизвестных и свободные члены имеют отрицательные знаки.
Решение таких задач производится двойственным симплексным методом. Система симплексных уравнений записывается в таблице.
| cj | p0 | x0 | 8 | 12 | 10 | 0 | 0 | 0 | 0 |
| x1 | х2 | х3 | х4 | х5 | х6 | х7 | |||
| 0 | х4 | -50 | -1 | -1 | 0 | 1 | 0 | 0 | 0 |
| 0 | х5 | -140 | -4 | -1 | -3 | 0 | 1 | 0 | 0 |
| 0 | х6 | -127 | -1 | -4 | -1 | 0 | 0 | 1 | 0 |
| 0 | х7 | -80 | 0 | -3 | -2 | 0 | 0 | 0 | 1 |
| Zj - Cj | 0 | -8 | -12 | -10 | 0 | 0 | 0 | 0 | |
Элементы целевой строки рассчитывают по обычным правилам и получают отрицательные знаки.
В отличие от вычислительной процедуры основного симплексного метода решение задач двойственным методом выполняется в обратном порядке.
В итоговом столбце свободные числа имеют отрицательные знаки. Это является свидетельством того, что данный план нельзя считать допустимым, так как он противоречит экономическому смыслу. План можно считать допустимым только тогда, когда в итоговом столбце не будет отрицательных чисел.
Ликвидация отрицательных чисел в итоговом столбце начинается с наибольшего по абсолютной величине. В нашем примере таким числом является (-140). Строка х5, в которой находится это число, принимается за ключевую и соответственно выделяется.
Определив ключевую строку, находим ключевой столбец. Для этого нужно элементы целевой строки разделить на элементы ключевой строки и из полученных отношений выбрать наименьшее. Столбец, имеющий наименьшее отношение, принимается за ключевой и так же как ключевая строка, выделяется.
Столбцы х1, х2, х3 будут иметь следующие отношения:
Наименьшее отношение имеет столбец х1,он и будет являться ключевым.
Определив ключевую строку, ключевой столбец и ключевое число, по обычным правилам преобразуются все элементы матрицы и записываются в новой таблице.
1-я итерация
| cj | p0 | x0 | 18 | 15 | 24 | 0 | 0 | 0 | 0 |
| x1 | х2 | х3 | х4 | х5 | х6 | х7 | |||
| 0 | х4 | -15 | 0 | -0.75 | 0.75 | 1 | -0.25 | 0 | 0 |
| 8 | х1 | 35 | 1 | 0.25 | 0.75 | 0 | -0.25 | 0 | 0 |
| 0 | х6 | -92 | 0 | -3.75 | -0.25 | 0 | -0.25 | 1 | 0 |
| 0 | х7 | -80 | 0 | -3 | -2 | 0 | 0 | 0 | 1 |
| Zj - Cj | 280 | 0 | -10 | -4 | 0 | -2 | 0 | 0 | |
После преобразования элементов в итоговом столбце осталось еще три отрицательных числа в строке х4, х6 и х7. Наибольшим по абсолютной величине является число в строке х6. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х2. Вводим этот вид сырья в программу вместо неизвестного х6. По общим правилам преобразуем элементы матрицы.
2-я итерация
| cj | p0 | x0 | x1 | х2 | х3 | х4 | х5 | х6 | х7 |
| 0 | х4 | 3.4 | 0 | 0 | 0.8 | 1 | -0.2 | -0.2 | 0 |
| 8 | х1 | 28.9 | 1.0 | 0.0 | 0.7 | 0.0 | -0.3 | 0.1 | 0.0 |
| 15 | х2 | 24.5 | 0.0 | 1.0 | 0.1 | 0.0 | 0.1 | -0.3 | 0.0 |
| 0 | х7 | -6.4 | 0.0 | 0.0 | -1.8 | 0.0 | 0.2 | -0.8 | 1.0 |
| Zj - Cj | 525.3 | 0.0 | 0.0 | -3.3 | 0.0 | -1.3 | -2.7 | 0.0 | |
После преобразования элементов в итоговом столбце осталось еще одно отрицательное число в строке х7. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х3. Вводим этот вид сырья в программу вместо неизвестного х7. По общим правилам преобразуем элементы матрицы.
В таблице записаны преобразованные числа, полученные на 3-й итерации. В итоговом столбце все отрицательные числа исчезли, значит полученный план является допустимым и одновременно оптимальным. Вывод о том, что план получен оптимальный, позволяют сделать элементы целевой строки. Все они отрицательны или равны нулю, что свидетельствует об оптимальности результата при решении задач на минимум целевой функции.
3-я итерация
| cj | p0 | x0 | x1 | х2 | х3 | х4 | х5 | х6 | х7 |
| 0 | х4 | 0.6 | 0.0 | 0.0 | 0.0 | 1.0 | -0.1 | -0.6 | 0.4 |
| 8 | х1 | 26.3 | 1.0 | 0.0 | 0.0 | 0.0 | -0.2 | -0.3 | 0.4 |
| 15 | х2 | 24.3 | 0.0 | 1.0 | 0.0 | 0.0 | 0.1 | -0.3 | 0.0 |
| 10 | х3 | 3.6 | 0.0 | 0.0 | 1.0 | 0.0 | -0.1 | 0.4 | -0.6 |
| Zj - Cj | 537.2 | 0.0 | 0.0 | 0.0 | 0.0 | -1.7 | -1.2 | -1.9 | |
Подставив значения неизвестных в исходные неравенства, получаем:
1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50
4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140
1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127
0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80
Стоимость сырья при этом будет минимальной и составит:
F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2
ЗАДАЧА 3
Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице.
| Поставщики | Потребители | Объемы вывоза, т | |||||
| М1 | М2 | М3 | М4 | М5 | М6 | ||
| П1 | 24 | 30 | 42 | 15 | 39 | 21 | 144 |
| П2 | 9 | 24 | 30 | 33 | 27 | 29 | 148 |
| П3 | 24 | 22 | 20 | 45 | 21 | 23 | 76 |
| П4 | 11 | 36 | 27 | 40 | 30 | 8 | 132 |
| Объемы завоза, т | 92 | 84 | 80 | 112 | 96 | 36 | |
Решение задачи начинается с распределения у имеющихся у поставщиков объемов вывоза между потребителями с учетом объемов завоза. Для первоначального распределения используются способы: северо-западного угла, наименьшего элемента по строке, наименьшего элемента по столбцу, наименьшего элемента матрицы.