Затем элементы столбца Х0 (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х5, она и будет ключевой. Ключевой элемент 4.
Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.
В столбцах Ро и Cj занимают место вводимая в план неизвестная х3 с прибылью 28 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:
- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столбца;
- соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключевой момент;
- частное от деления вычитают из значения элемента, которое он имел до преобразования, и полученный результат будет преобразованным элементом, который записывается в новую таблицу в том же самом месте. Следуя этому правилу, преобразование элементов столбца х0 будет:
Включение на первой итерации в план неизвестной х3 обеспечит сумму прибыли 1400 руб.
Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент -13. Он находится в столбце х1, который принимается за ключевой, а ключевой строкой будет х6 (116:1,3=92,8; 50:0,3=200; 253:2,8=92), ключевым элементом 2,8. Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу.
2-я итерация
cj
p2
x0
x1
х2
х3
х4
х5
х6
0
х4
1
0
1.18
0
1
-1
-0.5
28
х3
27
0
0.64
1
0
0.3
-0.1
13
х1
92
1
0
0
0
0
0
Zj - Cj
2596
0
2.91
0
0
5.8
4.7
В последней таблице целевая строка имеет только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение его невозможно.
Как видно из таблицы, оптимальный план предусматривает выпуск продукции П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 |
|
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9
