Симплекс-метод. Поиск наибольшего значения

Вариант 1.
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, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (12), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

 План

 Базис

 В

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

Поставщик

В1

В2

В3

В4

Запасы груза

А1

4

6

19

21

100

А2

29

4

8

6

150

А3

7

11

13

14

200

Потребности

220

80

75

75

 

Решение:
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 4
 

 6
 

 19
 

 21
 

 100
 

 2
 

 29
 

 4
 

 8
 

 6
 

 150
 

 3
 

 7
 

 11
 

 13
 

 14
 

 200
 

 Потребности
 

 220
 

 80
 

 75
 

 75
 

 
 

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 100 + 150 + 200 = 450
∑ b = 220 + 80 + 75 + 75 = 450
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 4
 

 6
 

 19
 

 21
 

 100
 

 2
 

 29
 

 4
 

 8
 

 6
 

 150
 

 3
 

 7
 

 11
 

 13
 

 14
 

 200
 

 Потребности
 

 220
 

 80
 

 75
 

 75
 

 
 

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Искомый элемент равен 4
Для этого элемента запасы равны 100, потребности 220. Поскольку минимальным является 100, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 29
 

 4
 

 8
 

 6
 

 150
 

 7
 

 11
 

 13
 

 14
 

 200
 

 120
 

 80
 

 75
 

 75
 

 0
 


Искомый элемент равен 4
Для этого элемента запасы равны 150, потребности 80. Поскольку минимальным является 80, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 29
 

 4
 

 8
 

 6
 

 70
 

 7
 

 x
 

 13
 

 14
 

 200
 

 120
 

 0
 

 75
 

 75
 

 0
 


Искомый элемент равен 6
Для этого элемента запасы равны 70, потребности 75. Поскольку минимальным является 70, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 x
 

 4
 

 x
 

 6
 

 0
 

 7
 

 x
 

 13
 

 14
 

 200
 

 120
 

 0
 

 75
 

 5
 

 0
 


Искомый элемент равен 7
Для этого элемента запасы равны 200, потребности 120. Поскольку минимальным является 120, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 x
 

 4
 

 x
 

 6
 

 0
 

 7
 

 x
 

 13
 

 14
 

 80
 

 0
 

 0
 

 75
 

 5
 

 0
 


Искомый элемент равен 13
Для этого элемента запасы равны 80, потребности 75. Поскольку минимальным является 75, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 x
 

 4
 

 x
 

 6
 

 0
 

 7
 

 x
 

 13
 

 14
 

 5
 

 0
 

 0
 

 0
 

 5
 

 0
 


Искомый элемент равен 14
Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

 4
 

 x
 

 x
 

 x
 

 0
 

 x
 

 4
 

 x
 

 6
 

 0
 

 7
 

 x
 

 13
 

 14
 

 0
 

 0
 

 0
 

 0
 

 0
 

 0
 


 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 4[100]
 

 6
 

 19
 

 21
 

 100
 

 2
 

 29
 

 4[80]
 

 8
 

 6[70]
 

 150
 

 3
 

 7[120]
 

 11
 

 13[75]
 

 14[5]
 

 200
 

 Потребности
 

 220
 

 80
 

 75
 

 75
 

 
 

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v3 = 13; 3 + v3 = 13; v3 = 10
u3 + v4 = 14; 3 + v4 = 14; v4 = 11
u2 + v4 = 6; 11 + u2 = 6; u2 = -5
u2 + v2 = 4; -5 + v2 = 4; v2 = 9

 
 

 v1=4
 

 v2=9
 

 v3=10
 

 v4=11
 

 u1=0
 

 4[100]
 

 6
 

 19
 

 21
 

 u2=-5
 

 29
 

 4[80]
 

 8
 

 6[70]
 

 u3=3
 

 7[120]
 

 11
 

 13[75]
 

 14[5]
 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;2): 0 + 9 > 6; ∆12 = 0 + 9 - 6 = 3
(3;2): 3 + 9 > 11; ∆32 = 3 + 9 - 11 = 1
max(3,1) = 3
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 4[100][-]
 

 6[+]
 

 19
 

 21
 

 100
 

 2
 

 29
 

 4[80][-]
 

 8
 

 6[70][+]
 

 150
 

 3
 

 7[120][+]
 

 11
 

 13[75]
 

 14[5][-]
 

 200
 

 Потребности
 

 220
 

 80
 

 75
 

 75
 

 
 

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 
 

 1
 

 2
 

 3
 

 4
 

 Запасы
 

 1
 

 4[95]
 

 6[5]
 

 19
 

 21
 

 100
 

 2
 

 29
 

 4[75]
 

 8
 

 6[75]
 

 150
 

 3
 

 7[125]
 

 11
 

 13[75]
 

 14
 

 200
 

 Потребности
 

 220
 

 80
 

 75
 

 75
 

 
 

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v3 = 13; 3 + v3 = 13; v3 = 10
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u2 + v2 = 4; 6 + u2 = 4; u2 = -2
u2 + v4 = 6; -2 + v4 = 6; v4 = 8

 
 

 v1=4
 

 v2=6
 

 v3=10
 

 v4=8
 

 u1=0
 

 4[95]
 

 6[5]
 

 19
 

 21
 

 u2=-2
 

 29
 

 4[75]
 

 8
 

 6[75]
 

 u3=3
 

 7[125]
 

 11
 

 13[75]
 

 14
 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui+ vi <= cij.
Минимальные затраты составят:
F(x) = 4*95 + 6*5 + 4*75 + 6*75 + 7*125 + 13*75  = 3010
Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект