Модели и методы управления

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

НЕКОММЕРЧЕСКОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра компьютерных технологий

Расчётно-графическая работа

По дисциплине

«Модели и методы управления»



Задача 1

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

Определим минимальное значение целевой функции F(X) = - 12x1 - 7x2 - 6x4+300 при следующих условиях-ограничений.

При вычислениях значение Fc = 300 временно не учитываем.

2x1 + 15x2 + 38x3 + 4x4?26

6x1 + 18x2 + 6x3 + 3x4?24

8x1 + 4x2 + x3?56

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

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

2x1 + 15x2 + 38x3 + 4x4 + 1x5 + 0x6 + 0x7 = 26

6x1 + 18x2 + 6x3 + 3x4 + 0x5 + 1x6 + 0x7 = 24

8x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 56

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

2	15	38	4	1	0	0
6	18	6	3	0	1	0
8	4	1	0	0	0	1

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

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

Решим систему уравнений относительно базисных переменных:

x5, x6, x7,

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

X1 = (0,0,0,0,26,24,56)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	26	2	15	38	4	1	0	0
x6	24	6	18	6	3	0	1	0
x7	56	8	4	1	0	0	0	1
F(X0)	0	12	7	0	6	0	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (26 : 2 , 24 : 6 , 56 : 8 ) = 4

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x5	26	2	15	38	4	1	0	0	13
x6	24	6	18	6	3	0	1	0	4
x7	56	8	4	1	0	0	0	1	7
F(X1)	0	12	7	0	6	0	0	0	0

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

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

Вместо переменной x6 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=6 На месте разрешающего элемента в плане 1 получаем 1.

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
26-(24 * 2):6	2-(6 * 2):6	15-(18 * 2):6	38-(6 * 2):6	4-(3 * 2):6	1-(0 * 2):6	0-(1 * 2):6	0-(0 * 2):6
24 : 6	6 : 6	18 : 6	6 : 6	3 : 6	0 : 6	1 : 6	0 : 6
56-(24 * 8):6	8-(6 * 8):6	4-(18 * 8):6	1-(6 * 8):6	0-(3 * 8):6	0-(0 * 8):6	0-(1 * 8):6	1-(0 * 8):6
0-(24 * 12):6	12-(6 * 12):6	7-(18 * 12):6	0-(6 * 12):6	6-(3 * 12):6	0-(0 * 12):6	0-(1 * 12):6	0-(0 * 12):6



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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	18	0	9	36	3	1	-1/3	0
x1	4	1	3	1	1/2	0	1/6	0
x7	24	0	-20	-7	-4	0	-11/3	1
F(X1)	-48	0	-29	-12	0	0	-2	0

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	18	0	9	36	3	1	-1/3	0
x1	4	1	3	1	1/2	0	1/6	0
x7	24	0	-20	-7	-4	0	-11/3	1
F(X2)	-48	0	-29	-12	0	0	-2	0

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

x1 = 4

F(X) = -12*4 + 300 = 252

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

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 18

В оптимальный план вошла дополнительная переменная x7. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 24

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 29> 0 в столбце x2 означает, что использование x2 - не выгодно.

Значение 12> 0 в столбце x3 означает, что использование x3 - не выгодно.

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

Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x5), выполнив соответствующие этапы алгоритма.

После преобразований получаем новую таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	6	0	3	12	1	1/3	-1/9	0
x1	1	1	11/2	-5	0	-1/6	2/9	0
x7	48	0	-8	41	0	11/3	-17/9	1
F(X )	-48	0	-29	-12	0	0	-2	0

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

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

Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x4), выполнив соответствующие этапы алгоритма.

После преобразований получаем новую таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	18	0	9	36	3	1	-1/3	0
x1	4	1	3	1	1/2	0	1/6	0
x7	24	0	-20	-7	-4	0	-11/3	1
F(X )	-48	0	-29	-12	0	0	-2	0



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

Значение 2 в столбце x6 означает, что теневая цена (двойственная оценка) равна 2.

Задача.2

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

Определим максимальное значение целевой функции F(X) = 6x1 + 4x2 + 2x3 при следующих условиях-ограничений.

2x1 + 7x2 + 22x3?22

2x1 - x2 + 6x3?6

2x1 - 5x2 + 2x3?2

4x1 + x2 + x3?1

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

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

2x1 + 7x2 + 22x3 + 1x4 + 0x5 + 0x6 + 0x7 = 22

2x1-1x2 + 6x3 + 0x4 + 1x5 + 0x6 + 0x7 = 6

2x1-5x2 + 2x3 + 0x4 + 0x5 + 1x6 + 0x7 = 2

4x1 + 1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 1

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

2	7	22	1	0	0	0
2	-1	6	0	1	0	0
2	-5	2	0	0	1	0
4	1	1	0	0	0	1

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

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

Решим систему уравнений относительно базисных переменных:

x4, x5, x6, x7,

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

X1 = (0,0,0,22,6,2,1)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	22	2	7	22	1	0	0	0
x5	6	2	-1	6	0	1	0	0
x6	2	2	-5	2	0	0	1	0
x7	1	4	1	1	0	0	0	1
F(X0)	0	-6	-4	-2	0	0	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (22 : 2 , 6 : 2 , 2 : 2 , 1 : 4 ) = 1/4

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	22	2	7	22	1	0	0	0	11
x5	6	2	-1	6	0	1	0	0	3
x6	2	2	-5	2	0	0	1	0	1
x7	1	4	1	1	0	0	0	1	1/4
F(X1)	0	-6	-4	-2	0	0	0	0	0

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

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

Вместо переменной x7 в план 1 войдет переменная x1.

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
22-(1 * 2):4	2-(4 * 2):4	7-(1 * 2):4	22-(1 * 2):4	1-(0 * 2):4	0-(0 * 2):4	0-(0 * 2):4	0-(1 * 2):4
6-(1 * 2):4	2-(4 * 2):4	-1-(1 * 2):4	6-(1 * 2):4	0-(0 * 2):4	1-(0 * 2):4	0-(0 * 2):4	0-(1 * 2):4
2-(1 * 2):4	2-(4 * 2):4	-5-(1 * 2):4	2-(1 * 2):4	0-(0 * 2):4	0-(0 * 2):4	1-(0 * 2):4	0-(1 * 2):4
1 : 4	4 : 4	1 : 4	1 : 4	0 : 4	0 : 4	0 : 4	1 : 4
0-(1 * -6):4	-6-(4 * -6):4	-4-(1 * -6):4	-2-(1 * -6):4	0-(0 * -6):4	0-(0 * -6):4	0-(0 * -6):4	0-(1 * -6):4

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	211/2	0	61/2	211/2	1	0	0	-1/2
x5	51/2	0	-11/2	51/2	0	1	0	-1/2
x6	11/2	0	-51/2	11/2	0	0	1	-1/2
x1	1/4	1	1/4	1/4	0	0	0	1/4
F(X1)	11/2	0	-21/2	-1/2	0	0	0	11/2

Итерация №1.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

min (211/2 : 61/2 , - , - , 1/4 : 1/4 ) = 1

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	211/2	0	61/2	211/2	1	0	0	-1/2	34/13
x5	51/2	0	-11/2	51/2	0	1	0	-1/2	-
x6	11/2	0	-51/2	11/2	0	0	1	-1/2	-
x1	1/4	1	1/4	1/4	0	0	0	1/4	1
F(X2)	11/2	0	-21/2	-1/2	0	0	0	11/2	0

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

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

Вместо переменной x1 в план 2 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x1 плана 1 на разрешающий элемент РЭ=1/4

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
211/2-(1/4 * 61/2):1/4	0-(1 * 61/2):1/4	61/2-(1/4 * 61/2):1/4	211/2-(1/4 * 61/2):1/4	1-(0 * 61/2):1/4	0-(0 * 61/2):1/4	0-(0 * 61/2):1/4	-1/2-(1/4 * 61/2):1/4
51/2-(1/4 * -11/2):1/4	0-(1 * -11/2):1/4	-11/2-(1/4 * -11/2):1/4	51/2-(1/4 * -11/2):1/4	0-(0 * -11/2):1/4	1-(0 * -11/2):1/4	0-(0 * -11/2):1/4	-1/2-(1/4 * -11/2):1/4
11/2-(1/4 * -51/2):1/4	0-(1 * -51/2):1/4	-51/2-(1/4 * -51/2):1/4	11/2-(1/4 * -51/2):1/4	0-(0 * -51/2):1/4	0-(0 * -51/2):1/4	1-(0 * -51/2):1/4	-1/2-(1/4 * -51/2):1/4
1/4 : 1/4	1 : 1/4	1/4 : 1/4	1/4 : 1/4	0 : 1/4	0 : 1/4	0 : 1/4	1/4 : 1/4
11/2-(1/4 * -21/2):1/4	0-(1 * -21/2):1/4	-21/2-(1/4 * -21/2):1/4	-1/2-(1/4 * -21/2):1/4	0-(0 * -21/2):1/4	0-(0 * -21/2):1/4	0-(0 * -21/2):1/4	11/2-(1/4 * -21/2):1/4



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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	15	-26	0	15	1	0	0	-7
x5	7	6	0	7	0	1	0	1
x6	7	22	0	7	0	0	1	5
x2	1	4	1	1	0	0	0	1
F(X2)	4	10	0	2	0	0	0	4

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	15	-26	0	15	1	0	0	-7
x5	7	6	0	7	0	1	0	1
x6	7	22	0	7	0	0	1	5
x2	1	4	1	1	0	0	0	1
F(X3)	4	10	0	2	0	0	0	4

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

x2 = 1

F(X) = 4*1 = 4

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

В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 15

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 7

В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 7

Значение 10> 0 в столбце x1 означает, что использование x1 - не выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 2> 0 в столбце x3 означает, что использование x3 - не выгодно.

Значение 4 в столбце x7 означает, что теневая цена (двойственная оценка) равна 4.

Задача 3

Определим минимальное значение целевой функции F(X) = x1 - 3x2 + 2x3+15 при следующих условиях-ограничений.

При вычислениях значение Fc = 15 временно не учитываем.

3x1 - x2 + 2x3?7

- 2x1 + 4x2?12

- 4x1 - 3x2 + 8x3?10

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

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

3x1-1x2 + 2x3 + 1x4 + 0x5 + 0x6 = 7

-2x1 + 4x2 + 0x3 + 0x4 + 1x5 + 0x6 = 12

-4x1-3x2 + 8x3 + 0x4 + 0x5 + 1x6 = 10

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

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

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

Решим систему уравнений относительно базисных переменных:

x4, x5, x6,

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

X1 = (0,0,0,7,12,10)

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	7	3	-1	2	1	0	0
x5	12	-2	4	0	0	1	0
x6	10	-4	-3	8	0	0	1
F(X0)	0	-1	3	-2	0	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

min (- , 12 : 4 , - ) = 3

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	7	3	-1	2	1	0	0	-
x5	12	-2	4	0	0	1	0	3
x6	10	-4	-3	8	0	0	1	-
F(X1)	0	-1	3	-2	0	0	0	0

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

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

Вместо переменной x5 в план 1 войдет переменная x2.

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

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

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

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

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

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

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

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

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



B	x 1	x 2	x 3	x 4	x 5	x 6
7-(12 * -1):4	3-(-2 * -1):4	-1-(4 * -1):4	2-(0 * -1):4	1-(0 * -1):4	0-(1 * -1):4	0-(0 * -1):4
12 : 4	-2 : 4	4 : 4	0 : 4	0 : 4	1 : 4	0 : 4
10-(12 * -3):4	-4-(-2 * -3):4	-3-(4 * -3):4	8-(0 * -3):4	0-(0 * -3):4	0-(1 * -3):4	1-(0 * -3):4
0-(12 * 3):4	-1-(-2 * 3):4	3-(4 * 3):4	-2-(0 * 3):4	0-(0 * 3):4	0-(1 * 3):4	0-(0 * 3):4

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	10	21/2	0	2	1	1/4	0
x2	3	-1/2	1	0	0	1/4	0
x6	19	-51/2	0	8	0	3/4	1
F(X1)	-9	1/2	0	-2	0	-3/4	0

Итерация №1.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (10 : 21/2 , - , - ) = 4

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	10	21/2	0	2	1	1/4	0	4
x2	3	-1/2	1	0	0	1/4	0	-
x6	19	-51/2	0	8	0	3/4	1	-
F(X2)	-9	1/2	0	-2	0	-3/4	0	0

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

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

Вместо переменной x4 в план 2 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=21/2

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6
10 : 21/2	21/2 : 21/2	0 : 21/2	2 : 21/2	1 : 21/2	1/4 : 21/2	0 : 21/2
3-(10 * -1/2):21/2	-1/2-(21/2 * -1/2):21/2	1-(0 * -1/2):21/2	0-(2 * -1/2):21/2	0-(1 * -1/2):21/2	1/4-(1/4 * -1/2):21/2	0-(0 * -1/2):21/2
19-(10 * -51/2):21/2	-51/2-(21/2 * -51/2):21/2	0-(0 * -51/2):21/2	8-(2 * -51/2):21/2	0-(1 * -51/2):21/2	3/4-(1/4 * -51/2):21/2	1-(0 * -51/2):21/2
-9-(10 * 1/2):21/2	1/2-(21/2 * 1/2):21/2	0-(0 * 1/2):21/2	-2-(2 * 1/2):21/2	0-(1 * 1/2):21/2	-3/4-(1/4 * 1/2):21/2	0-(0 * 1/2):21/2

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

Базис	B	x1	x2	x3	x4	x5	x6
x1	4	1	0	4/5	2/5	1/10	0
x2	5	0	1	2/5	1/5	3/10	0
x6	41	0	0	122/5	21/5	13/10	1
F(X2)	-11	0	0	-22/5	-1/5	-4/5	0

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x1	4	1	0	4/5	2/5	1/10	0
x2	5	0	1	2/5	1/5	3/10	0
x6	41	0	0	122/5	21/5	13/10	1
F(X3)	-11	0	0	-22/5	-1/5	-4/5	0

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

x1 = 4

x2 = 5

F(X) = 1*4 -3*5 + 15 = 4

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

В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 41

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 22/5> 0 в столбце x3 означает, что использование x3 - не выгодно.

Значение 1/5 в столбце x4 означает, что теневая цена (двойственная оценка) равна 1/5.

Значение 4/5 в столбце x5 означает, что теневая цена (двойственная оценка) равна 4/5.

РГР 2

Задача 4

Определим максимальное значение целевой функции F(X) = x1 + 7x2 - 3x3 - 3x4 - 3x5 при следующих условиях-ограничений.

- x1 + 2x2 - 2x4 + 2x5=10

x1 + 2x2 - 2x3 + x4=4

3x1 + 2x2 + 2x3 - x4 - x5=6

Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7; в 3-м равенстве вводим переменную x8;

-1x1 + 2x2 + 0x3-2x4 + 2x5 + 1x6 + 0x7 + 0x8 = 10

1x1 + 2x2-2x3 + 1x4 + 0x5 + 0x6 + 1x7 + 0x8 = 4

3x1 + 2x2 + 2x3-1x4-1x5 + 0x6 + 0x7 + 1x8 = 6

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = x1+7x2-3x3-3x4-3x5 - Mx6 - Mx7 - Mx8 > max

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

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

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

Из уравнений выражаем искусственные переменные:

x6 = 10+x1-2x2+2x4-2x5

x7 = 4-x1-2x2+2x3-x4

x8 = 6-3x1-2x2-2x3+x4+x5

которые подставим в целевую функцию:

F(X) = x1 + 7x2-3x3-3x4-3x5 - M(10+x1-2x2+2x4-2x5) - M(4-x1-2x2+2x3-x4) - M(6-3x1-2x2-2x3+x4+x5) > max

или F(X) = (1+3M)x1+(7+6M)x2+(-3)x3+(-3-2M)x4+(-3+M)x5+(-20M) > max

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

-1	2	0	-2	2	1	0	0
1	2	-2	1	0	0	1	0
3	2	2	-1	-1	0	0	1

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

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

Решим систему уравнений относительно базисных переменных:

x6, x7, x8,

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

X1 = (0,0,0,0,0,10,4,6)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	10	-1	2	0	-2	2	1	0	0
x7	4	1	2	-2	1	0	0	1	0
x8	6	3	2	2	-1	-1	0	0	1
F(X0)	-20M	-1-3M	-7-6M	3	3+2M	3-M	0	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

min (10 : 2 , 4 : 2 , 6 : 2 ) = 2

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	10	-1	2	0	-2	2	1	0	0	5
x7	4	1	2	-2	1	0	0	1	0	2
x8	6	3	2	2	-1	-1	0	0	1	3
F(X1)	-20M	-1-3M	-7-6M	3	3+2M	3-M	0	0	0	0

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

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

Вместо переменной x7 в план 1 войдет переменная x2.

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4
10-(4 * 2):2	-1-(1 * 2):2	2-(2 * 2):2	0-(-2 * 2):2	-2-(1 * 2):2
4 : 2	1 : 2	2 : 2	-2 : 2	1 : 2
6-(4 * 2):2	3-(1 * 2):2	2-(2 * 2):2	2-(-2 * 2):2	-1-(1 * 2):2
(0)-(4 * (-7-6M)):2	(-1-3M)-(1 * (-7-6M)):2	(-7-6M)-(2 * (-7-6M)):2	(3)-(-2 * (-7-6M)):2	(3+2M)-(1 * (-7-6M)):2
x 5	x 6	x 7	x 8
2-(0 * 2):2	1-(0 * 2):2	0-(1 * 2):2	0-(0 * 2):2
0 : 2	0 : 2	1 : 2	0 : 2
-1-(0 * 2):2	0-(0 * 2):2	0-(1 * 2):2	1-(0 * 2):2
(3-M)-(0 * (-7-6M)):2	(0)-(0 * (-7-6M)):2	(0)-(1 * (-7-6M)):2	(0)-(0 * (-7-6M)):2

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	6	-2	0	2	-3	2	1	-1	0
x2	2	1/2	1	-1	1/2	0	0	1/2	0
x8	2	2	0	4	-2	-1	0	-1	1
F(X1)	14-8M	21/2	0	-4-6M	61/2+5M	3-M	0	31/2+3M	0

Итерация №1.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai3

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

min (6 : 2 , - , 2 : 4 ) = 1/2

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	6	-2	0	2	-3	2	1	-1	0	3
x2	2	1/2	1	-1	1/2	0	0	1/2	0	-
x8	2	2	0	4	-2	-1	0	-1	1	1/2
F(X2)	14-8M	21/2	0	-4-6M	61/2+5M	3-M	0	31/2+3M	0	0

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

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

Вместо переменной x8 в план 2 войдет переменная x3.

Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x8 плана 1 на разрешающий элемент РЭ=4

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

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

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

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

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

B	x 1	x 2	x 3	x 4
6-(2 * 2):4	-2-(2 * 2):4	0-(0 * 2):4	2-(4 * 2):4	-3-(-2 * 2):4
2-(2 * -1):4	1/2-(2 * -1):4	1-(0 * -1):4	-1-(4 * -1):4	1/2-(-2 * -1):4
2 : 4	2 : 4	0 : 4	4 : 4	-2 : 4
(0)-(2 * (-4-6M)):4	(21/2)-(2 * (-4-6M)):4	(0)-(0 * (-4-6M)):4	(-4-6M)-(4 * (-4-6M)):4	(61/2+5M)-(-2 * (-4-6M)):4
x 5	x 6	x 7	x 8
2-(-1 * 2):4	1-(0 * 2):4	-1-(-1 * 2):4	0-(1 * 2):4
0-(-1 * -1):4	0-(0 * -1):4	1/2-(-1 * -1):4	0-(1 * -1):4
-1 : 4	0 : 4	-1 : 4	1 : 4
(3-M)-(-1 * (-4-6M)):4	(0)-(0 * (-4-6M)):4	(31/2+3M)-(-1 * (-4-6M)):4	(0)-(1 * (-4-6M)):4

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	5	-3	0	0	-2	21/2	1	-1/2	-1/2
x2	21/2	1	1	0	0	-1/4	0	1/4	1/4
x3	1/2	1/2	0	1	-1/2	-1/4	0	-1/4	1/4
F(X2)	16-5M	41/2+3M	0	0	41/2+2M	2-21/2M	0	21/2+11/2M	1+11/2M

Итерация №2.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai5

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

min (5 : 21/2 , - , - ) = 2

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	5	-3	0	0	-2	21/2	1	-1/2	-1/2	2
x2	21/2	1	1	0	0	-1/4	0	1/4	1/4	-
x3	1/2	1/2	0	1	-1/2	-1/4	0	-1/4	1/4	-
F(X3)	16-5M	41/2+3M	0	0	41/2+2M	2-21/2M	0	21/2+11/2M	1+11/2M	0

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

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

Вместо переменной x6 в план 3 войдет переменная x5.

Строка, соответствующая переменной x5 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=21/2

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

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

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

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

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

B	x 1	x 2	x 3	x 4
5 : 21/2	-3 : 21/2	0 : 21/2	0 : 21/2	-2 : 21/2
21/2-(5 * -1/4):21/2	1-(-3 * -1/4):21/2	1-(0 * -1/4):21/2	0-(0 * -1/4):21/2	0-(-2 * -1/4):21/2
1/2-(5 * -1/4):21/2	1/2-(-3 * -1/4):21/2	0-(0 * -1/4):21/2	1-(0 * -1/4):21/2	-1/2-(-2 * -1/4):21/2
(1+11/2M)-(5 * (2-21/2M)):21/2	(41/2+3M)-(-3 * (2-21/2M)):21/2	(0)-(0 * (2-21/2M)):21/2	(0)-(0 * (2-21/2M)):21/2	(41/2+2M)-(-2 * (2-21/2M)):21/2
x 5	x 6	x 7	x 8
21/2 : 21/2	1 : 21/2	-1/2 : 21/2	-1/2 : 21/2
-1/4-(21/2 * -1/4):21/2	0-(1 * -1/4):21/2	1/4-(-1/2 * -1/4):21/2	1/4-(-1/2 * -1/4):21/2
-1/4-(21/2 * -1/4):21/2	0-(1 * -1/4):21/2	-1/4-(-1/2 * -1/4):21/2	1/4-(-1/2 * -1/4):21/2
(2-21/2M)-(21/2 * (2-21/2M)):21/2	(0)-(1 * (2-21/2M)):21/2	(21/2+11/2M)-(-1/2 * (2-21/2M)):21/2	(1+11/2M)-(-1/2 * (2-21/2M)):21/2

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



Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x5	2	-11/5	0	0	-4/5	1	2/5	-1/5	-1/5
x2	3	7/10	1	0	-1/5	0	1/10	1/5	1/5
x3	1	1/5	0	1	-7/10	0	1/10	-3/10	1/5
F(X3)	12	69/10	0	0	61/10	0	-4/5+M	29/10+M	12/5+M

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x5	2	-11/5	0	0	-4/5	1	2/5	-1/5	-1/5
x2	3	7/10	1	0	-1/5	0	1/10	1/5	1/5
x3	1	1/5	0	1	-7/10	0	1/10	-3/10	1/5
F(X4)	12	69/10	0	0	61/10	0	-4/5+M	29/10+M	12/5+M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

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

x5 = 2

x2 = 3

x3 = 1

F(X) = -3*2 + 7*3 -3*1 = 12

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

Значение 69/10> 0 в столбце x1 означает, что использование x1 - не выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 0 в столбце x3 означает, что использование x3 - выгодно.

Значение 61/10> 0 в столбце x4 означает, что использование x4 - не выгодно.

Значение 0 в столбце x5 означает, что использование x5 - выгодно.

Значение -4/5+1M в столбце x6 означает, что теневая цена (двойственная оценка) равна -4/5+1M.

Значение 29/10+1M в столбце x7 означает, что теневая цена (двойственная оценка) равна 29/10+1M.

Значение 12/5+1M в столбце x8 означает, что теневая цена (двойственная оценка) равна 12/5+1M.

Задача 5

Определим минимальное значение целевой функции F(X) = 12x1+5x2+9x3 при следующих условиях-ограничений.

5.5x1+x2+5.5x3?143

3x1+2x2+x3=62

x1+2x2+2x3?102

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

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

5.5x1 + 1x2 + 5.5x3 + 1x4 + 0x5 = 143

3x1 + 2x2 + 1x3 + 0x4 + 0x5 = 62

1x1 + 2x2 + 2x3 + 0x4-1x5 = 102

Введем искусственные переменные x: в 2-м равенстве вводим переменную x6; в 3-м равенстве вводим переменную x7;

5.5x1 + 1x2 + 5.5x3 + 1x4 + 0x5 + 0x6 + 0x7 = 143

3x1 + 2x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 62

1x1 + 2x2 + 2x3 + 0x4-1x5 + 0x6 + 1x7 = 102

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = 12x1+5x2+9x3+Mx6+Mx7 > min

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

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

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

Из уравнений выражаем искусственные переменные:

x6 = 62-3x1-2x2-x3

x7 = 102-x1-2x2-2x3+x5

которые подставим в целевую функцию:

F(X) = 12x1 + 5x2 + 9x3 + M(62-3x1-2x2-x3) + M(102-x1-2x2-2x3+x5) > min или F(X) = (12-4M)x1+(5-4M)x2+(9-3M)x3+(M)x5+(164M) > min

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

5.5	1	5.5	1	0	0	0
3	2	1	0	0	1	0
1	2	2	0	-1	0	1

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

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

Решим систему уравнений относительно базисных переменных:

x4, x6, x7,

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

X1 = (0,0,0,143,0,62,102)

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

Базис	В	x1	x2	x3	x4	x5	x6	x7
x4	143	5.5	1	5.5	1	0	0	0
x6	62	3	2	1	0	0	1	0
x7	102	1	2	2	0	-1	0	1
F(X0)	164M	-12+4M	-5+4M	-9+3M	0	-M	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

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

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

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x4	143	5.5	1	5.5	1	0	0	0	143
x6	62	3	2	1	0	0	1	0	31
x7	102	1	2	2	0	-1	0	1	51
F(X1)	164M	-12+4M	-5+4M	-9+3M	0	-M	0	0	0



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

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

Вместо переменной x6 в план 1 войдет переменная x2

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

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

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

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

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

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

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

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

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

B	x1	x2	x3
62 / 2 = 31	3 / 2 = 1.5	2 / 2 = 1	1 / 2 = 0.5
x4	x5	x6	x7
0 / 2 = 0	0 / 2 = 0	1 / 2 = 0.5	0 / 2 = 0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x4	112	4	0	5	1	0	-0.5	0
x2	31	1.5	1	0.5	0	0	0.5	0
x7	40	-2	0	1	0	-1	-1	1
F(X1)	155+40M	-4.5-2M	0	-6.5+M	0	-M	2.5-2M	0

Итерация №1.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai3

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

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

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

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x4	112	4	0	5	1	0	-0.5	0	22.4
x2	31	1.5	1	0.5	0	0	0.5	0	62
x7	40	-2	0	1	0	-1	-1	1	40
F(X2)	155+40M	-4.5-2M	0	-6.5+M	0	-M	2.5-2M	0	0

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

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

Вместо переменной x4 в план 2 войдет переменная x3

Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=5

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

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

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

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

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

B	x1	x2	x3	x4
112 / 5 = 22.4	4 / 5 = 0.8	0 / 5 = 0	5 / 5 = 1	1 / 5 = 0.2
x5	x6	x7
0 / 5 = 0	-0.5 / 5 = -0.1	0 / 5 = 0

После преобразований получаем новую таблицу:



Базис	В	x1	x2	x3	x4	x5	x6	x7
x3	22.4	0.8	0	1	0.2	0	-0.1	0
x2	19.8	1.1	1	0	-0.1	0	0.55	0
x7	17.6	-2.8	0	0	-0.2	-1	-0.9	1
F(X2)	300.6+17.6M	0.7-2.8M	0	0	1.3-0.2M	-M	1.85-1.9M	0

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

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

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

Базис	В	x1	x2	x3	x4	x5	x6	x7
x3	22.4	0.8	0	1	0.2	0	-0.1	0
x2	19.8	1.1	1	0	-0.1	0	0.55	0
x7	17.6	-2.8	0	0	-0.2	-1	-0.9	1
F(X3)	300.6+17.6M	0.7-2.8M	0	0	1.3-0.2M	-M	1.85-1.9M	0

Так как в оптимальном решении присутствуют искусственные переменные (x7 > 0), то задача не имеет допустимого решения.

Задача 6

Определим максимальное значение целевой функции F(X) = 15x1 + 12x2 - 8x3 при следующих условиях-ограничений.

2x1 + x2 + x3?50

3x1 + 2x2 + x3=60

5x1 + 3x2 + 4x3?10

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

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

2x1 + 1x2 + 1x3 + 1x4 + 0x5 = 50

3x1 + 2x2 + 1x3 + 0x4 + 0x5 = 60

5x1 + 3x2 + 4x3 + 0x4-1x5 = 10

Введем искусственные переменные x: в 2-м равенстве вводим переменную x6; в 3-м равенстве вводим переменную x7;

2x1 + 1x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 = 50

3x1 + 2x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 60

5x1 + 3x2 + 4x3 + 0x4-1x5 + 0x6 + 1x7 = 10

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = 15x1+12x2-8x3 - Mx6 - Mx7 > max

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

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

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

Из уравнений выражаем искусственные переменные:

x6 = 60-3x1-2x2-x3

x7 = 10-5x1-3x2-4x3+x5

которые подставим в целевую функцию:

F(X) = 15x1 + 12x2-8x3 - M(60-3x1-2x2-x3) - M(10-5x1-3x2-4x3+x5) > max или F(X) = (15+8M)x1+(12+5M)x2+(-8+5M)x3+(-M)x5+(-70M) > max

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



2	1	1	1	0	0	0
3	2	1	0	0	1	0
5	3	4	0	-1	0	1

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

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

Решим систему уравнений относительно базисных переменных:

x4, x6, x7,

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

X1 = (0,0,0,50,0,60,10)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	50	2	1	1	1	0	0	0
x6	60	3	2	1	0	0	1	0
x7	10	5	3	4	0	-1	0	1
F(X0)	-70M	-15-8M	-12-5M	8-5M	0	M	0	0

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (50 : 2 , 60 : 3 , 10 : 5 ) = 2

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	50	2	1	1	1	0	0	0	25
x6	60	3	2	1	0	0	1	0	20
x7	10	5	3	4	0	-1	0	1	2
F(X1)	-70M	-15-8M	-12-5M	8-5M	0	M	0	0	0

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

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

Вместо переменной x7 в план 1 войдет переменная x1.

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
50-(10 * 2):5	2-(5 * 2):5	1-(3 * 2):5	1-(4 * 2):5	1-(0 * 2):5	0-(-1 * 2):5	0-(0 * 2):5	0-(1 * 2):5
60-(10 * 3):5	3-(5 * 3):5	2-(3 * 3):5	1-(4 * 3):5	0-(0 * 3):5	0-(-1 * 3):5	1-(0 * 3):5	0-(1 * 3):5
10 : 5	5 : 5	3 : 5	4 : 5	0 : 5	-1 : 5	0 : 5	1 : 5
(0)-(10 * (-15-8M)):5	(-15-8M)-(5 * (-15-8M)):5	(-12-5M)-(3 * (-15-8M)):5	(8-5M)-(4 * (-15-8M)):5	(0)-(0 * (-15-8M)):5	(M)-(-1 * (-15-8M)):5	(0)-(0 * (-15-8M)):5	(0)-(1 * (-15-8M)):5

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	46	0	-1/5	-3/5	1	2/5	0	-2/5
x6	54	0	1/5	-12/5	0	3/5	1	-3/5
x1	2	1	3/5	4/5	0	-1/5	0	1/5
F(X1)	30-54M	0	-3-M	20+12/5M	0	-3-3/5M	0	3+13/5M

Итерация №1.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai5

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

min (46 :2/5 , 54 : 3/5 , - ) = 90

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	46	0	-1/5	-3/5	1	2/5	0	-2/5	115
x6	54	0	1/5	-12/5	0	3/5	1	-3/5	90
x1	2	1	3/5	4/5	0	-1/5	0	1/5	-
F(X2)	30-54M	0	-3-M	20+12/5M	0	-3-3/5M	0	3+13/5M	0

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

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

Вместо переменной x6 в план 2 войдет переменная x5.

Строка, соответствующая переменной x5 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=3/5

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
46-(54 * 2/5):3/5	0-(0 * 2/5):3/5	-1/5-(1/5 * 2/5):3/5	-3/5-(-12/5 * 2/5):3/5	1-(0 * 2/5):3/5	2/5-(3/5 * 2/5):3/5	0-(1 * 2/5):3/5	-2/5-(-3/5 * 2/5):3/5
54 : 3/5	0 : 3/5	1/5 : 3/5	-12/5 : 3/5	0 : 3/5	3/5 : 3/5	1 : 3/5	-3/5 : 3/5
2-(54 * -1/5):3/5	1-(0 * -1/5):3/5	3/5-(1/5 * -1/5):3/5	4/5-(-12/5 * -1/5):3/5	0-(0 * -1/5):3/5	-1/5-(3/5 * -1/5):3/5	0-(1 * -1/5):3/5	1/5-(-3/5 * -1/5):3/5
(3+13/5M)-(54 * (-3-3/5M)):3/5	(0)-(0 * (-3-3/5M)):3/5	(-3-M)-(1/5 * (-3-3/5M)):3/5	(20+12/5M)-(-12/5 * (-3-3/5M)):3/5	(0)-(0 * (-3-3/5M)):3/5	(-3-3/5M)-(3/5 * (-3-3/5M)):3/5	(0)-(1 * (-3-3/5M)):3/5	(3+13/5M)-(-3/5 * (-3-3/5M)):3/5

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



Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	10	0	-1/3	1/3	1	0	-2/3	0
x5	90	0	1/3	-21/3	0	1	12/3	-1
x1	20	1	2/3	1/3	0	0	1/3	0
F(X2)	300	0	-2	13	0	0	5+M	M

Итерация №2.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

min (- , 90 :1/3 , 20 : 2/3 ) = 30

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	10	0	-1/3	1/3	1	0	-2/3	0	-
x5	90	0	1/3	-21/3	0	1	12/3	-1	270
x1	20	1	2/3	1/3	0	0	1/3	0	30
F(X3)	300	0	-2	13	0	0	5+M	M	0

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

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

Вместо переменной x1 в план 3 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 3, получена в результате деления всех элементов строки x1 плана 2 на разрешающий элемент РЭ=2/3 На месте разрешающего элемента в плане 3 получаем 1.

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
10-(20 * -1/3):2/3	0-(1 * -1/3):2/3	-1/3-(2/3 * -1/3):2/3	1/3-(1/3 * -1/3):2/3	1-(0 * -1/3):2/3	0-(0 * -1/3):2/3	-2/3-(1/3 * -1/3):2/3	0-(0 * -1/3):2/3
90-(20 * 1/3):2/3	0-(1 * 1/3):2/3	1/3-(2/3 * 1/3):2/3	-21/3-(1/3 * 1/3):2/3	0-(0 * 1/3):2/3	1-(0 * 1/3):2/3	12/3-(1/3 * 1/3):2/3	-1-(0 * 1/3):2/3
20 : 2/3	1 : 2/3	2/3 : 2/3	1/3 : 2/3	0 : 2/3	0 : 2/3	1/3 : 2/3	0 : 2/3
(M)-(20 * (-2)):2/3	(0)-(1 * (-2)):2/3	(-2)-(2/3 * (-2)):2/3	(13)-(1/3 * (-2)):2/3	(0)-(0 * (-2)):2/3	(0)-(0 * (-2)):2/3	(5+M)-(1/3 * (-2)):2/3	(M)-(0 * (-2)):2/3

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	20	1/2	0	1/2	1	0	-1/2	0
x5	80	-1/2	0	-21/2	0	1	11/2	-1
x2	30	11/2	1	1/2	0	0	1/2	0
F(X3)	360	3	0	14	0	0	6+M	M

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	20	1/2	0	1/2	1	0	-1/2	0
x5	80	-1/2	0	-21/2	0	1	11/2	-1
x2	30	11/2	1	1/2	0	0	1/2	0
F(X4)	360	3	0	14	0	0	6+M	M



Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

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

x2 = 30

F(X) = 12*30 = 360

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

В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 20

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 80

Значение 3> 0 в столбце x1 означает, что использование x1 - не выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 14> 0 в столбце x3 означает, что использование x3 - не выгодно.

Значение 6+1M в столбце x6 означает, что теневая цена (двойственная оценка) равна 6+1M.

Значение 0+1M в столбце x7 означает, что теневая цена (двойственная оценка) равна 0+1M.

РГР3

Задача 7

программирование симплексный неравенство функция

Приведем систему ограничений к системе неравенств смысла ?, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = x1 - 2x2 - 4x3 + 2x4 + 3x5 при следующих условиях-ограничений.

2x1 + 3x2 - x3 + x4 + x5=18

2x2 - 3x3 - x4?-24

x1 - 4x2 + x4?-12

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

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

2x1 + 3x2-1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 18

0x1 + 2x2-3x3-1x4 + 0x5 + 1x6 + 0x7 = -24

1x1-4x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 = -12

Введем искусственные переменные x: в 1-м равенстве вводим переменную x8;

2x1 + 3x2-1x3 + 1x4 + 1x5 + 0x6 + 0x7 + 1x8 = 18

0x1 + 2x2-3x3-1x4 + 0x5 + 1x6 + 0x7 + 0x8 = -24

1x1-4x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 + 0x8 = -12

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = x1-2x2-4x3+2x4+3x5+Mx8 > min

Из уравнений выражаем искусственные переменные:

x8 = 18-2x1-3x2+x3-x4-x5

которые подставим в целевую функцию:

F(X) = x1-2x2-4x3 + 2x4 + 3x5 + M(18-2x1-3x2+x3-x4-x5) > min

или F(X) = (1-2M)x1+(-2-3M)x2+(-4+M)x3+(2-M)x4+(3-M)x5+(18M) > min

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

2	3	-1	1	1	0	0	1
0	2	-3	-1	0	1	0	0
1	-4	0	1	0	0	1	0

Решим систему уравнений относительно базисных переменных:

x8, x6, x7,

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

X1 = (0,0,0,0,0,-24,-12,18)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	18	2	3	-1	1	1	0	0	1
x6	-24	0	2	-3	-1	0	1	0	0
x7	-12	1	-4	0	1	0	0	1	0
F(X0)	18M	-1+2M	2+3M	4-M	-2+M	-3+M	0	0	0

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

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 2-ая строка, а переменную x6 следует вывести из базиса.

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

Минимальное значение и соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	18	2	3	-1	1	1	0	0	1
x6	-24	0	2	-3	-1	0	1	0	0
x7	-12	1	-4	0	1	0	0	1	0
F(X0)	18M	-1+2M	2+3M	4-M	-2+M	-3+M	0	0	0
и	0	-	-	4-M : (-3)	-2+M : (-1)	-	-	-	-

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

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	-6	2	5	-4	0	1	1	0	1
x4	24	0	-2	3	1	0	-1	0	0
x7	-36	1	-2	-3	0	0	1	1	0
F(X0)	48-6M	-1+2M	-2+5M	10-4M	0	-3+M	-2+M	0	0

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
18-(-24 * 1):-1	2-(0 * 1):-1	3-(2 * 1):-1	-1-(-3 * 1):-1	1-(-1 * 1):-1	1-(0 * 1):-1	0-(1 * 1):-1	0-(0 * 1):-1	1-(0 * 1):-1
-24 : -1	0 : -1	2 : -1	-3 : -1	-1 : -1	0 : -1	1 : -1	0 : -1	0 : -1
-12-(-24 * 1):-1	1-(0 * 1):-1	-4-(2 * 1):-1	0-(-3 * 1):-1	1-(-1 * 1):-1	0-(0 * 1):-1	0-(1 * 1):-1	1-(0 * 1):-1	0-(0 * 1):-1
(0)-(-24 * (0)):-1	(-1+2M)-(0 * (0)):-1	(-2+5M)-(2 * (0)):-1	(10-4M)-(-3 * (0)):-1	(0)-(-1 * (0)):-1	(-3+M)-(0 * (0)):-1	(-2+M)-(1 * (0)):-1	(0)-(0 * (0)):-1	(0)-(0 * (0)):-1

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

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 3-ая строка, а переменную x7 следует вывести из базиса.

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

Минимальное значение и соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3). 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	-6	2	5	-4	0	1	1	0	1
x4	24	0	-2	3	1	0	-1	0	0
x7	-36	1	-2	-3	0	0	1	1	0
F(X0)	48-6M	-1+2M	-2+5M	10-4M	0	-3+M	-2+M	0	0
и	0	-	-2+5M : (-2)	10-4M : (-3)	-	-	-	-	-

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

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x8	42	2/3	72/3	0	0	1	-1/3	-11/3	1
x4	-12	1	-4	0	1	0	0	1	0
x3	12	-1/3	2/3	1	0	0	-1/3	-1/3	0
F(X1)	-72+42M	21/3+2/3M	-82/3+72/3M	0	0	-3+M	11/3-M	31/3-11/3M	0

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

B	x 1

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

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

  Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
  
  курсовая работа [232,4 K], добавлен 01.06.2009
  

• Решение задачи нахождения минимума целевой функции

  Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
  
  курсовая работа [511,9 K], добавлен 20.07.2012
  

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

  Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
  
  курсовая работа [100,0 K], добавлен 31.10.2014
  

• Решение задач симплекс-методом

  Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
  
  контрольная работа [191,1 K], добавлен 05.04.2016
  

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

  Создание математической модели, приведение ее к виду задачи линейного программирования. Геометрическая трактовка решения. Определение области допустимых значений. Составление симплекс-таблиц. Разработка опорного плана задачи методом минимального элемента.
  
  контрольная работа [260,2 K], добавлен 22.12.2013
  

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

  Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
  
  контрольная работа [362,3 K], добавлен 03.11.2011
  

• Анализ методов определения минимального, максимального значения функции при наличии ограничений

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

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

  Составление производственного плана трех видов изделий при определенных возможностях машин. Написание алгоритма решения задачи симплексным методом: описание переменных, констант, нахождение разрешающего элемента, вычисление таблицы методом прямоугольника.
  
  методичка [237,2 K], добавлен 25.09.2010
  

• Основы математического моделирования

  Методы линейного программирования в математическом моделировании технологических процессов. Направление оптимизации целевой функции. Ввод функциональных зависимостей для целевой функции и ограничений осуществляется с использованием Мастера функций.
  
  курсовая работа [994,6 K], добавлен 04.01.2014
  

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

  Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
  
  курсовая работа [132,0 K], добавлен 09.12.2008
  

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