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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

min (81 : 3 , 68 : 6 , 54 : 7 ) = 7⁵/₇

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	81	7	8	3	1	0	0	27
x5	68	4	1	6	0	1	0	111/3
x6	54	5	1	7	0	0	1	75/7
F(X1)	0	-2	-5	-6	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₆ в план 1 войдет переменная x₃.

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₆ плана 0 на разрешающий элемент РЭ=7

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (7), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
81-(54 * 3):7	7-(5 * 3):7	8-(1 * 3):7	3-(7 * 3):7	1-(0 * 3):7	0-(0 * 3):7	0-(1 * 3):7
68-(54 * 6):7	4-(5 * 6):7	1-(1 * 6):7	6-(7 * 6):7	0-(0 * 6):7	1-(0 * 6):7	0-(1 * 6):7
54 : 7	5 : 7	1 : 7	7 : 7	0 : 7	0 : 7	1 : 7
0-(54 * -6):7	-2-(5 * -6):7	-5-(1 * -6):7	-6-(7 * -6):7	0-(0 * -6):7	0-(0 * -6):7	0-(1 * -6):7



Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x4	405/7	34/7	53/7	0	1	0	-3/7
x5	152/7	-2/7	1/7	0	0	1	-6/7
x3	54/7	5/7	1/7	1	0	0	1/7
F(X1)	324/7	16/7	-29/7	0	0	0	6/7

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (57⁶/₇ : 7⁴/₇ , 21⁵/₇ : ¹/₇ , 7⁵/₇ : ¹/₇ ) = 7³⁴/₅₃

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (7⁴/₇) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	576/7	46/7	74/7	0	1	0	-3/7	734/53
x5	215/7	-2/7	1/7	0	0	1	-6/7	152
x3	75/7	5/7	1/7	1	0	0	1/7	54
F(X2)	462/7	22/7	-41/7	0	0	0	6/7	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 2 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=7⁴/₇

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
576/7 : 74/7	46/7 : 74/7	74/7 : 74/7	0 : 74/7	1 : 74/7	0 : 74/7	-3/7 : 74/7
215/7-(576/7 * 1/7):74/7	-2/7-(46/7 * 1/7):74/7	1/7-(74/7 * 1/7):74/7	0-(0 * 1/7):74/7	0-(1 * 1/7):74/7	1-(0 * 1/7):74/7	-6/7-(-3/7 * 1/7):74/7
75/7-(576/7 * 1/7):74/7	5/7-(46/7 * 1/7):74/7	1/7-(74/7 * 1/7):74/7	1-(0 * 1/7):74/7	0-(1 * 1/7):74/7	0-(0 * 1/7):74/7	1/7-(-3/7 * 1/7):74/7
462/7-(576/7 * -41/7):74/7	22/7-(46/7 * -41/7):74/7	-41/7-(74/7 * -41/7):74/7	0-(0 * -41/7):74/7	0-(1 * -41/7):74/7	0-(0 * -41/7):74/7	6/7-(-3/7 * -41/7):74/7

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x2	405/53	34/53	1	0	7/53	0	-3/53
x5	1093/53	-20/53	0	0	-1/53	1	-45/53
x3	351/53	33/53	0	1	-1/53	0	8/53
F(X2)	4131/53	262/53	0	0	29/53	0	33/53

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x2	405/53	34/53	1	0	7/53	0	-3/53
x5	1093/53	-20/53	0	0	-1/53	1	-45/53
x3	351/53	33/53	0	1	-1/53	0	8/53
F(X3)	4131/53	262/53	0	0	29/53	0	33/53

Оптимальный план можно записать так:

x₂ = 7³⁴/₅₃

x₃ = 6³³/₅₃

F(X) = 5*7³⁴/₅₃ + 6*6³³/₅₃ = 77⁵⁰/₅₃

Составим двойственную задачу к прямой задаче.

7y₁ + 4y₂ + 5y₃?2

8y₁ + y₂ + y₃?5

3y₁ + 6y₂ + 7y₃?6

81y₁ + 68y₂ + 54y₃ > min

y₁ ? 0

y₂ ? 0

y₃ ? 0

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

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

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

A = (A2, A5, A3) =	8 0 3 1 1 6 1 0 7

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:



D = A-1 =	7/53 0 -3/53 -1/53 1 -45/53 -1/53 0 8/53

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

(5, 0, 6) x	7/53 0 -3/53 -1/53 1 -45/53 -1/53 0 8/53	= (29/53;0;33/53)

Оптимальный план двойственной задачи равен:

y₁ = ²⁹/₅₃

y₂ = 0

y₃ = ³³/₅₃

Z(Y) = 81*²⁹/₅₃+68*0+54*³³/₅₃ = 77⁵⁰/₅₃

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

7*0 + 8*7³⁴/₅₃ + 3*6³³/₅₃ = 81 = 81

4*0 + 1*7³⁴/₅₃ + 6*6³³/₅₃ = 47²⁰/₅₃ < 68

5*0 + 1*7³⁴/₅₃ + 7*6³³/₅₃ = 54 = 54

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).

2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0.

Неиспользованный экономический резерв ресурса 2 составляет 20³³/₅₃ (68-47²⁰/₅₃).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).

Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.

Обоснование эффективности оптимального плана.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

7*²⁹/₅₃ + 4*0 + 5*³³/₅₃ = 6⁵⁰/₅₃ > 2

8*²⁹/₅₃ + 1*0 + 1*³³/₅₃ = 5 = 5

3*²⁹/₅₃ + 6*0 + 7*³³/₅₃ = 6 = 6

1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₁ = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (6⁵⁰/₅₃ - 2 = 4⁵⁰/₅₃) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).

3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₃>0).

Задание № 2

Необходимо найти минимальное значение целевой функции F = 12x₁+4x₂ > min, при системе ограничений:

2x1?34	(1)
17x1+12x2?204	(2)
-10x1+25x2?0	(3)
23x1+27x2?621	(4)
x1?0	(5)
x2?0	(6)

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).



Задача не имеет допустимых решений. ОДР представляет собой пустое множество.

Задание № 3. Транспортная задача.

С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа u_i (при i = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ?a_iu_i + ?b_jv_j

при условии

u_i + v_j <= c_ij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j <= c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij >= 0,

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

Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j - потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

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

	1	2	3	Запасы
1	4	2	3	140
2	5	3	2	120
3	1	2	3	140
Потребности	98	122	100

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 140 + 120 + 140 = 400

?b = 98 + 122 + 100 = 320

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 80 (400--320). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	4	2	3	0	140
2	5	3	2	0	120
3	1	2	3	0	140
Потребности	98	122	100	80

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

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

Искомый элемент равен 1

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

x₃₁ = min(140,98) = 98.

x	2	3	0	140
x	3	2	0	120
1	2	3	0	140 - 98 = 42
98 - 98 = 0	122	100	80	0

Искомый элемент равен 2

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

x₁₂ = min(140,122) = 122.

x	2	3	0	140 - 122 = 18
x	x	2	0	120
1	x	3	0	42
0	122 - 122 = 0	100	80	0

Искомый элемент равен 2

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

x₂₃ = min(120,100) = 100.

x	2	x	0	18
x	x	2	0	120 - 100 = 20
1	x	x	0	42
0	0	100 - 100 = 0	80	0

Искомый элемент равен 0

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

x₁₄ = min(18,80) = 18.

x	2	x	0	18 - 18 = 0
x	x	2	0	20
1	x	x	0	42
0	0	0	80 - 18 = 62	0

Искомый элемент равен 0

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

x₂₄ = min(20,62) = 20.

x	2	x	0	0
x	x	2	0	20 - 20 = 0
1	x	x	0	42
0	0	0	62 - 20 = 42	0

Искомый элемент равен 0

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

x₃₄ = min(42,42) = 42.

x	2	x	0	0
x	x	2	0	0
1	x	x	0	42 - 42 = 0
0	0	0	42 - 42 = 0	0



	1	2	3	4	Запасы
1	4	2[122]	3	0[18]	140
2	5	3	2[100]	0[20]	120
3	1[98]	2	3	0[42]	140
Потребности	98	122	100	80

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*122 + 0*18 + 2*100 + 0*20 + 1*98 + 0*42 = 542

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₁ + v₄ = 0; 0 + v₄ = 0; v₄ = 0

u₂ + v₄ = 0; 0 + u₂ = 0; u₂ = 0

u₂ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₃ + v₄ = 0; 0 + u₃ = 0; u₃ = 0

u₃ + v₁ = 1; 0 + v₁ = 1; v₁ = 1

	v1=1	v2=2	v3=2	v4=0
u1=0	4	2[122]	3	0[18]
u2=0	5	3	2[100]	0[20]
u3=0	1[98]	2	3	0[42]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.

Минимальные затраты составят:

F(x) = 2*122 + 0*18 + 2*100 + 0*20 + 1*98 + 0*42 = 542

Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).

G = 0*140 + 0*120 + 0*140 + 1*98 + 2*122 + 2*100 + 0*80 = 542

Анализ оптимального плана.

Из 1-го склада необходимо весь груз направить в 2-й магазин

Из 2-го склада необходимо весь груз направить в 3-й магазин

Из 3-го склада необходимо весь груз направить в 1-й магазин

На 1-ом складе остался невостребованным груз в количестве 18 ед.

Оптимальный план является вырожденным, так как базисная переменная x₁₄=0.

На 2-ом складе остался невостребованным груз в количестве 20 ед.

Оптимальный план является вырожденным, так как базисная переменная x₂₄=0.

На 3-ом складе остался невостребованным груз в количестве 42 ед.

Оптимальный план является вырожденным, так как базисная переменная x₃₄=0.

Задание № 4

Системы массового обслуживания.

Исчисляем показатели обслуживания многоканальной СМО:

Интенсивность потока обслуживания:

1. Интенсивность нагрузки.

с = л * t_обс = 1 * 6/60 = 0.1

Интенсивность нагрузки с=0.1 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

3. Вероятность, что канал свободен (доля времени простоя каналов).

= =

Следовательно, 90% в течение часа канал будет не занят, время простоя равно t_пр = 54.1 мин.

Вероятность того, что обслуживанием:

занят 1 канал:

p₁ = с¹/1! p₀ = 0.1¹/1! * 0.9 = 0.0901

заняты 2 канала:

p₂ = с²/2! p₀ = 0.1²/2! * 0.9 = 0.0045

заняты 3 канала:

p₃ = с³/3! p₀ = 0.1³/3! * 0.9 = 0.00015

заняты 4 канала:

p₄ = с⁴/4! p₀ = 0.1⁴/4! * 0.9 = 4.0E-6

заняты 5 каналов:

p₅ = с⁵/5! p₀ = 0.1⁵/5! * 0.9 = 0

заняты 6 каналов:

p₆ = с⁶/6! p₀ = 0.1⁶/6! * 0.9 = 0

заняты 7 каналов:

p₇ = с⁷/7! p₀ = 0.1⁷/7! * 0.9 = 0

заняты 8 каналов:

p₈ = с⁸/8! p₀ = 0.1⁸/8! * 0.9 = 0

заняты 9 каналов:

p₉ = с⁹/9! p₀ = 0.1⁹/9! * 0.9 = 0

заняты 10 каналов:

p₁₀ = с¹⁰/10! p₀ = 0.1¹⁰/10! * 0.9 = 0

4. Доля заявок, получивших отказ.

Заявки не получают отказ. Обслуживаются все поступившие заявки.

5. Вероятность обслуживания поступающих заявок.

В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:

p_отк + p_обс = 1

Относительная пропускная способность: Q = p_обс.

p_обс = 1 - p_отк = 1 - 0 = 1

Следовательно, 100% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.

6. Среднее число каналов, занятых обслуживанием.

n_з = с * p_обс = 0.1 * 1 = 0.1 канала.

Среднее число простаивающих каналов.

n_пр = n - n_з = 10 - 0.1 = 9.9 канала.

7. Коэффициент занятости каналов обслуживанием.

Следовательно, система на 0% занята обслуживанием.

8. Абсолютная пропускная способность.

A = p_обс * л = 1 * 1 = 1 заявок/час.

9. Среднее время простоя СМО.

t_пр = p_отк * t_обс = 0 * 0.1 = 0 час.

12. Среднее число обслуживаемых заявок.

L_обс = с * Q = 0.1 * 1 = 0.1 ед.

Число заявок, получивших отказ в течение часа: л * p₁ = 0 заявок в час.

Номинальная производительность СМО: 10 / 0.1 = 100 заявок в час.

Фактическая производительность СМО: 1 / 100 = 1% от номинальной производительности.

Задание № 5

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

12x₁+3x₂+9x₃+14x₄ ? 1

9x₁+18x₂+13x₃+4x₄ ? 1

F(x) = x₁+x₂+x₃+x₄ = min

найти максимум функции Ф(y) при ограничениях:

12y₁+9y₂ ? 1

3y₁+18y₂ ? 1

9y₁+13y₂ ? 1

14y₁+4y₂ ? 1

Ф(y) = y₁+y₂ = max

Решаем эти системы симплексным методом

12x₁ + 9x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 1

3x₁ + 18x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 1

9x₁ + 13x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 1

14x₁ + 4x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ = 1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	12 9 1 0 0 0 3 18 0 1 0 0 9 13 0 0 1 0 14 4 0 0 0 1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅, x₆

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,1,1,1,1)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x3	1	12	9	1	0	0	0
x4	1	3	18	0	1	0	0
x5	1	9	13	0	0	1	0
x6	1	14	4	0	0	0	1
F(X0)	0	-1	-1	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (1 : 9 , 1 : 18 , 1 : 13 , 1 : 4 ) = ¹/₁₈

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (18) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	1	12	9	1	0	0	0	1/9
x4	1	3	18	0	1	0	0	1/18
x5	1	9	13	0	0	1	0	1/13
x6	1	14	4	0	0	0	1	1/4
F(X1)	0	-1	-1	0	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=18

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (18), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
1-(1 * 9):18	12-(3 * 9):18	9-(18 * 9):18	1-(0 * 9):18	0-(1 * 9):18	0-(0 * 9):18	0-(0 * 9):18
1 : 18	3 : 18	18 : 18	0 : 18	1 : 18	0 : 18	0 : 18
1-(1 * 13):18	9-(3 * 13):18	13-(18 * 13):18	0-(0 * 13):18	0-(1 * 13):18	1-(0 * 13):18	0-(0 * 13):18
1-(1 * 4):18	14-(3 * 4):18	4-(18 * 4):18	0-(0 * 4):18	0-(1 * 4):18	0-(0 * 4):18	1-(0 * 4):18
0-(1 * -1):18	-1-(3 * -1):18	-1-(18 * -1):18	0-(0 * -1):18	0-(1 * -1):18	0-(0 * -1):18	0-(0 * -1):18

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/2	21/2	0	1	-1/2	0	0
x2	1/18	1/6	1	0	1/18	0	0
x5	5/18	41/6	0	0	-13/18	1	0
x6	7/9	40/3	0	0	-2/9	0	1
F(X1)	1/18	-5/6	0	0	1/18	0	0

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (¹/₂ : 10¹/₂ , ¹/₁₈ : ¹/₆ , ⁵/₁₈ : 6⁵/₆ , ⁷/₉ : 13¹/₃ ) = ⁵/₁₂₃

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (6⁵/₆) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	1/2	101/2	0	1	-1/2	0	0	1/21
x2	1/18	1/6	1	0	1/18	0 <...

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

• Решение задач линейного программирования

  Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
  
  курсовая работа [106,0 K], добавлен 05.10.2014
  

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

  Нахождение области допустимых значений и оптимумов целевой функции с целью решения графическим методом задачи линейного программирования. Нахождение оптимальных значений двойственных переменных при помощи симплексного метода и теории двойственности.
  
  контрольная работа [116,0 K], добавлен 09.04.2012
  

• Решение задач линейного программирования

  Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
  
  контрольная работа [40,0 K], добавлен 04.05.2014
  

• Математические методы в экономике

  Симплекс-метод решения задач линейного программирования. Элементы теории игр. Системы массового обслуживания. Транспортная задача. Графоаналитический метод решения задач линейного программирования. Определение оптимальной стратегии по критерию Вальде.
  
  контрольная работа [400,2 K], добавлен 24.08.2010
  

• Методы сетевого планирования

  История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.
  
  курсовая работа [842,1 K], добавлен 19.02.2015
  

• Математическое программирование

  Понятие математического программирования как отрасли математики, являющейся теоретической основой решения задач о нахождении оптимальных решений. Основные этапы нахождения оптимальных решений экономических задач. Примеры задач линейного программирования.
  
  учебное пособие [2,0 M], добавлен 15.06.2015
  

• Экономико-математические методы и модели

  Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.
  
  лекция [124,5 K], добавлен 15.06.2004
  

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

  Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
  
  контрольная работа [367,5 K], добавлен 11.05.2014
  

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

  Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
  
  курсовая работа [105,5 K], добавлен 02.10.2014
  

• Экономико-математические методы и прикладные модели

  Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.
  
  курсовая работа [30,5 K], добавлен 14.04.2004
  

• Разработка алгоритмов для решения экономических задач

  Моделирование экономических процессов методами планирования и управления. Построение сетевой модели. Оптимизация сетевого графика при помощи табличного редактора Microsoft Excel и среды программирования Visual Basic. Методы принятия оптимальных решений.
  
  курсовая работа [217,2 K], добавлен 22.11.2013
  

• Методы линейного программирования для решения транспортной задачи

  Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
  
  реферат [4,1 M], добавлен 09.03.2011
  

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

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

• Расчет интервалов устойчивости

  Устойчивость двойственных оценок. Чувствительность оптимального решения задачи к изменению свободных членов. Графический метод решения задачи линейного программирования. Прогнозирование экономических процессов с использованием моделей временных рядов.
  
  курсовая работа [2,3 M], добавлен 05.12.2011
  

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

  Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Характеристика графических методов решения задачи линейного программирования, сущность их геометрической интерпретации и основные этапы.
  
  курсовая работа [609,5 K], добавлен 17.02.2010
  

• Нахождение критического пути табличным методом

  Проблема автоматизации расчёта сетевого графика. Вычисление критического пути с помощью ЭВМ. Табличный метод решения проблемы, метод графов. Составление алгоритма, написание программы и решение задачи. графический интерфейс пользователя, ввод данных.
  
  курсовая работа [39,7 K], добавлен 20.11.2008
  

• Линейное программирование: методы решения задач

  Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.
  
  контрольная работа [1,1 M], добавлен 14.03.2014
  

• Оптимизационные задачи в экономике и алгоритмы решения некоторых задач линейного программирования

  Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
  
  учебное пособие [126,0 K], добавлен 07.10.2014
  

• Экономико-математические методы сетевого планирования и управления

  Сравнение экономико-математических методов сетевого планирования при решении практических задач управления. Временные характеристики и правила построения сетевых графиков. Оптимизация проекта по времени и стоимости. Особенности метода критического пути.
  
  курсовая работа [1,5 M], добавлен 29.03.2015
  

• Двойственность в линейном программировании

  Прямые и двойственные задачи линейного программирования, особенности и методика их решения. Основные положения теоремы двойственности. Виды математических моделей двойственных задач. Разработка программы планирования работы швейной мастерской в Excel.
  
  курсовая работа [177,8 K], добавлен 26.07.2009
  

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