Пример нахождения максимума функции симплексным методом
Здесь рассмотрен пример решения калькулятором в виде симплексной таблицы. Существуют и другие формы записи симплекс-методаПример №1. Предприятие выпускает 3 вида продукции А1, A2 и A3, для производства которых используется сырье трех видов. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а11,а12,а13 кг соответственно, а для единицы изделия A2-a21,a22,a23 кг. Производство обеспечено сырьем каждого вида в количестве P1,P2,P3 кг. Стоимость единицы изделия А1 составляет С1 руб., А2 составляет С2 руб., а единицы изделия A3- С3 руб. Требуется составить план производства изделий А1, A2 и A3, обеспечивающий максимальную стоимость продукции. Решить:
А) геометрически;
В) симплекс-методом.
{a1j}={0.1;0.2;0.4}
{a2j}={0.05;0.02;0.02}
{a3j}={3;1;2}
P1=1100,P2=120,P3=8000
C1=3,C2=5,C3=4
Решение.
Математическая модель задачи:
0.1x1+0.2x2+0.4x3 ≤ 1100
0.05x1+0.02x2+0.02x3 ≤ 120
3x1+x2+2x3 ≤ 8000
3x1+5x2+4x3 → max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных: x4,x5,x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (1100,120,8000)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Индексная строка | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Индексная строка | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Индексная строка | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее: 
Следовательно,1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=0.04
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Конец итераций: найден оптимальный план
Оптимальный план можно записать так: x2 = 5375, x1 = 250, x6 = 1875. F(X) = 27625
Перейти к онлайн решению своей задачи
Пример №2. Наиболее эффективным для хозяйства является выращивание трех культур: озимой пшеницы, проса, гречихи. Ожидаемый уровень урожайности этих культур, себестоимость центнера продукции, нормы внесен6ия удобрений и затраты труда в расчете на единицу продукции, приведенные в соответствии с ожидаемым уровнем урожайности, заданы таблицей. Известны и наиболее вероятные цены фактической реализации центнера продукции.
Критерий оптимальности – максимум прибыли от реализации данных видов продукции.
Введем систему обозначений:
Х1 – искомая площадь посева озимой пшеницы (га);
Х2 – искомая площадь посева проса (га);
Х3 – искомая площадь посева гречихи (га).
Ограничения:
1. Общая площадь посева культур (га)
Х1+Х2+Х3≤2000
2. Затраты труда (чел.-дни)
Если за единицу измерения неизвестных принят 1 га, то соответственно необходимо рассчитать все нормативы на эту единицу. Затраты труда даны по условию задачи в расчете на 1 ц продукции , но, зная урожайность , легко пересчитать нормативы затрат труда в расчете на 1 га посева. Таким образом ограничение запишется так:
40x1 + 50x2 + 45x3 ≤ 14600
3. Расход минеральных удобрений (ц д.в.)
0.8x1 + 0.6x2 + x3 ≤ 1600
Целевая функция:
Поскольку в качестве критерия оптимальности выступает максимум прибыли, то необходимо рассчитать соответствующие коэффициенты данной целевой функции. В расчете на 1 га прибыль составит соответственно: (11.6-6)*30, (8-7)*18,(30-11)*15 рублей. Прибыль = выручка - себестоимость.
Целевая функция задач при этом будет выглядеть так:
(11.6-6)*30x1 + (8-7)*18x2 + (30-11)*15x3 = max
Таким образом математическая модель задачи выглядит так:
Х1+Х2+Х3≤2000
9,6Х1+7Х2+7,2Х3≤14600
0,6Х1+0,4Х2+0,8Х3≤1600
Z=168Х1+18Х2+285Х3=max
Далее решается согласно алгоритму симплексного метода.
Поиск наибольшего значения
1. Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны: 12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида - 4 у.е. Составить план, обеспечивающий наибольшую прибыль производству:а) записать математическую модель;
б) решить задачу графическим методом;
в) решить задачу симплекс-методом;
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Решение:
а) математическая модель;
x1 – производство цемента первого вида;
x2 – производство цемента второго вида;
12x1 + 3x2 ≤ 264
4x1 + 5x2 ≤ 136
3x1 + 14x2 ≤ 266
x1 ≥ 0, x2 ≥ 0
Целевая функция:
6x1 + 4x2 → max
б) решим задачу графическим методом;
Необходимо найти максимальное значение целевой функции F = 6X1+4X2 => max, при системе ограничений:
12x1+3x2≤264 (1)
4x1+5x2≤136 (2)
3x1+14x2≤266 (3)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Обозначим границы области многоугольника решений.
Построим прямую, отвечающую значению функции F = 0: F = 6X1+4X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Решив систему уравнений, получим:
x1 = (264-3x2)/12
4(264-3x2)/12+5x2 = 136
x1 = 19, x2 = 12
Откуда найдем максимальное значение целевой функции: F(X) = 6*19 + 4*12 = 162
Таким образом, чтобы получить максимальную прибыль необходимо выпускать 19 т. цемента 1-го вида, и 12 т. цемента 2-го вида.
в) решить задачу симплекс-методом;
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x1+4x2 при следующих условиях-ограничений.
12x1+3x2≤264
4x1+5x2≤136
3x1+14x2≤266
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
12x1 + 3x2 + 1x3 + 0x4 + 0x5 = 264
4x1 + 5x2 + 0x3 + 1x4 + 0x5 = 136
3x1 + 14x2 + 0x3 + 0x4 + 1x5 = 266
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,264,136,266)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 0 | x3 | 264 | 12 | 3 | 1 | 0 | 0 |
| x4 | 136 | 4 | 5 | 0 | 1 | 0 | |
| x5 | 266 | 3 | 14 | 0 | 0 | 1 | |
| Индексная строка | F(X0) | 0 | -6 | -4 | 0 | 0 | 0 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 1 | x3 | 264 | 12 | 3 | 1 | 0 | 0 | 22 |
| x4 | 136 | 4 | 5 | 0 | 1 | 0 | 34 | |
| x5 | 266 | 3 | 14 | 0 | 0 | 1 | 88.67 | |
| Индексная строка | F(X1) | 0 | -6 | -4 | 0 | 0 | 0 | 0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Diпо строкам как частное от деления
и из них выберем наименьшее: 
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3в план 1 войдет переменная x1
Строка, соответствующая переменной x1в плане 1, получена в результате деления всех элементов строки x3плана 0 на разрешающий элемент РЭ=12
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 2 | x1 | 22 | 1 | 0.25 | 0.0833 | 0 | 0 | 88 |
| x4 | 48 | 0 | 4 | -0.3333 | 1 | 0 | 12 | |
| x5 | 200 | 0 | 13.25 | -0.25 | 0 | 1 | 15.09 | |
| Индексная строка | F(X2) | 132 | 0 | -2.5 | 0.5 | 0 | 0 | 0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Diпо строкам как частное от деления
и из них выберем наименьшее: 
Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4в план 2 войдет переменная x2
Строка, соответствующая переменной x2в плане 2, получена в результате деления всех элементов строки x4плана 1 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 3 | x1 | 19 | 1 | 0 | 0.1042 | -0.0625 | 0 |
| x2 | 12 | 0 | 1 | -0.0833 | 0.25 | 0 | |
| x5 | 41 | 0 | 0 | 0.8542 | -3.31 | 1 | |
| Индексная строка | F(X3) | 162 | 0 | 0 | 0.2917 | 0.625 | 0 |
Оптимальный план можно записать так: x1 = 19, x2 = 12, x5 = 41; F(X) = 6*19 + 4*12 = 162
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Составим двойственную задачу к прямой задаче.
12y1+4y2+3y3≥6
3y1+5y2+14y3≥4
264y1+136y2+266y3 => min
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен: y1 = 0.29, y2 = 0.62, y3 = 0
Z(Y) = 264*0.29+136*0.62+266*0 = 162
2. На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.