Системный анализ и исследование операций
Задача 1
8. Фирме требуется уголь с содержанием фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %. Три сорта угля А, В, С доступны по следующим ценам (за 1 т):
Сорт угля |
Содержание примеси фосфора, % |
Содержание примеси золы, % |
Цена, дол. |
A |
0.06 |
2.0 |
30 |
B |
0.04 |
4.0 |
30 |
C |
0.02 |
3.0 |
45 |
Как их смешивать, чтобы получить минимальную цену и удовлетворить ограничениям на содержание примесей? Покажите, что задача может быть представлена графически в двухмерном пространстве и таким образом может быть получено решение.
Решение
Построим математическую модель.
Обозначим:
Х1 - количество угля сорта А в тонне смеси;
Х2 - количество угля сорта В в тонне смеси, (переменные);
Х3 - количество угля сорта С в тонне смеси.
F(Х) = 30ЧX1 + 30ЧX2 + 45ЧX3 - стоимость 1 т. смеси (целевая функция),
- 0.06 ЧХ1 + 0.04ЧХ2 + 0.02ЧХ3 0.03 (%) - ограничение на содержание фосфора в смеси, 2ЧХ1 + 4ЧХ2+ 3ЧХ3 3.25 (%) - ограничение на содержание зольных примесей,
Х1+ Х2 + Х3 = 1 (т.) - ограничение на состав 1 т. смеси.
Окончательно, математическая модель имеет вид.
Определить количество угля сортов А, В, С (Х1, Х2, Х3) в тонне смеси, при которых достигается
F(Х) = 30ЧX1 + 30ЧX2 + 45ЧX3
При ограничениях
- 0.06 ЧХ1 + 0.04ЧХ2 + 0.02ЧХ3 <= 0.03 2чх1 + 4чх2 + 3чх3 <= 3.25
Х1 + Х2 + Х3 = 1
Х1, X2, X3>= 0.
Решим прямую задачу линейного программирования симплекс-методом.
Определим минимальное значение целевой функции F(X) = 30x1+30x2+45x3 при следующих условиях-ограничений.
- 0.06 x1+0.04x2+0.02x3?0.03 2x1+4x2+3x3?3.25
X1+x2+x3=1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x4. В 2-м неравенстве смысла (?) вводим базисную переменную x5.
- 0.06 x1 + 0.04x2 + 0.02x3 + 1x4 + 0x5 = 0.03 2x1 + 4x2 + 3x3 + 0x4 + 1x5 = 3.25 1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 1
Введем искусственные переменные x: в 3-м равенстве вводим переменную x6;
- 0.06 x1 + 0.04x2 + 0.02x3 + 1x4 + 0x5 + 0x6 = 0.03 2x1 + 4x2 + 3x3 + 0x4 + 1x5 + 0x6 = 3.25 1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 1x6 = 1
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = Mx6 > min
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 1-x1-x2-x3
Которые подставим в целевую функцию:
F(X) = M(1-x1-x2-x3) > min
Или F(X) = (-M)x1+(-M)x2+(-M)x3+(M) > min
Введем новую переменную x0 = - x1-x2-x3.
Выразим базисные переменные <4, 5, 6> через небазисные.
X0 = 1-x1-x2-x3
X4 = 0.03-0.06x1-0.04x2-0.02x3
X5 = 3.25-2x1-4x2-3x3
X6 = 1-x1-x2-x3
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на минимум, то переменную для включения в текущий план выбирают по минимальному отрицательному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
Max(-1,-1,-1,0,0,0) = -1
X0 = 1-x1-x2-x3
X4 = 0.03-0.06x1-0.04x2-0.02x3
X5 = 3.25-2x1-4x2-3x3
X6 = 1-x1-x2-x3
В качестве новой переменной выбираем x3.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3
И из них выберем наименьшее:
Вместо переменной x6 в план войдет переменная x3.
4. Пересчет всех уравнений.
Выразим переменную x3 через x6
X3 = 1-x1-x2-x6
И подставим во все выражения.
X0 = 1-x1-x2-(1-x1-x2-x6)
X4 = 0.03-0.06x1-0.04x2-0.02(1-x1-x2-x6)
X5 = 3.25-2x1-4x2-3(1-x1-x2-x6)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
X0 = 0+x6
X4 = 0.01-0.04x1-0.02x2+0.02x6
X5 = 0.25+x1-x2+3x6
X3 = 1-x1-x2-x6
Полагая небазисные переменные x = (4, 5, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:
X = (0, 0, 0, 0, 0, -1), x0 = 0
Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.
X0 = 0+x6
X4 = 0.01-0.04x1-0.02x2+0.02x6
X5 = 0.25+x1-x2+3x6
X3 = 1-x1-x2-x6
На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
X4 = 0.01-0.04x1-0.02x2
X5 = 0.25+x1-x2
X3 = 1-x1-x2
Выразим базисные переменные:
X3 = 1-x1-x2
Которые подставим в целевую функцию:
F(X) = 30x1 + 30x2 + 45(1-x1-x2)
Или
F(X) = 45-15x1-15x2
Получаем новую систему переменных.
X0 = 45-15x1-15x2
X4 = 0.01-0.04x1-0.02x2
X5 = 0.25+x1-x2
X3 = 1-x1-x2
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
Max(-15,-15,0,0,0) = -15
X0 = 45-15x1-15x2
X4 = 0.01-0.04x1-0.02x2
X5 = 0.25+x1-x2
X3 = 1-x1-x2
В качестве новой переменной выбираем x2.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2
И из них выберем наименьшее:
Вместо переменной x5 в план войдет переменная x2.
4. Пересчет всех уравнений.
Выразим переменную x2 через x5
X2 = 0.25+x1-x5
И подставим во все выражения.
X0 = 45-15x1-15(0.25+x1-x5)
X4 = 0.01-0.04x1-0.02(0.25+x1-x5)
X3 = 1-x1-(0.25+x1-x5)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
X0 = 41.25-30x1+15x5
X4 = 0.005-0.06x1+0.02x5
X2 = 0.25+x1-x5
X3 = 0.75-2x1+x5
Полагая небазисные переменные x = (4, 2, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:
X = (30, 0, 0, 0, -15), x0 = 41.25
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
Max(-30,0,0,0,15) = -30
X0 = 41.25-30x1+15x5
X4 = 0.005-0.06x1+0.02x5
X2 = 0.25+x1-x5
X3 = 0.75-2x1+x5
В качестве новой переменной выбираем x1.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1
И из них выберем наименьшее:
Вместо переменной x4 в план войдет переменная x1.
4. Пересчет всех уравнений.
Выразим переменную x1 через x4
X1 = 0.0833-16.67x4+0.33x5
И подставим во все выражения.
X0 = 41.25-30(0.0833-16.67x4+0.33x5)+15x5
X2 = 0.25+(0.0833-16.67x4+0.33x5)-x5
X3 = 0.75-2(0.0833-16.67x4+0.33x5)+x5
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
X0 = 38.75+500x4+5x5
X1 = 0.0833-16.67x4+0.33x5
X2 = 0.33-16.67x4-0.67x5
X3 = 0.58+33.33x4+0.33x5
Полагая небазисные переменные x = (1, 2, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:
X = (0, 0, 0, -500, -5), x0 = 38.75
Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
X0 = 38.75+500x4+5x5
X1 = 0.0833-16.67x4+0.33x5
X2 = 0.33-16.67x4-0.67x5
X3 = 0.58+33.33x4+0.33x5
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
X1 = 0.0833
X2 = 0.33
X3 = 0.58
F(X) = 30 * 0.0833 + 30 * 0.33 + 45 * 0.58 = 38.75
Анализ оптимального плана.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 0 в столбце x3 означает, что использование x3 - выгодно.
Значение 500 в столбце x4 означает, что теневая цена (двойственная оценка) равна 500.
Значение 5 в столбце x5 означает, что теневая цена (двойственная оценка) равна 5.
В индексной строке в 6-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Переход к КЗЛП.
F(X) = 30x1 + 30x2 + 45x3 > min при ограничениях:
- 3/50x1 + 1/25x2 + 1/50x3?3/100 2x1 + 4x2 + 3x3?31.25/5
X1 + x2 + x3=1
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции.
Сведем задачу F(X) > min к задаче F(X) > max. Для этого умножаем F(X) на (-1).
В 1-м неравенстве смысла (?) вводим базисную переменную x4. В 2-м неравенстве смысла (?) вводим базисную переменную x5.
- 3/50x1 + 1/25x2 + 1/50x3 + 1x4 + 0x5 = 3/100 2x1 + 4x2 + 3x3 + 0x4 + 1x5 = 31.25/5 1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 1
F(X) = - 30x1 - 30x2 - 45x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
Преобразуем матрицу до единичной.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,3).
Соответствующие уравнения имеют вид:
- 1/25x1 + 1/50x2 + x4 = 1/100 - x1 + x2 + x5 = 0.25000000
X1 + x2 + x3 = 1
Выразим базисные переменные через остальные:
X4 = - 1/25x1 - 1/50x2+1/100
X5 = x1 - x2+0.25000000
X3 = - x1 - x2+1
Подставим их в целевую функцию:
F(X) = - 30x1 - 30x2 - 45(- x1 - x2+1)
Или
F(X) = 15x1 + 15x2-45 > max
Система неравенств:
- 1/25x1 - 1/50x2+1/100 ? 0
X1 - x2+0.25000000 ? 0
- x1 - x2+1 ? 0
Приводим систему неравенств к следующему виду:
- 1/25x1 + 1/50x2 ? 1/100 - x1 + x2 ? 0.25000000
X1 + x2 ? 1
F(X) = 15x1 + 15x2-45 > max
Упростим систему.
X1 + 1/2x2 ? 1/4
- x1 + x2 ? 0.25000000
X1 + x2 ? 1
F(X) = 15x1 + 15x2-45 > max
Необходимо найти максимальное значение целевой функции F = 15x1+15x2-45 > max, при системе ограничений:
X1+0.5x2?0.25 |
(1) |
-x1+x2?0.25 |
(2) |
X1+x2?1 |
(3) |
X1?0 |
(4) |
X2?0 |
(5) |
Построим область допустимых решений, т. е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом) (рис.1).
Рисунок 1.- Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 15x1+15x2-45 > max.
Построим прямую, отвечающую значению функции F = 0: F = 15x1+15x2-45 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (15; 15). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
X1+0.5x2=0.25
-x1+x2=0.25
Решив систему уравнений, получим: x1 = 0.0833, x2 = 0.3333
Откуда найдем максимальное значение целевой функции:
F(X) = -15*0.0833 - 15*0.3333 +45 = 38.75
Вывод: , , , С = 38 3/4 дол. за 1 т.
Задача 2
Измените приведенные программы так, чтобы переменная, выбранная для включения в базис на очередной итерации, была первой из имеющих отрицательный коэффициент переменных. Проверьте полученную программу на задачах, приведенных в упражнениях. Приводит ли это изменение к заметному увеличению времени вычислений?
Решение
Определим минимальное значение целевой функции F(X) = 50x1 + 25x2 при следующих условиях-ограничений.
X1 + 3x2?80
- 3x1 + 4x2?19 3x1 + x2?7
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x3 со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (?) вводим базисную переменную x5 со знаком минус.
- 1x1 + 3x2-1x3 + 0x4 + 0x5 = 80 3x1 + 4x2 + 0x3-1x4 + 0x5 = 19 3x1 + 1x2 + 0x3 + 0x4-1x5 = 7
Умножим все строки на (-1) и будем искать первоначальный опорный план.
- -1x1-3x2 + 1x3 + 0x4 + 0x5 = -80 -3x1-4x2 + 0x3 + 1x4 + 0x5 = -19 -3x1-1x2 + 0x3 + 0x4 + 1x5 = -7
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,-80,-19,-7)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X3 |
-80 |
-1 |
-3 |
1 |
0 |
0 |
X4 |
-19 |
-3 |
-4 |
0 |
1 |
0 |
X5 |
-7 |
-3 |
-1 |
0 |
0 |
1 |
F(X0) |
0 |
50 |
25 |
0 |
0 |
0 |
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x3 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение и соответствует 2-му столбцу, т. е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3).
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X3 |
-80 |
-1 |
-3 |
1 |
0 |
0 |
X4 |
-19 |
-3 |
-4 |
0 |
1 |
0 |
X5 |
-7 |
-3 |
-1 |
0 |
0 |
1 |
F(X0) |
0 |
50 |
25 |
0 |
0 |
0 |
И |
50 : (-1) = -50 |
25 : (-3) = -81/3 |
- |
- |
- |
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X2 |
80/3 |
1/3 |
1 |
-1/3 |
0 |
0 |
X4 |
263/3 |
-5/3 |
0 |
-4/3 |
1 |
0 |
X5 |
59/3 |
-8/3 |
0 |
-1/3 |
0 |
1 |
F(X0) |
-2000/3 |
125/3 |
0 |
25/3 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
B |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
-80 : -3 |
-1 : -3 |
-3 : -3 |
1 : -3 |
0 : -3 |
0 : -3 |
-19-(-80 * -4):-3 |
-3-(-1 * -4):-3 |
-4-(-3 * -4):-3 |
0-(1 * -4):-3 |
1-(0 * -4):-3 |
0-(0 * -4):-3 |
-7-(-80 * -1):-3 |
-3-(-1 * -1):-3 |
-1-(-3 * -1):-3 |
0-(1 * -1):-3 |
0-(0 * -1):-3 |
1-(0 * -1):-3 |
0-(-80 * 25):-3 |
50-(-1 * 25):-3 |
25-(-3 * 25):-3 |
0-(1 * 25):-3 |
0-(0 * 25):-3 |
0-(0 * 25):-3 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X2 |
80/3 |
1/3 |
1 |
-1/3 |
0 |
0 |
X4 |
263/3 |
-5/3 |
0 |
-4/3 |
1 |
0 |
X5 |
59/3 |
-8/3 |
0 |
-1/3 |
0 |
1 |
F(X1) |
-2000/3 |
125/3 |
0 |
25/3 |
0 |
0 |
Оптимальный план можно записать так:
X2 = 262/3
F(X) = 25*262/3 = 6662/3
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 872/3
В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 192/3
Значение 412/3> 0 в столбце x1 означает, что использование x1 - не выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 81/3 в столбце x3 означает, что теневая цена (двойственная оценка) равна 81/3.
Задача 3
Фирма производит на фабрике четыре сорта изделий. Производство лимитируется временем использования станков и количеством комплектующих изделий. Известно также, что суммарное время использования станков - 90 ч в день, а комплектующих изделий может быть поставлено не более 80 в день.
Произв одственные характеристики |
Изделия | |||
1 |
2 |
3 |
4 | |
Время использования станка, ч |
1 |
3 |
8 |
4 |
Количество комплектующих |
2 |
2 |
1 |
3 |
Цена изделия, дол. |
20 |
25 |
40 |
55 |
Доход от продажи, дол. |
30 |
45 |
80 |
85 |
Ежедневное производство хj изделия j является решением следующей задачи:
Минимизировать функцию, при ограничениях
Объясните постановку этой задачи.
Приведем оптимальную таблицу в виде, в котором ее выдает компьютер:
Базис |
Значение |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
X6 |
X1 |
10 |
1 |
-1/5 |
-4 |
0 |
-3/5 |
4/5 |
X4 |
20 |
0 |
4/5 |
3 |
1 |
2/5 |
-1/5 |
-z |
70 |
0 |
1/5 |
1 |
0 |
3/5 |
1/5 |
- 1) Найдите симплекс-множители. 2) Найдите обращенный базис. 3) Фирма может увеличить время работы станков до 10 ч в день, арендуя оборудование, что будет стоить 40 дол. в день. Рентабельно ли это; если да, то какой нужен новый план производства? 4) Стоимость одного из видов сырья, используемого при производстве изделий 1 и 3 часто меняется. В данный момент стоимость сырья составляет 80 дол. за 10 кг. Изделию 1 требуется 11/4 кг на единицу сырья, а изделию 3-21/2 кг на единицу сырья. Цена этого сырья включена в приведенную выше стоимость продукции. В каких пределах может колебаться цена этого вида сырья, чтобы исходное решение осталось тем же самым? 5) Беспорядки на заводе одного из потребителей приводят к тому, что дневной выпуск изделия 4 должен быть сокращен до 15 единиц. Воспользуйтесь двойственным симплекс-методом для составления нового производственного плана.
Решение
Минимизировать функцию, при ограничениях
(прибыль, взятая с обратным знаком)
- 1) Найдем симплекс-множители 3/5, 1/5 2) Найдем обращенный базис из последней симплекс-таблицы
3) Если фирма увеличит время работы станков до 10 ч в день, арендуя оборудование, что будет стоить 40 дол. в день, то это будет рентабельно и при этом новый план производства будет таким
,
4) Цена будет колебаться в пределах
- 5) Определим минимальное значение целевой функции F(X) = - x1 - 2x2 - 4x3 - 3x4 при следующих условиях-ограничений. - x1 - 2x2 - 4x3 - 3x4?90 2x1 + 2x2 + x3 + 3x4?80
x4=15
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x5. В 2-м неравенстве смысла (?) вводим базисную переменную x6.
- -1x1-2x2-4x3-3x4 + 1x5 + 0x6 = 90 2x1 + 2x2 + 1x3 + 3x4 + 0x5 + 1x6 = 80 0x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
Введем искусственные переменные x: в 3-м равенстве вводим переменную x7;
- -1x1-2x2-4x3-3x4 + 1x5 + 0x6 + 0x7 = 90 2x1 + 2x2 + 1x3 + 3x4 + 0x5 + 1x6 + 0x7 = 80 0x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 = 15
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -1x1-2x2-4x3-3x4+Mx7 > min
План производственный метод симплекс
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 15-x4
Которые подставим в целевую функцию:
F(X) = - x1-2x2-4x3-3x4 + M(15-x4) > min
Или
F(X) = (-1)x1+(-2)x2+(-4)x3+(-3-M)x4+(15M) > min
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
-1 |
-2 |
-4 |
-3 |
1 |
0 |
0 |
2 |
2 |
1 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x5, x6, x7.
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,90,80,15)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X5 |
90 |
-1 |
-2 |
-4 |
-3 |
1 |
0 |
0 |
X6 |
80 |
2 |
2 |
1 |
3 |
0 |
1 |
0 |
X7 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
F(X0) |
15M |
1 |
2 |
4 |
3+M |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Вычислим значения Di по строкам как частное от деления: bi / ai4
И из них выберем наименьшее:
Min (- , 80 : 3 , 15 : 1 ) = 15
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Min |
X5 |
90 |
-1 |
-2 |
-4 |
-3 |
1 |
0 |
0 |
- |
X6 |
80 |
2 |
2 |
1 |
3 |
0 |
1 |
0 |
262/3 |
X7 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
15 |
F(X1) |
15M |
1 |
2 |
4 |
3+M |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 1 войдет переменная x4.
Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x4 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x4 и столбец x4.
Представим расчет каждого элемента в виде таблицы:
B |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
90-(15 * -3):1 |
-1-(0 * -3):1 |
-2-(0 * -3):1 |
-4-(0 * -3):1 |
-3-(1 * -3):1 |
1-(0 * -3):1 |
0-(0 * -3):1 |
0-(1 * -3):1 |
80-(15 * 3):1 |
2-(0 * 3):1 |
2-(0 * 3):1 |
1-(0 * 3):1 |
3-(1 * 3):1 |
0-(0 * 3):1 |
1-(0 * 3):1 |
0-(1 * 3):1 |
15 : 1 |
0 : 1 |
0 : 1 |
0 : 1 |
1 : 1 |
0 : 1 |
0 : 1 |
1 : 1 |
(0)-(15 * (3+M)):1 |
(1)-(0 * (3+M)):1 |
(2)-(0 * (3+M)):1 |
(4)-(0 * (3+M)):1 |
(3+M)-(1 * (3+M)):1 |
(0)-(0 * (3+M)):1 |
(0)-(0 * (3+M)):1 |
(0)-(1 * (3+M)):1 |
Получаем новую симплекс-таблицу:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X5 |
135 |
-1 |
-2 |
-4 |
0 |
1 |
0 |
3 |
X6 |
35 |
2 |
2 |
1 |
0 |
0 |
1 |
-3 |
X4 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
F(X1) |
-45 |
1 |
2 |
4 |
0 |
0 |
0 |
-3-M |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
И из них выберем наименьшее:
Min (- , 35 : 1 , - ) = 35
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Min |
X5 |
135 |
-1 |
-2 |
-4 |
0 |
1 |
0 |
3 |
- |
X6 |
35 |
2 |
2 |
1 |
0 |
0 |
1 |
-3 |
35 |
X4 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
- |
F(X2) |
-45 |
1 |
2 |
4 |
0 |
0 |
0 |
-3-M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
135-(35 * -4):1 |
-1-(2 * -4):1 |
-2-(2 * -4):1 |
-4-(1 * -4):1 |
0-(0 * -4):1 |
1-(0 * -4):1 |
0-(1 * -4):1 |
3-(-3 * -4):1 |
35 : 1 |
2 : 1 |
2 : 1 |
1 : 1 |
0 : 1 |
0 : 1 |
1 : 1 |
-3 : 1 |
15-(35 * 0):1 |
0-(2 * 0):1 |
0-(2 * 0):1 |
0-(1 * 0):1 |
1-(0 * 0):1 |
0-(0 * 0):1 |
0-(1 * 0):1 |
1-(-3 * 0):1 |
(-3-M)-(35 * (4)):1 |
(1)-(2 * (4)):1 |
(2)-(2 * (4)):1 |
(4)-(1 * (4)):1 |
(0)-(0 * (4)):1 |
(0)-(0 * (4)):1 |
(0)-(1 * (4)):1 |
(-3-M)-(-3 * (4)):1 |
Получаем новую симплекс-таблицу:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X5 |
275 |
7 |
6 |
0 |
0 |
1 |
4 |
-9 |
X3 |
35 |
2 |
2 |
1 |
0 |
0 |
1 |
-3 |
X4 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
F(X2) |
-185 |
-7 |
-6 |
0 |
0 |
0 |
-4 |
9-M |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X5 |
275 |
7 |
6 |
0 |
0 |
1 |
4 |
-9 |
X3 |
35 |
2 |
2 |
1 |
0 |
0 |
1 |
-3 |
X4 |
15 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
F(X3) |
-185 |
-7 |
-6 |
0 |
0 |
0 |
-4 |
9-M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
X3 = 35
X4 = 15
F(X) = -4*35 -3*15 = -185, z=185
Вывод: 1) 3/5, 1/5; 2) ; 3) да, , ; 4) , где - цена сырья; 5) , , .
Задача 4
8. Четыре сталелитейных завода I, II, III и IV производят еженедельно соответственно 950, 300, 1350 и 450 т стали определенного сорта. Стальные болванки должны быть переданы потребителям А, В, С, D, Е, еженедельные запросы которых составляют соответственно 250, 1000, 700, 650 и 450 т стали.
Стоимость транспортировки от заводов к потребителям в тоннах приведена в таблице:
Завод |
Потребитель | ||||
А |
В |
С |
D |
Е | |
1 |
12 |
16 |
21 |
19 |
32 |
2 |
4 |
4 |
9 |
5 |
24 |
3 |
3 |
8 |
14 |
10 |
26 |
4 |
24 |
33 |
36 |
34 |
49 |
Какой нужно составить план распределения стальных болванок, чтобы минимизировать общую стоимость.
Решение
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21 |
19 |
32 |
950 |
2 |
4 |
4 |
9 |
5 |
24 |
300 |
3 |
3 |
8 |
14 |
10 |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49 |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим необходимое и достаточное условие разрешимости задачи.
- ?a = 950 + 300 + 1350 + 450 = 3050 ?b = 250 + 1000 + 700 + 650 + 450 = 3050
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21 |
19 |
32 |
950 |
2 |
4 |
4 |
9 |
5 |
24 |
300 |
3 |
3 |
8 |
14 |
10 |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49 |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3[250] |
8[700] |
14 |
10[400] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*700 + 19*250 + 4*300 + 3*250 + 8*700 + 10*400 + 49*450 = 53050
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4[250] |
4[50] |
9 |
5 |
24 |
300 |
3 |
3 |
8[950] |
14 |
10[400] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*700 + 19*250 + 4*250 + 4*50 + 8*950 + 10*400 + 49*450 = 54300
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3[250] |
8[700] |
14 |
10[400] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*700 + 19*250 + 4*300 + 3*250 + 8*700 + 10*400 + 49*450 = 53050
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*700 + 19*250 + 5*300 + 3*250 + 8*1000 + 10*100 + 49*450 = 52750
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*700 + 19*250 + 5*300 + 3*250 + 8*1000 + 10*100 + 49*450 = 52750
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[400] |
19[550] |
32 |
950 |
2 |
4 |
4 |
9[300] |
5 |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 21*400 + 19*550 + 9*300 + 3*250 + 8*1000 + 10*100 + 49*450 = 53350
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16[250] |
21[700] |
19 |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3[250] |
8[450] |
14 |
10[650] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 16*250 + 21*700 + 4*300 + 3*250 + 8*450 + 10*650 + 49*450 = 52800
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12[250] |
16 |
21[700] |
19 |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3 |
8[700] |
14 |
10[650] |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 12*250 + 21*700 + 4*300 + 8*700 + 10*650 + 49*450 = 53050
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16[300] |
21 |
19[650] |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3[250] |
8[400] |
14[700] |
10 |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 16*300 + 19*650 + 4*300 + 3*250 + 8*400 + 14*700 + 49*450 = 54150
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16[300] |
21 |
19[650] |
32 |
950 |
2 |
4 |
4[300] |
9 |
5 |
24 |
300 |
3 |
3[250] |
8[400] |
14[700] |
10 |
26 |
1350 |
4 |
24 |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 16*300 + 19*650 + 4*300 + 3*250 + 8*400 + 14*700 + 49*450 = 54150
На протяжении многих итераций так и не удалось получить невырожденный план.
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;1);
Возвращаемся к плану №3
1 |
2 |
3 |
4 |
5 | |
1 |
12[0] |
16 |
21[700] |
19[250] |
32 |
2 |
4 |
4 |
9 |
5[300] |
24 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
4 |
24 |
33 |
36 |
34 |
49[450] |
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v1 = 12; 0 + v1 = 12; v1 = 12
U3 + v1 = 3; 12 + u3 = 3; u3 = -9
U3 + v2 = 8; -9 + v2 = 8; v2 = 17
U3 + v4 = 10; -9 + v4 = 10; v4 = 19
U2 + v4 = 5; 19 + u2 = 5; u2 = -14
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
U4 + v5 = 49; 0 + u4 = 49; u4 = 49
U4 + v5 = 49; 49 + v5 = 49; v5 = 0
V1=12 |
V2=17 |
V3=21 |
V4=19 |
V5=0 | |
U1=0 |
12[0] |
16 |
21[700] |
19[250] |
32 |
U2=-14 |
4 |
4 |
9 |
5[300] |
24 |
U3=-9 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
U4=49 |
24 |
33 |
36 |
34 |
49[450] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
- (1;2): 0 + 17 > 16; ?12 = 0 + 17 - 16 = 1 (4;1): 49 + 12 > 24; ?41 = 49 + 12 - 24 = 37 (4;2): 49 + 17 > 33; ?42 = 49 + 17 - 33 = 33 (4;3): 49 + 21 > 36; ?43 = 49 + 21 - 36 = 34 (4;4): 49 + 19 > 34; ?44 = 49 + 19 - 34 = 34, max(1,37,33,34,34) = 37
Выбираем максимальную оценку свободной клетки (4;1): 24
Для этого в перспективную клетку (4;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12[0] |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24[+] |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Цикл приведен в таблице (4,1).
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12[0] |
16 |
21[700] |
19[250] |
32 |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24[0] |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v1 = 12; 0 + v1 = 12; v1 = 12
U3 + v1 = 3; 12 + u3 = 3; u3 = -9
U3 + v2 = 8; -9 + v2 = 8; v2 = 17
U3 + v4 = 10; -9 + v4 = 10; v4 = 19
U2 + v4 = 5; 19 + u2 = 5; u2 = -14
U4 + v1 = 24; 12 + u4 = 24; u4 = 12
U4 + v5 = 49; 12 + v5 = 49; v5 = 37
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
V1=12 |
V2=17 |
V3=21 |
V4=19 |
V5=37 | |
U1=0 |
12[0] |
16 |
21[700] |
19[250] |
32 |
U2=-14 |
4 |
4 |
9 |
5[300] |
24 |
U3=-9 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
U4=12 |
24[0] |
33 |
36 |
34 |
49[450] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
- (1;2): 0 + 17 > 16; ?12 = 0 + 17 - 16 = 1 (1;5): 0 + 37 > 32; ?15 = 0 + 37 - 32 = 5 (3;5): -9 + 37 > 26; ?35 = -9 + 37 - 26 = 2
Max(1,5,2) = 5
Выбираем максимальную оценку свободной клетки (1;5): 32
Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12[0][-] |
16 |
21[700] |
19[250] |
32[+] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24[0][+] |
33 |
36 |
34 |
49[450][-] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Цикл приведен в таблице (1,5 > 1,1 > 4,1 > 4,5).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 1) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250] |
32[0] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
1350 |
4 |
24[0] |
33 |
36 |
34 |
49[450] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
U1 + v4 = 19; 0 + v4 = 19; v4 = 19
U2 + v4 = 5; 19 + u2 = 5; u2 = -14
U3 + v4 = 10; 19 + u3 = 10; u3 = -9
U3 + v1 = 3; -9 + v1 = 3; v1 = 12
U4 + v1 = 24; 12 + u4 = 24; u4 = 12
U4 + v5 = 49; 12 + v5 = 49; v5 = 37
U3 + v2 = 8; -9 + v2 = 8; v2 = 17
V1=12 |
V2=17 |
V3=21 |
V4=19 |
V5=37 | |
U1=0 |
12 |
16 |
21[700] |
19[250] |
32[0] |
U2=-14 |
4 |
4 |
9 |
5[300] |
24 |
U3=-9 |
3[250] |
8[1000] |
14 |
10[100] |
26 |
U4=12 |
24[0] |
33 |
36 |
34 |
49[450] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
- (1;2): 0 + 17 > 16; ?12 = 0 + 17 - 16 = 1 (1;5): 0 + 37 > 32; ?15 = 0 + 37 - 32 = 5 (3;5): -9 + 37 > 26; ?35 = -9 + 37 - 26 = 2
Max(1,5,2) = 5
Выбираем максимальную оценку свободной клетки (1;5): 32
Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[250][-] |
32[0][+] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3[250][-] |
8[1000] |
14 |
10[100][+] |
26 |
1350 |
4 |
24[0][+] |
33 |
36 |
34 |
49[450][-] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Цикл приведен в таблице (1,5 > 1,4 > 3,4 > 3,1 > 4,1 > 4,5).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 1) = 250. Прибавляем 250 к объемам грузов, стоящих в плюсовых клетках и вычитаем 250 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700] |
19[0] |
32[250] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3 |
8[1000] |
14 |
10[350] |
26 |
1350 |
4 |
24[250] |
33 |
36 |
34 |
49[200] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
U1 + v4 = 19; 0 + v4 = 19; v4 = 19
U2 + v4 = 5; 19 + u2 = 5; u2 = -14
U3 + v4 = 10; 19 + u3 = 10; u3 = -9
U3 + v2 = 8; -9 + v2 = 8; v2 = 17
U1 + v5 = 32; 0 + v5 = 32; v5 = 32
U4 + v5 = 49; 32 + u4 = 49; u4 = 17
U4 + v1 = 24; 17 + v1 = 24; v1 = 7
V1=7 |
V2=17 |
V3=21 |
V4=19 |
V5=32 | |
U1=0 |
12 |
16 |
21[700] |
19[0] |
32[250] |
U2=-14 |
4 |
4 |
9 |
5[300] |
24 |
U3=-9 |
3 |
8[1000] |
14 |
10[350] |
26 |
U4=17 |
24[250] |
33 |
36 |
34 |
49[200] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
- (1;2): 0 + 17 > 16; ?12 = 0 + 17 - 16 = 1 (4;2): 17 + 17 > 33; ?42 = 17 + 17 - 33 = 1 (4;3): 17 + 21 > 36; ?43 = 17 + 21 - 36 = 2 (4;4): 17 + 19 > 34; ?44 = 17 + 19 - 34 = 2
Max(1,1,2,2) = 2
Выбираем максимальную оценку свободной клетки (4;3): 36
Для этого в перспективную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[700][-] |
19[0] |
32[250][+] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3 |
8[1000] |
14 |
10[350] |
26 |
1350 |
4 |
24[250] |
33 |
36[+] |
34 |
49[200][-] |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Цикл приведен в таблице (4,3 > 4,5 > 1,5 > 1,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (4, 5) = 200. Прибавляем 200 к объемам грузов, стоящих в плюсовых клетках и вычитаем 200 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16 |
21[500] |
19[0] |
32[450] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3 |
8[1000] |
14 |
10[350] |
26 |
1350 |
4 |
24[250] |
33 |
36[200] |
34 |
49 |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
U4 + v3 = 36; 21 + u4 = 36; u4 = 15
U4 + v1 = 24; 15 + v1 = 24; v1 = 9
U1 + v4 = 19; 0 + v4 = 19; v4 = 19
U2 + v4 = 5; 19 + u2 = 5; u2 = -14
U3 + v4 = 10; 19 + u3 = 10; u3 = -9
U3 + v2 = 8; -9 + v2 = 8; v2 = 17
U1 + v5 = 32; 0 + v5 = 32; v5 = 32
V1=9 |
V2=17 |
V3=21 |
V4=19 |
V5=32 | |
U1=0 |
12 |
16 |
21[500] |
19[0] |
32[450] |
U2=-14 |
4 |
4 |
9 |
5[300] |
24 |
U3=-9 |
3 |
8[1000] |
14 |
10[350] |
26 |
U4=15 |
24[250] |
33 |
36[200] |
34 |
49 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 17 > 16; ?12 = 0 + 17 - 16 = 1
Выбираем максимальную оценку свободной клетки (1;2): 16
Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16[+] |
21[500] |
19[0][-] |
32[450] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3 |
8[1000][-] |
14 |
10[350][+] |
26 |
1350 |
4 |
24[250] |
33 |
36[200] |
34 |
49 |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Цикл приведен в таблице (1,2 > 1,4 > 3,4 > 3,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
12 |
16[0] |
21[500] |
19 |
32[450] |
950 |
2 |
4 |
4 |
9 |
5[300] |
24 |
300 |
3 |
3 |
8[1000] |
14 |
10[350] |
26 |
1350 |
4 |
24[250] |
33 |
36[200] |
34 |
49 |
450 |
Потребности |
250 |
1000 |
700 |
650 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
U1 + v2 = 16; 0 + v2 = 16; v2 = 16
U3 + v2 = 8; 16 + u3 = 8; u3 = -8
U3 + v4 = 10; -8 + v4 = 10; v4 = 18
U2 + v4 = 5; 18 + u2 = 5; u2 = -13
U1 + v3 = 21; 0 + v3 = 21; v3 = 21
U4 + v3 = 36; 21 + u4 = 36; u4 = 15
U4 + v1 = 24; 15 + v1 = 24; v1 = 9
U1 + v5 = 32; 0 + v5 = 32; v5 = 32
V1=9 |
V2=16 |
V3=21 |
V4=18 |
V5=32 | |
U1=0 |
12 |
16[0] |
21[500] |
19 |
32[450] |
U2=-13 |
4 |
4 |
9 |
5[300] |
24 |
U3=-8 |
3 |
8[1000] |
14 |
10[350] |
26 |
U4=15 |
24[250] |
33 |
36[200] |
34 |
49 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ? cij.
Минимальные затраты составят:
F(x) = 21*500 + 32*450 + 5*300 + 8*1000 + 10*350 + 24*250 + 36*200 = 51100
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 3-й магазин (500), в 5-й магазин (450)
Из 2-го склада необходимо весь груз направить в 4-й магазин
Из 3-го склада необходимо груз направить в 2-й магазин (1000), в 4-й магазин (350)
Из 4-го склада необходимо груз направить в 1-й магазин (250), в 3-й магазин (200)
Задача имеет множество оптимальных планов, поскольку оценка для (1;2) равна 0.
Ответ: Заводы посылают потребителям стали: I - 500 т С, 450 т Е; II - 300 т D; III - 1000 т В, 350 т D, IV - 250 т А, 200 т С.
Задача 5
8. Компания реализует продукцию в пяти географических областях. Покупательные способности жителей этих областей оцениваются следующим образом:
Область |
1 |
2 |
3 |
4 |
5 |
Покупательная способность |
80000 |
60000 |
50000 |
40000 |
20000 |
Профессиональный уровень пяти продавцов различен. Предполагается, что доля реализуемых покупательных способностей составляет:
Продавец |
А |
В |
С |
D |
Е |
Доля |
0,7 |
0,6 |
0,5 |
0,45 |
0,4 |
Как следует распределить продавцов по областям, чтобы максимизировать количество проданной продукции?
Решение
Исходная матрица имеет вид:
56000 |
48000 |
40000 |
36000 |
32000 |
42000 |
36000 |
30000 |
27000 |
24000 |
35000 |
30000 |
25000 |
225000 |
20000 |
28000 |
24000 |
20000 |
18000 |
16000 |
14000 |
12000 |
10000 |
9000 |
8000 |
Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
24000 |
16000 |
8000 |
4000 |
0 |
32000 |
18000 |
12000 |
6000 |
3000 |
0 |
24000 |
15000 |
10000 |
5000 |
205000 |
0 |
20000 |
12000 |
8000 |
4000 |
2000 |
0 |
16000 |
6000 |
4000 |
2000 |
1000 |
0 |
8000 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
18000 |
12000 |
6000 |
3000 |
0 |
12000 |
8000 |
4000 |
2000 |
0 |
9000 |
6000 |
3000 |
204000 |
0 |
6000 |
4000 |
2000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
6000 |
4000 |
2000 |
1000 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 5), (3; 5), (4; 5), (5; 5)
В итоге получаем следующую матрицу:
18000 |
12000 |
6000 |
3000 |
[0] |
12000 |
8000 |
4000 |
2000 |
[-0-] |
9000 |
6000 |
3000 |
204000 |
[-0-] |
6000 |
4000 |
2000 |
1000 |
[-0-] |
0 |
0 |
0 |
0 |
[-0-] |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 1), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Строку 5,
Столбец 5,
Получаем сокращенную матрицу (элементы выделены):
18000 |
12000 |
6000 |
3000 |
0 |
12000 |
8000 |
4000 |
2000 |
0 |
9000 |
6000 |
3000 |
204000 |
0 |
6000 |
4000 |
2000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
Минимальный элемент сокращенной матрицы (min(18000, 12000, 6000, 3000, 12000, 8000, 4000, 2000, 9000, 6000, 3000, 204000, 6000, 4000, 2000, 1000) = 1000) вычитаем из всех ее элементов:
17000 |
11000 |
5000 |
2000 |
0 |
11000 |
7000 |
3000 |
1000 |
0 |
8000 |
5000 |
2000 |
203000 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
17000 |
11000 |
5000 |
2000 |
0 |
11000 |
7000 |
3000 |
1000 |
0 |
8000 |
5000 |
2000 |
203000 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
1000 |
Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
17000 |
11000 |
5000 |
2000 |
0 |
0 |
11000 |
7000 |
3000 |
1000 |
0 |
0 |
8000 |
5000 |
2000 |
203000 |
0 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
17000 |
11000 |
5000 |
2000 |
0 |
11000 |
7000 |
3000 |
1000 |
0 |
8000 |
5000 |
2000 |
203000 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
1000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 5), (3; 5), (4; 5)
В итоге получаем следующую матрицу:
17000 |
11000 |
5000 |
2000 |
[0] |
11000 |
7000 |
3000 |
1000 |
[-0-] |
8000 |
5000 |
2000 |
203000 |
[-0-] |
5000 |
3000 |
1000 |
0 |
[-0-] |
0 |
0 |
0 |
0 |
1000 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 1), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Строку 5,
Столбец 5,
Строку 4,
Получаем сокращенную матрицу (элементы выделены):
17000 |
11000 |
5000 |
2000 |
0 |
11000 |
7000 |
3000 |
1000 |
0 |
8000 |
5000 |
2000 |
203000 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
1000 |
Минимальный элемент сокращенной матрицы (min(17000, 11000, 5000, 2000, 11000, 7000, 3000, 1000, 8000, 5000, 2000, 203000) = 1000) вычитаем из всех ее элементов:
16000 |
10000 |
4000 |
1000 |
0 |
10000 |
6000 |
2000 |
0 |
0 |
7000 |
4000 |
1000 |
202000 |
0 |
5000 |
3000 |
1000 |
0 |
0 |
0 |
0 |
0 |
0 |
1000 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
16000 |
10000 |
4000 |
1000 |
0 |
10000 |
6000 |
2000 |
0 |
0 |
7000 |
4000 |
1000 |
202000 |
0 |
5000 |
3000 |
1000 |
0 |
1000 |
0 |
0 |
0 |
0 |
2000 |
Шаг №3.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
16000 |
10000 |
4000 |
1000 |
0 |
0 |
10000 |
6000 |
2000 |
0 |
0 |
0 |
7000 |
4000 |
1000 |
202000 |
0 |
0 |
5000 |
3000 |
1000 |
0 |
1000 |
0 |
0 |
0 |
0 |
0 |
2000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
16000 |
10000 |
4000 |
1000 |
0 |
10000 |
6000 |
2000 |
0 |
0 |
7000 |
4000 |
1000 |
202000 |
0 |
5000 |
3000 |
1000 |
0 |
1000 |
0 |
0 |
0 |
0 |
2000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 4), (5; 4)
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 4), (5; 4)
В итоге получаем следующую матрицу:
16000 |
10000 |
4000 |
1000 |
[0] |
10000 |
6000 |
2000 |
[0] |
[-0-] |
7000 |
4000 |
1000 |
202000 |
[-0-] |
5000 |
3000 |
1000 |
[-0-] |
1000 |
0 |
0 |
0 |
[-0-] |
2000 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Строку 5,
Столбец 5,
Столбец 4,
Получаем сокращенную матрицу (элементы выделены):
16000 |
10000 |
4000 |
1000 |
0 |
10000 |
6000 |
2000 |
0 |
0 |
7000 |
4000 |
1000 |
202000 |
0 |
5000 |
3000 |
1000 |
0 |
1000 |
0 |
0 |
0 |
0 |
2000 |
Минимальный элемент сокращенной матрицы (min(16000, 10000, 4000, 10000, 6000, 2000, 7000, 4000, 1000, 5000, 3000, 1000) = 1000) вычитаем из всех ее элементов:
15000 |
9000 |
3000 |
1000 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
6000 |
3000 |
0 |
202000 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
0 |
2000 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
15000 |
9000 |
3000 |
1000 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
6000 |
3000 |
0 |
202000 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
1000 |
3000 |
Шаг №4.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
15000 |
9000 |
3000 |
1000 |
0 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
0 |
6000 |
3000 |
0 |
202000 |
0 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
0 |
1000 |
3000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
15000 |
9000 |
3000 |
1000 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
6000 |
3000 |
0 |
202000 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
1000 |
3000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (5; 3)
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (5; 3)
Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (5; 3)
В итоге получаем следующую матрицу:
15000 |
9000 |
3000 |
1000 |
[0] |
9000 |
5000 |
1000 |
[0] |
[-0-] |
6000 |
3000 |
[0] |
202000 |
[-0-] |
4000 |
2000 |
[-0-] |
[-0-] |
1000 |
0 |
0 |
[-0-] |
1000 |
3000 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Строку 5,
Столбец 5,
Строку 4,
Столбец 3,
Строку 2,
Получаем сокращенную матрицу (элементы выделены):
15000 |
9000 |
3000 |
1000 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
6000 |
3000 |
0 |
202000 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
1000 |
3000 |
Минимальный элемент сокращенной матрицы (min(15000, 9000, 1000, 6000, 3000, 202000) = 1000) вычитаем из всех ее элементов:
14000 |
8000 |
3000 |
0 |
0 |
9000 |
5000 |
1000 |
0 |
0 |
5000 |
2000 |
0 |
201000 |
0 |
4000 |
2000 |
0 |
0 |
1000 |
0 |
0 |
0 |
1000 |
3000 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
14000 |
8000 |
3000 |
0 |
0 |
9000 |
5000 |
2000 |
0 |
1000 |
5000 |
2000 |
0 |
201000 |
0 |
4000 |
2000 |
1000 |
0 |
2000 |
0 |
0 |
1000 |
1000 |
4000 |
Шаг №5.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
14000 |
8000 |
3000 |
0 |
0 |
0 |
9000 |
5000 |
2000 |
0 |
1000 |
0 |
5000 |
2000 |
0 |
201000 |
0 |
0 |
4000 |
2000 |
1000 |
0 |
2000 |
0 |
0 |
0 |
1000 |
1000 |
4000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
14000 |
8000 |
3000 |
0 |
0 |
9000 |
5000 |
2000 |
0 |
1000 |
5000 |
2000 |
0 |
201000 |
0 |
4000 |
2000 |
1000 |
0 |
2000 |
0 |
0 |
1000 |
1000 |
4000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем.
В итоге получаем следующую матрицу:
14000 |
8000 |
3000 |
[-0-] |
[0] |
9000 |
5000 |
2000 |
[0] |
1000 |
5000 |
2000 |
[0] |
201000 |
[-0-] |
4000 |
2000 |
1000 |
[-0-] |
2000 |
0 |
0 |
1000 |
1000 |
4000 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Столбец 4, строку 3, строку 5, столбец 5,
Получаем сокращенную матрицу (элементы выделены):
14000 |
8000 |
3000 |
0 |
0 |
9000 |
5000 |
2000 |
0 |
1000 |
5000 |
2000 |
0 |
201000 |
0 |
4000 |
2000 |
1000 |
0 |
2000 |
0 |
0 |
1000 |
1000 |
4000 |
Минимальный элемент сокращенной матрицы (min(14000, 8000, 3000, 9000, 5000, 2000, 4000, 2000, 1000) = 1000) вычитаем из всех ее элементов:
13000 |
7000 |
2000 |
0 |
0 |
8000 |
4000 |
1000 |
0 |
1000 |
5000 |
2000 |
0 |
201000 |
0 |
3000 |
1000 |
0 |
0 |
2000 |
0 |
0 |
1000 |
1000 |
4000 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
13000 |
7000 |
2000 |
0 |
0 |
8000 |
4000 |
1000 |
0 |
1000 |
5000 |
2000 |
0 |
202000 |
1000 |
3000 |
1000 |
0 |
0 |
2000 |
0 |
0 |
1000 |
2000 |
5000 |
Шаг №6.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
13000 |
7000 |
2000 |
0 |
0 |
0 |
8000 |
4000 |
1000 |
0 |
1000 |
0 |
5000 |
2000 |
0 |
202000 |
1000 |
0 |
3000 |
1000 |
0 |
0 |
2000 |
0 |
0 |
0 |
1000 |
2000 |
5000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
13000 |
7000 |
2000 |
0 |
0 |
8000 |
4000 |
1000 |
0 |
1000 |
5000 |
2000 |
0 |
202000 |
1000 |
3000 |
1000 |
0 |
0 |
2000 |
0 |
0 |
1000 |
2000 |
5000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3)
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3)
Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3)
В итоге получаем следующую матрицу:
13000 |
7000 |
2000 |
[-0-] |
[0] |
8000 |
4000 |
1000 |
[0] |
1000 |
5000 |
2000 |
[0] |
202000 |
1000 |
3000 |
1000 |
[-0-] |
[-0-] |
2000 |
0 |
0 |
1000 |
2000 |
5000 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Столбец 4,
Строку 5,
Столбец 3,
Строку 1,
Получаем сокращенную матрицу (элементы выделены):
13000 |
7000 |
2000 |
0 |
0 |
8000 |
4000 |
1000 |
0 |
1000 |
5000 |
2000 |
0 |
202000 |
1000 |
3000 |
1000 |
0 |
0 |
2000 |
0 |
0 |
1000 |
2000 |
5000 |
Минимальный элемент сокращенной матрицы (min(8000, 4000, 1000, 5000, 2000, 1000, 3000, 1000, 2000) = 1000) вычитаем из всех ее элементов:
13000 |
7000 |
2000 |
0 |
0 |
7000 |
3000 |
1000 |
0 |
0 |
4000 |
1000 |
0 |
202000 |
0 |
2000 |
0 |
0 |
0 |
1000 |
0 |
0 |
1000 |
2000 |
5000 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
13000 |
7000 |
3000 |
1000 |
0 |
7000 |
3000 |
1000 |
0 |
0 |
4000 |
1000 |
0 |
202000 |
0 |
2000 |
0 |
0 |
0 |
1000 |
0 |
0 |
2000 |
3000 |
5000 |
Шаг №7.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
13000 |
7000 |
3000 |
1000 |
0 |
0 |
7000 |
3000 |
1000 |
0 |
0 |
0 |
4000 |
1000 |
0 |
202000 |
0 |
0 |
2000 |
0 |
0 |
0 |
1000 |
0 |
0 |
0 |
2000 |
3000 |
5000 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
13000 |
7000 |
3000 |
1000 |
0 |
7000 |
3000 |
1000 |
0 |
0 |
4000 |
1000 |
0 |
202000 |
0 |
2000 |
0 |
0 |
0 |
1000 |
0 |
0 |
2000 |
3000 |
5000 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 4 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (5, 1). Другие нули в строке 5 и столбце 1 вычеркиваем.
В итоге получаем следующую матрицу:
13000 |
7000 |
3000 |
1000 |
[0] |
7000 |
3000 |
1000 |
[0] |
[-0-] |
4000 |
1000 |
[0] |
202000 |
[-0-] |
2000 |
[0] |
[-0-] |
[-0-] |
1000 |
[0] |
[-0-] |
2000 |
3000 |
5000 |
Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:
13000 |
7000 |
3000 |
1000 |
0 |
7000 |
3000 |
1000 |
0 |
0 |
4000 |
1000 |
0 |
202000 |
0 |
2000 |
0 |
0 |
0 |
1000 |
0 |
0 |
2000 |
3000 |
5000 |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
13000 |
7000 |
3000 |
1000 |
[0] |
7000 |
3000 |
1000 |
[0] |
[-0-] |
4000 |
1000 |
[0] |
202000 |
[-0-] |
2000 |
[0] |
[-0-] |
[-0-] |
1000 |
[0] |
[-0-] |
2000 |
3000 |
5000 |
Cmin = 32000 + 27000 + 25000 + 24000 + 14000 = 122000
Вывод: Направить: А в область 1, В в область 2, С в область 3, D в область 6, Е в область 5.
Задача 6
8. Была предложена следующая простая модель сельскохозяйственного производства на Нарвских островах для внешнего рынка. Имеется три основные культуры, растущие в этом климате, и выращиваться они могут на одном из двух типов пахотных земель. В настоящее время для обработки пригодны 14 * 10 акров земли типа I и 12 * 10 акров земли типа II. Разные типы культур по-разному растут на разных землях, и подсчитано, что чистый урожай культуры i с земли типа j составляет Rij.
I |
Rij | |
J=I |
J=II | |
1 |
6 |
6 |
2 |
8 |
5 |
3 |
4 |
5 |
Все культуры требуют дополнительного орошения (ирригационного). Имеющаяся ирригационная система обеспечивает 56 * 10 м3 воды в год. Для одного акра культуры i, выращенной на земле типа j, требуется Wij м3 воды в год:
I |
Wij | |
J=I |
J=II | |
1 |
2 |
3 |
2 |
3 |
3 |
3 |
3 |
2 |
Население, занятое в сельском хозяйстве, составляет 7 * 10 человек. Чтобы получить урожаи 1, 2, 3 с каждых 10 акров земли, для выполнения различных работ по выращиванию культур в течение 1 года требуется соответственно 2, 1, 3 человека. Описанная модель приводит к следующей задаче линейного программирования:
Пусть все переменные неотрицательны и удовлетворяют условиям
Минимизируйте функцию
Объясните физический смысл всех переменных, входящих в задачу. Найдите базис, обращение базиса, симплекс-множители этого базиса, решите эту задачу улучшенным симплекс-методом.
Задача была решена на ЭВМ; решение было выдано в виде таблицы
Базис |
Значение |
Обращение | |||
X21 |
4 |
-2 |
-2 |
1 |
0 |
X11 |
10 |
3 |
2 |
-1 |
0 |
X32 |
12 |
0 |
1 |
0 |
0 |
Z |
10 |
-4 |
-5 |
1 |
1 |
Симплекс-множители |
2 |
1 |
2 |
0 |
Значение целевой функции равно 152.
- А) Прокомментируйте это решение. Б) Рассматриваются план вырубки лесов, реализация которого даст дополнительные земли типа I, и пути принципиального улучшения ирригационной системы. Каково значение этих перемен с точки зрения экономики сельского хозяйства? В) Предложена четвертая культура, которая может выращиваться только на земле типа II. Для нее требуются 2 м3 воды на 1 акр и весьма большие затраты труда - 4 человека на 10 акров. В текущих единицах на мировом рынке она принесла бы б единиц чистого урожая с 1 акра. Стоит ли ее выращивать? А) Занять акров культуры 1 на земле типа I, акров культуры 2 на земле типа I, акров культуры 3 на земле типа II. Все земельные и водные ресурсы используются полностью, однако остаются не занятыми человек, более 14 % доступной рабочей силы. Б) Каждые акров земли типа I дают 2 дополнительные единицы дохода. Каждые единиц воды дают 2 дополнительные единицы дохода.
В) Да. Это увеличивает доход на единиц (с 152 до ). В новом решении выращивается - акров культуры 1 на земле типа I, акров культуры 2 на земле типа I и акров новой культуры на земле типа II. Теперь рабочая сила используется полностью, а земля типа II - не полностью.
Задача 7.
Покажите, что утверждение, обратное сформулированному в упр. 7, неверно.
Постройте контрпример.
Решение
Прямая задача: найти такие, , что
И функция имеет минимальное значение; допустимого решения нет. Двойственная задача: найти такие, , что
И функция имеет максимальное значение; допустимого решения нет.
Литература
- 1. Вентцель Е. С. Исследование операций: Задачи, принципы, методология. Учебное пособие. - М.: Дрофа, 2004. 2. Колемаев В. А. Математическая экономика. Учебник для вузов. - М.: ЮНИТИ-ДАНА, 2005. 3. Кремер Н. Ш. Исследование операций в экономике. - М.: ЮНИТИ, 2006. 4. Орехов Н. А., Левин А. Г., Горбунов Е. А. Математические методы и мо-дели в экономике. Учебное пособие для вузов / Под ред. проф. Н. А. Орехова - М.: ЮНИТИ-ДАНА, 2004.
Похожие статьи
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Топологический элементный анализ - Системная революция и принцип дуального управления
Независимые от системы элементы формально выглядят как изолированные вершины графа структуры (ее симплекса). Если некоторый элемент на всех структурах...
-
Регрессионный анализ данных - Статистическое исследование инвестиционной деятельности в регионе
Если расчет корреляции характеризует силу связи между переменными, то регрессионный анализ служит для определения вида этой связи и дает возможность для...
-
Первичный статистический анализ данных Для анализа инвестиционной деятельности в основной капитал был использован статистический ежегодник...
-
Моделирование в условиях противодействия, игровые модели - Основы теории систем и системного анализа
Как уже неоднократно отмечалось, системный анализ невозможен без учета взаимодействий данной системы с внешней средой. Ранее упоминалась необходимость...
-
В нашем анализе данных показателей рынков под "самородками" понимаются зависимости, отражающие степень эффективности рекламных кампаний. Эксперты часами...
-
После проведения регрессионного анализа получается модель объекта исследований в виде некоторой функции. В простейшем случае линейной регрессии она имеет...
-
С системной точки зрения важно иметь в виду, что мы оцениваем вещи, явления или события не сами по себе, а в их ситуационном проявлении, т. е. по их...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Методы непараметрической статистики - Основы теории систем и системного анализа
Использование классических распределений случайных величин обычно называют "параметрической статистикой" - мы делаем предположение о том, что...
-
1. Ознакомиться с методами регрессионного анализа и планирования эксперимента; 2. Определить коэффициенты статистической характеристики объекта...
-
Топологический анализ связей и отношений - Системная революция и принцип дуального управления
Среди основных морфологических типов связей и отношений, определяющих внутреннее строение дискретных систем, прежде всего следует выделить...
-
Анализ временных рядов - Статистическое исследование инвестиционной деятельности в регионе
Временной ряд - Это последовательность чисел; его элементы - это значения некоторого протекающего во времени процесса. Проведем анализ временных рядов....
-
Моделирование системы в условиях неопределенности - Основы теории систем и системного анализа
Как уже отмечалось в первой части нашего курса, в большинстве реальных больших систем не обойтись без учета "состояний природы" -- воздействий...
-
Корреляционный анализ данных - Статистическое исследование инвестиционной деятельности в регионе
Графическое представление корреляционной зависимости. Для графического представления корреляционной связи можно использовать прямоугольную систему...
-
Выборочное наблюдение широко используется для : 1) статистического оценивания и проверки гипотез; 2) решения производственных и управленческих задач; 3)...
-
Для активизации надстройки "Пакет анализа" необходимо открыть меню "Сервис" и щелкнуть по строке "Надстройки...". В открывшемся меню следует отметить...
-
Общая постановка задачи исследования операций - Экономико-математические методы
Все факторы, входящие в описание операции, можно разделить на две группы: Постоянные факторы (условия проведения операции), на которые мы влиять не...
-
Матрицей называется прямоугольная таблица чисел, содержащая m строк одинаковой длины. Матрицы равны между собой, если равны все их соответствующие...
-
Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее...
-
Основные предпосылки регрессионного анализа - Основы научных исследований
Методика РА создана с использованием некоторых предпосылок. Если они не выполняются, то корректное выполнение всех процедур РА приведет к неверным...
-
Сущность и значение экспорта товаров Экспорт (англ. Export) в экономике - вывоз за границу товаров, проданных иностранному покупателю или предназначенных...
-
Корреляция и регрессия Вспомним, что зависимости называются вероятностными или стохастическими, если каждому набору факторов Х I соответствует множество...
-
Оптимизация, Верификация модели - Синтез скоринговой модели методом системно-когнитивного анализа
Оптимизируем полученную модель с помощью удаления признаков, по которым имеется недостаточно данных. За пороговое значение встреч признаков в модели...
-
Введение - Регрессионный анализ в экономических исследованиях
Актуальность выбранной темы определяется тем, что в эконометрике широко используются методы статистики. Во многих практических задачах прогнозирования,...
-
Помимо технических характеристик здания, анализируемых выше, объекты офисной недвижимости характеризуются факторами удобства для арендаторов. К таким...
-
Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Методика отбора и хранения проб Отбор и хранение проб производилось согласно ГОСТ Р 51592-2000 "Общие требования к отбору проб".[35,36] Пробы воды в...
-
Основные положения регрессионного анализа В практике экономических исследований имеющиеся данные не всегда можно считать выборкой из многомерной...
-
Оценка значимости уравнения регрессии - Регрессионный анализ в экономических исследованиях
Проверить значимость уравнения регрессии - значит установить, соответствует ли математическая модель, выражающая зависимость между переменными,...
-
Основы системного похода к решению проблем, Структура системного анализа - Моделирование систем
В процессе функционирования реальной системы выявляется проблема практики как несоответствие существующего положения дел требуемому. Для решения проблемы...
-
Инновации как объект статистического исследования Дадим определение понятию "инновации". Инновацией является внедренное новшество, обеспечивающее...
-
Малое предпринимательство в наше время стоит воспринимать как важнейший фактов ускорения развития и укрепления рыночных отношений. Правительства...
-
Разнообразие объектов исследования является одной из характерных особенностей химико-токсикологического анализа. Объектами химико-токсикологического...
-
Нелинейный регрессионный анализ, Множественный регрессионный анализ - Основы научных исследований
Линейные по параметрам регрессионные модели можно использовать для аппроксимации нелинейных зависимостей путем их линеаризации с помощью базисных...
-
Описание используемых переменных Все имеющиеся характеристики объектов были условно разделены на две группы: - технические характеристики объектов...
-
Показатели Результаты исследования Гидрокарбонаты ПАВ Фосфаты Сульфаты Проба №1 (пос. Кирпичное) Отсутствуют 0,085 Осадок бурого цвета Отсутствуют Проба...
-
Метод сравнения является универсальным методом и применяется во всех разделах статистики (метод сравнения средних, оценивания неизвестных параметров и...
Системный анализ и исследование операций