Размещено на http://www.allbest.ru/

Задача 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.06x1+0.04x2+0.02x3?0.03

2x1+4x2+3x3?3.25

x1+x2+x3=1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x4. В 2-м неравенстве смысла (?) вводим базисную переменную x5.

0.06x1 + 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.06x1 + 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

Подобные документы

• Составление оптимального плана производства дополнительной продукции с использованием симплекс-метода

  Линейное программирование как инструмент исследования линейных моделей. Основы симплекс-метода. Моделирование экономической ситуации в инструментальном цехе. Применение симплекс-метода для оптимизации плана производства. Применимость линейной модели.
  
  курсовая работа [112,0 K], добавлен 09.12.2014
  

• Определение оптимального плана движения морских судов симплекс-методом

  Характеристика направлений перевозок и флота. Расчет нормативов работы судов на схемах движения. Составление математической модели задачи. Нахождение оптимального плана работы флота и оптимальных схем движения судов, построение симплекс таблицы.
  
  курсовая работа [1,4 M], добавлен 24.10.2012
  

• Исследование операций

  Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
  
  курсовая работа [54,1 K], добавлен 05.03.2010
  

• Построение математических моделей линейных систем управления и их моделирование

  Построение асимптотических логарифмических амплитудно- и фазочастотных характеристик. Расчет оптимального плана и экстремального значения функции цели с помощью симплекс-метода. Нахождение экстремума заданной функции с учетом системы ограничений.
  
  курсовая работа [3,2 M], добавлен 25.05.2015
  

• Применение графического метода и симплекс-метода для решения задач линейного программирования

  Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
  
  контрольная работа [398,2 K], добавлен 15.08.2012
  

• Построение оптимального плана перевозок груза с минимальной стоимостью

  Определение первичного опорного плана разными способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Перепланировка поставок с помощью метода потенциалов для каждого плана. Анализ эффективности их использования.
  
  контрольная работа [67,2 K], добавлен 06.11.2012
  

• Линейное программирование

  Задача линейного программирования: определение количества продуктов для получения максимального дохода от реализации, расчет цены для минимальной общей стоимости затрат на производство с помощью графического и симплекс-метода. Решение транспортных задач.
  
  курсовая работа [519,5 K], добавлен 06.05.2011
  

• Нахождение оптимального плана производства двух типов ремонтных работ с помощью симплексного метода

  Математические и программные средства моделирования при решении конкретной производственной задачи. Метод реализации задачи планирования производства и нахождение оптимального плана с помощью симплексного метода. Программа на языке программирования С.
  
  курсовая работа [603,8 K], добавлен 06.06.2011
  

• Моделирование исследования операций

  Характеристика табличного и канонического представления линейно-программной модели планирования. Содержательная интерпретация симплекс-метода. Корректировка оптимального плана по нерентабельной продукции. Постановка и решение транспортной задачи.
  
  курс лекций [10,1 M], добавлен 11.07.2010
  

• Симплекс-метод

  Универсальный метод решения канонической задачи линейного программирования. Общая схема симплекс-метода, его простейшая реализация на примере. Группировка слагаемых при одинаковых небазисных переменных. Определение координат нового базисного плана.
  
  контрольная работа [49,1 K], добавлен 21.10.2013
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам