Контрольная работа: Решение задач симплекс методом
В последней таблице целевая строка имеет только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение его невозможно.
Как видно из таблицы, оптимальный план предусматривает выпуск продукции П1 27 ед. (х1 = 27), П3 92 ед. (х3 = 92), дополнительного неизвестного П4 1 ед. (х4 = 1). П2 и дополнительные неизвестные в план не вошли, следовательно, х2 = 0, х5 = 0 х6 = 0. Подставив значения неизвестных в уравнения, получим:
2 * 92 + 4 * 0 + 3 * 27 + 1 = 266
1 * 92 + 3 * 0 + 4 * 27 + 0 = 200
3 * 92 + 2 * 0 + 1 * 27 + 0 = 303
F = 20 * 92 + 24 * 0 + 27 * 28 = 2596
Анализ оптимального плана.
а) Запасы сырья трех видов используются не полностью, так как х4 = 1, а х5 = х6 = 0.
б) Рассмотрим элементы матрицы.
От выпуска продукции II следует отказаться.
Элементы столбца х5 показывают, что увеличение запасов сахара на I ед. (х5 = 1) позволит увеличить выпуск продукции III вида на 0,3 ед. Сумма прибыли увеличится на 5,8 руб.
Элементы столбца х6 показывают, что увеличение запасов жира на I ед. (х6 = 1) позволит уменьшить выпуск только продукции III вида на 0,1 ед. (27 - 0.1) Сумма прибыли увеличится на 4,7 руб.
Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.
Элементы целевой строки оптимального плана называются двойственными оценками, которые определяют величину изменения прибыли при изменении запасов сырья на 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