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

Задача 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-й  строке данного столбца, равен