Методы оптимальных решений. 7

Задача 1

решить графически.

 

max(min) F = 2x₁ + x₂

 

 

Задача 2

Для производства 4-х видов продукции  используется 3 вида сырья. Нормы расхода  сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

 

Задача 3

Четыре предприятия данного  экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого  из пред- приятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

С =

 

 

Составить такой план перевозок, при  котором общая себестоимость  перевозок является минимальной. Задачу решить методом потенциалов.

 

	B1	B2	B3	B4
A1	5	7	3	5	100
A2	1	2	5	6	150
A3	3	4	1	2	50
	75	80	60	85

 

Задача 4

Решить задачи целочисленного программирования геометрическим методом.

 

F=3x₁+2x₂ max,

2x₁+x₂ 5

-2x₁+3x₂ 10

x₁ 0, x₂ 0,

x₁, x₂ – целые

 

Задача 5

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

 

Задача 1

решить графически.

max(min) F = 2x₁ + x₂

 

 

 

Принимаем:

 

Строим график

 

Минимум будет в точке А

Найдем координаты точки А – пересечения прямых:

= = =

 

= =

 

F_min = 2x₁ + x₂ = + 22/7 = 16/7 = 2,28

Минимум будет в точке C

Найдем координаты точки С – пересечения прямых:

= = =

 

= =

F_max = 2x₁ + x₂ = + 1 = 13

 

 

 

Задача 2

Для производства 4-х видов продукции  используется 3 вида сырья. Нормы расхода  сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

Решение:

Составим математическую модель. Обозначим:

х₁ – выпуск изделия 1;

х₂ – выпуск изделия 2;

х₃ – выпуск изделия 3.

x₄ – выпуск изделия 4.

 

Запишем систему ограничений:

Общая ценность произведенных товаров  составляет:

F =

По экономическому содержанию переменные х₁, х₂, х₃, х₄ могут принимать только неотрицательные значения: х₁, х₂, х₃, х₄ 0

Запишем эту задачу в виде основной ЗЛП, для этого перейдем от системы  неравенств к равенствам, для этого  введем три дополнительные переменные:

Экономический смысл новых переменных – не используемое при данном плане производства количества сырья того или иного вида.

Запишем преобразованную систему  уравнений в векторной форме:

x₁* P₁ + x₂* P₂ + x₃* P₃ + x₄* P₄ + x₅* P₅ + x₆* P₆ + x₇* P₇+ x₈* P₈

 

P₁= ; P₂= ; P₃= ; P₄= ; P₅= ; P₆= ; P₇= ; P₈= ;

P₉= .

Поскольку среди векторов Рj имеется четыре единичных вектора, то для дан- ной задачи можно записать опорный план Х=(0, 0, 0,0,35, 50, 100; 0;0) определяемый системой единичных векторов Р5, Р6, Р7, Р8, которые образуют базис трехмерного пространства.

Составляем симплексную таблицу  I итерации и подсчитываем значения

F₀, z_j – c_j.

Проверяем исходный план на оптимальность:

F₀ = (C,P₀) = 0; z₁ = (C,P₁) = 0 ; z₂ = (C,P₂) = 0; z₃ = (C,P₃) = 0; z₄ = (C,P₄) = 0

z₁ – c₁ = 0 = ; z₂ – c₂ = 0 = ; z₃ – c₃ = 0 = ;

z₄ – c₄ = 0 = .

Для векторов базиса z_i – c_i = 0 (j = 5,6,7,8).

Таблица I

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	35	6	3	1	8	1	0	0	0
2	P6	0	50	10	5	2	9	0	1	0	0
3	P7	0	100	4	6	15	10	0	0	1	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			0	-3,5	-7	-9	-11	0	0	0	0

 

Максимальное отрицательное число  _j стоит в 5-ой строке столбца Р4. Следовательно, в базис введем вектор Р4. Определим вектор, подлежащий

исключению из базиса, для этого  находим  ₀ min(b_i/a_ij) для a_i3>0

₀ min(35/8; 50/9; 100/10) = 35/8

 

Т.е. ограничивающим фактором для производства изделий 4 является имеющийся ресурс I вида. С учетом его наличия предприятие может изготовить 35/8 (4) изделия 4, при этом ресурс I вида будет полностью израсходован.

 

Следовательно, вектор Р5 подлежит исключению из базиса. Столбец вектора Р4 и 1-я строка являются направляющими.

 

Составим таблицу II итерации. Сначала заполняем строку вектора, вновь введенного в базис, т.е. направляющую строку 1.

Элементы этой строки получаются путем  деления соответствующих элементов таблицы 1 на разрешающий элемент (т.е. 8). При этом в столбец Сб записываем коэффициент С3=11, стоящий в столбце вводимого в базис вектора Р4.

Таблица II

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	35/8	3/4	3/8	1/8	1	1/8	0	0	0
2	P6	0	85/8	13/4	13/8	7/8	0	-9/8	1	0	0
3	P7	0	225/4	-7/2	9/4	55/4	0	-5/4	0	1	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			385/8	4,75	-23/8	-61/8	0	11/8	0	0	0

 

Для определения остальных  элементов таблицы II применим правило треугольника.

Вычислим элементы таблицы II, стоящие в столбце Р0.

 

Первый элемент был вычислен ранее ₀ = 35/8)

 

Второй элемент - находим три числа 

1) число, стоящее в т. 1 на пересечении столбца Р₀ и 2-ой строки (50);

2) число, стоящее в т. 1 на пересечении столбца Р₄ и 2-ой строки (9);

3) число, стоящее в т. 2 на пересечении столбца Р₀ и 1-ой строки (35/8).

50 - 9*35/8 = 85/8

Третий элемент

1) число, стоящее в т. 1 на пересечении столбца Р₀ и 3-ей строки (100);

2) число, стоящее в т. 1 на пересечении столбца Р₄ и 3-ей строки (10);

3) число, стоящее в т. 2 на пересечении столбца Р₀ и 1-ой строки (35/8).

100 - 10*35/8 = 225/4

Четвёртый элемент -

1) число, стоящее в т. 2 на пересечении столбца Р₀ и 4-ой строки (0);

2) число, стоящее в т. 2 на пересечении столбца Р₄ и 4-ой строки (0);

3) число, стоящее в т. 3 на пересечении столбца Р₀ и 1-ой строки (35/8).

0 - 0*35/8 = 0

 

Значение F0 в 5-ой строке этого же столбца можно найти двумя способами:

1) по формуле F₀ = (C,P₀) = 11* 35/8 + 0 * 85/8 + 0 * 225/4 = 385/8

2) по правилу треугольника: 11* 35/8 = 385/8

 

Вычислим элементы вектора Р1 т.2. Первые два числа берем из столбцов Р1 и Р4 т.1, а третье число – из т.2 на пересечении 1- ой строки и столбца Р1

10 – 9 * 3/4 = 13/4 , 4 – 10 * 3/4 = -7/2 , 0 - 0 * 3/4 = 0

 

Значение z₁ – c₁ в 5-ой строке столбца вектора Р1

можно найти двумя способами:

1) по формуле z₁ – c₁ = (C,P₁)-с₁ = 11 * 3/4 + 0 * 13/4 + 0 * (-7/2) – 3,5 = 4,75

2) по правилу треугольника: - 3,5 - (-11) * 3/4 = 4,75

 

Аналогично находим элементы столбца вектора P₂, P₃, P₄

5 - 9* 3/8 = 13/8 6 – 10 * 3/8 = 9/4 0 - 0 * 3/8 = 0

- 7 - (- 11) * 3/8 = -23/8

 

2 - 9* 1/8 = 7/8 15 – 10 * 1/8 = 55/4 0 - 0 * 1/8 = 0

- 9 - (-11) * 1/8 = -61/8

Элементы столбца вектора Р₅ вычисляем по правилу треугольника.

Однако построенные для  определения этих элементов треугольники вы- глядят иначе.

При вычислении элемента 2-й  строки указанного столбца получается

треугольник, образованный числами 0;9 и 1/8. Следовательно, искомый элемент равен

0 – 9* 1/8 = - 9/8

Элемент, стоящий в 3-й  строке данного столбца, равен 

0 – 10 * 1/8 = - 10/8 = - 5/4

0 - (-11) * 1/8 = 11/8

По окончании расчета  всех элементов таблица II в ней получены новый опорный план и коэффициенты разложения векторов Рj через базисные векторы P₃, P₅, P₆, P₈ и значения

Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 0; 35/8; 0; 85/8; 225/4; 0).

Найденный на II итерации план задачи не является оптимальным.

Это видно и из 5-й строки таблицы 2, поскольку в столбце вектора P₂ и P₃ этой строки стоит отрицательное число – 23/8 и – 61/8

Значит, в базис следует  ввести вектор P₃ т. е. в новом плане следует предусмотреть выпуск изделия 3.

 

При определении возможного числа изготовления изделий 3 следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий 1 определяется для т.е. находим min( / /) для a_i2>0

₀ min(35/8/1/8; 85/8/7/8; 225/4/55/4) = 225/4/55/4 = 45/11

Следовательно, исключению из базиса подлежит вектор Р₇ иными словами, выпуск изделий 1 ограничен имеющимся в распоряжении предприятия ресурсом III вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 45/11 (4) изделия 1. Число 55/4 является разрешающим элементом, а столбец вектора P3 и 3-я строка таблицы 2 являются направляющими.

Составим таблицу для III итерации.

Таблица III

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	85/22	43/55	39/110	0	1	3/22	0	-1/110	0
2	P6	0	155/22	191/55	163/110	0	0	-23/22	1	-7/110	0
3	P3	9	45/11	-14/55	9/55	1	0	-1/11	0	4/55	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			1745/22	2,8	-179/110	0	0	15/22	0	61/110	0

Найденный на III итерации план задачи не является оптимальным.

Это видно и из 5-й строки таблицы 2, поскольку в столбце вектора P₂ этой строки стоит отрицательное число – 179/110

Значит, в базис следует  ввести вектор P₂ т. е. в новом плане следует предусмотреть выпуск изделия 2.

Исключению из базиса подлежит вектор Р₆

 

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	355/163	-8/163	0	0	1	63/163	-39/163	-1/163	0
2	P2	7	775/163	382/163	1	0	0	-115/163	110/163	-7/163	0
3	P3	9	540/163	-104/163	0	1	0	4/163	-18/163	13/163	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			14190/163	6,62	0	0	0	-76/163	179/163	79/163	0

 

Найденный на IV итерации план задачи не является оптимальным.

Это видно и из 5-й строки таблицы 2, поскольку в столбце вектора P₅ этой строки стоит отрицательное число – 76/163

Значит, в базис следует  ввести вектор P₅

Исключению из базиса подлежит вектор Р₄

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	355/63	-8/63	0	0	163/63	1	-13/21	1/63	0
2	P2	7	550/63	142/63	1	0	115/63	0	5/21	-2/63	0
3	P3	9	200/63	-40/63	0	1	-4/63	0	-2/21	5/63	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			5650/63	6,56	0	0	76/63	0	17/21	31/63	0

 

В результате в таблице V получаем новый опорный план

X=(0; 550/63; 220/63; 0; 355/63; 0; 0; 0). и коэффициенты разложения векторов Рj через базисные векторы P₁, P₂, P_3, P₄ соответствующие значения

Проверяем, является ли данный опорный  план оптимальным или нет.

Для этого рассмотрим 5-ю строку, таблицы 3 . В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и F_max = 5650/63 = 89,68

Следовательно, план выпуска  продукции, включающий изготовление 550/63(8) изделий 2 и 200/63 (3)изделий 3, является оптимальным. При данном плане выпуска изделий полностью используется сырье II и III видов и остается неиспользованным 355/63 (5,63) ресурсов I вида, а ценность производимой продукции равна 5650/63 = 89,68

Оптимальным планом производства продукции не предусматривается  изготовление изделий 1 и 4 . Введение в план выпуска продукции изделий вида 1 привело бы к уменьшению указанной общей стоимости. Это видно из 5-й строки столбца вектора P1, где число 6,56 показывает, что при данном плане включение в него выпуска единицы изделия 1 приводит лишь к уменьшению общей величины стоимости на 6,56.

Введение в план выпуска  продукции изделий вида 4 привело бы к уменьшению указанной общей стоимости. Это видно из 5-й строки столбца вектора P4, где число 76/63 (1,21) показывает, что при данном плане включение в него выпуска единицы изделия 4 приводит лишь к уменьшению общей величины стоимости на 1,21.

Построить двойственную задачу и решить ее симплекс-методом 

F_max = F =

x_j 0 (j = 1,2,3,4)

 

A =

 

A^T = =

 

=

y_j 0 (j = 1,2,3,4)

Умножим целевую функцию на -1 и  будем искать

S' = -S = -35*y₁ - 50*y₂ - 100*y₃ → MAX 
Cистема ограничений в форме Такера примет вид:  
y₄ = -3,5- ( -6*y₁ - 10y₂ - 4*y₃ ) 
y₅ = -7 - ( -3*y₁ - 5*y₂ - 6*y₃ ) 
y₆ = -9 - (-y₁ - 2*y₂ - 15*y₃ ) 
y₇ = -11 - ( -8*y₁ - 9*y₂ - 10*y₃ ) 
Целевая функция: 
S' = 0 - ( 35*y₁ + 50*y₂ + 100*y₃ )

y₁* P₁ + y₂* P₂ + y₃* P₃ + y₄* P₄ + y₅* P₅ + y₆* P₆ + y₇* P₇ + y₈* P₈

P₁= ; P₂= ; P₃= ; P₄= ; P₅= ; P₆= ; P₇= ; P₈= ;

P₉= .

Поскольку среди векторов Рj имеется четыре единичных вектора, то для дан- ной задачи можно записать опорный план

Y=(0, 0, 0,0,3,5, 7, 9;11 )

Составляем симплексную таблицу  I итерации и подсчитываем значения

F₀, z_j – c_j.

Проверяем исходный план на оптимальность:

F₀ = (C,P₀) = 0; z₁ = (C,P₁) = 0 ; z₂ = (C,P₂) = 0; z₃ = (C,P₃) = 0; z₄ = (C,P₄) = 0

z₁ – c₁ = 0 = ; z₂ – c₂ = 0 = ; z₃ – c₃ = 0 = ;

z₄ – c₄ = 0 = .

Для векторов базиса z_i – c_i = 0 (j = 5,6,7,8).

Составим таблицу I итерации

Таблица I

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	-3/5	-6	-10	-4	0	1	0	0	0
2	P6	0	-7	-3	-5	-6	0	0	1	0	0
3	P7	0	-9	-1	-2	-15	0	0	0	1	0
4	P8	0	-11	-8	-9	-10	0	0	0	0	1
5			0	35	50	100	0	0	0	0	0