Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Метод Гомори Графический метод Теория игр
Симплекс-метод M-задача Теоремы двойственности
Одноканальные СМО Задача коммивояжера Транспортная задача

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

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

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

Далее решается согласно алгоритму симплексного метода.

Поиск наибольшего значения

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 = 6X1+4X2 => max.
Построим прямую, отвечающую значению функции F = 0: F = 6X1+4X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых: 12x1+3x2≤264 4x1+5x2≤136
Решив систему уравнений, получим:
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

Итерация №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

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной 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. На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.

Посмотреть решение