Пример нахождения максимума функции симплексным методом

Здесь рассмотрен пример решения калькулятором в виде симплексной таблицы. Существуют и другие формы записи симплекс-метода

Предприятие выпускает 2 вида продукции А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1,а2,а3 кг соответственно , а для единицы изделия В-b1,b2,b3 кг. Производство обеспечено сырьем каждого вида в количестве P1,P2,P3 кг. Соответственно. Стоимость единицы изделия А составляет С1 руб., а единицы изделия В- С2 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость продукции. Решить
А) геометрически;
В) симплекс-методом.

Матрица коэффициентов 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

Перейти к онлайн решению своей задачи

Пример. Наиболее эффективным для хозяйства является выращивание трех культур: озимой пшеницы, проса, гречихи. Ожидаемый уровень урожайности этих культур, себестоимость центнера продукции, нормы внесен6ия удобрений и затраты труда в расчете на единицу продукции, приведенные в соответствии с ожидаемым уровнем урожайности, заданы таблицей. Известны и наиболее вероятные цены фактической реализации центнера продукции.
Критерий оптимальности – максимум прибыли от реализации данных видов продукции.

Введем систему обозначений:
Х1 – искомая площадь посева озимой пшеницы (га);
Х2 – искомая площадь посева проса (га);
Х3 – искомая площадь посева гречихи (га).

Ограничения:
1. Общая площадь посева культур (га)
Х123≤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

Таким образом математическая модель задачи выглядит так:
Х123≤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

загрузка...