Исследования и проектирования систем на базе ЭВМ

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

ВВЕДЕНИЕ

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

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

Для осуществления вычислительного эксперимента на ЭВМ необходимо разработать алгоритм реализации математической модели. Формализация процесса проектирования на основе математического моделирования позволяет его автоматизировать. Одним из основных компонентов системы автоматизированного проектирования является математическое обеспечение, включающее математические модели объектов проектирования и их элементов, методы и алгоритмы выполнения проектных операций и процедур. моделирование симплексный транспортная задача

Исходя из вышесказанного, можно сделать вывод, что дисциплина «Моделирование систем» -- одна из базовых дисциплин подготовки инженеров-системотехников по специальности Автоматизация технологических процессов и производств.

Целью курсовой работы является практическое усвоение основных разделов дисциплины «Моделирование систем», развитие практических навыков комплексного решения задач исследования и проектирования систем на базе ЭВМ.

1. СИМПЛЕКС-МЕТОД

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

Определим максимальное значение целевой функции F(X) = 4x₁ + 3x₂ + 6x₃ + 7x₄ при следующих условиях-ограничений.

2x₁ + x₂ + x₃ + x₄?280

x₁ + x₃ + x₄?80

x₁ + 2x₂ + x₃?250

x₁ + x₂ + x₃ + x₄?0

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

В 1-м неравенстве смысла (?) вводим базисную переменную x₅. В 2-м неравенстве смысла (?) вводим базисную переменную x₆. В 3-м неравенстве смысла (?) вводим базисную переменную x₇. В 4-м неравенстве смысла (?) вводим базисную переменную x₈ со знаком минус.

2x₁ + 1x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ = 280

1x₁ + 0x₂ + 1x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ = 80

1x₁ + 2x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ = 250

1x₁ + 1x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ = 0

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

2x₁ + 1x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 280

1x₁ + 0x₂ + 1x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ = 80

1x₁ + 2x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 250

1x₁ + 1x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 1x₉ = 0

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

F(X) = 4x₁+3x₂+6x₃+7x₄ - Mx₉ > max

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

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

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

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

x₉ = 0-x₁-x₂-x₃-x₄+x₈

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

F(X) = 4x₁ + 3x₂ + 6x₃ + 7x₄ - M(0-x₁-x₂-x₃-x₄+x₈) > max

или

F(X) = (4+M)x₁+(3+M)x₂+(6+M)x₃+(7+M)x₄+(-M)x₈ > max

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

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

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

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

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

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

X1 = (0,0,0,0,280,80,250,0,0)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	280	2	1	1	1	1	0	0	0	0
x6	80	1	0	1	1	0	1	0	0	0
x7	250	1	2	1	0	0	0	1	0	0
x9	0	1	1	1	1	0	0	0	-1	1
F(X0)	0	-4-M	-3-M	-6-M	-7-M	0	0	0	M	0

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

Итерация №0.

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

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

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

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

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

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

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

min (280 : 1 , 80 : 1 , - , 0 : 1 ) = 0

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5	280	2	1	1	1	1	0	0	0	0	280
x6	80	1	0	1	1	0	1	0	0	0	80
x7	250	1	2	1	0	0	0	1	0	0	-
x9	0	1	1	1	1	0	0	0	-1	1	0
F(X1)	0	-4-M	-3-M	-6-M	-7-M	0	0	0	M	0	0

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

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

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

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
280-(0 * 1):1	2-(1 * 1):1	1-(1 * 1):1	1-(1 * 1):1	1-(1 * 1):1	1-(0 * 1):1	0-(0 * 1):1	0-(0 * 1):1	0-(-1 * 1):1	0-(1 * 1):1
80-(0 * 1):1	1-(1 * 1):1	0-(1 * 1):1	1-(1 * 1):1	1-(1 * 1):1	0-(0 * 1):1	1-(0 * 1):1	0-(0 * 1):1	0-(-1 * 1):1	0-(1 * 1):1
250-(0 * 0):1	1-(1 * 0):1	2-(1 * 0):1	1-(1 * 0):1	0-(1 * 0):1	0-(0 * 0):1	0-(0 * 0):1	1-(0 * 0):1	0-(-1 * 0):1	0-(1 * 0):1
0 : 1	1 : 1	1 : 1	1 : 1	1 : 1	0 : 1	0 : 1	0 : 1	-1 : 1	1 : 1
(0)-(0 * (-7-M)):1	(-4-M)-(1 * (-7-M)):1	(-3-M)-(1 * (-7-M)):1	(-6-M)-(1 * (-7-M)):1	(-7-M)-(1 * (-7-M)):1	(0)-(0 * (-7-M)):1	(0)-(0 * (-7-M)):1	(0)-(0 * (-7-M)):1	(M)-(-1 * (-7-M)):1	(0)-(1 * (-7-M)):1

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	280	1	0	0	0	1	0	0	1	-1
x6	80	0	-1	0	0	0	1	0	1	-1
x7	250	1	2	1	0	0	0	1	0	0
x4	0	1	1	1	1	0	0	0	-1	1
F(X1)	0	3	4	1	0	0	0	0	-7	7+M

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

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

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

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

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

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

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

min (280 : 1 , 80 : 1 , - , - ) = 80

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5	280	1	0	0	0	1	0	0	1	-1	280
x6	80	0	-1	0	0	0	1	0	1	-1	80
x7	250	1	2	1	0	0	0	1	0	0	-
x4	0	1	1	1	1	0	0	0	-1	1	-
F(X2)	0	3	4	1	0	0	0	0	-7	7+M	0

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
280-(80 * 1):1	1-(0 * 1):1	0-(-1 * 1):1	0-(0 * 1):1	0-(0 * 1):1	1-(0 * 1):1	0-(1 * 1):1	0-(0 * 1):1	1-(1 * 1):1	-1-(-1 * 1):1
80 : 1	0 : 1	-1 : 1	0 : 1	0 : 1	0 : 1	1 : 1	0 : 1	1 : 1	-1 : 1
250-(80 * 0):1	1-(0 * 0):1	2-(-1 * 0):1	1-(0 * 0):1	0-(0 * 0):1	0-(0 * 0):1	0-(1 * 0):1	1-(0 * 0):1	0-(1 * 0):1	0-(-1 * 0):1
0-(80 * -1):1	1-(0 * -1):1	1-(-1 * -1):1	1-(0 * -1):1	1-(0 * -1):1	0-(0 * -1):1	0-(1 * -1):1	0-(0 * -1):1	-1-(1 * -1):1	1-(-1 * -1):1
(7+M)-(80 * (-7)):1	(3)-(0 * (-7)):1	(4)-(-1 * (-7)):1	(1)-(0 * (-7)):1	(0)-(0 * (-7)):1	(0)-(0 * (-7)):1	(0)-(1 * (-7)):1	(0)-(0 * (-7)):1	(-7)-(1 * (-7)):1	(7+M)-(-1 * (-7)):1

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	200	1	1	0	0	1	-1	0	0	0
x8	80	0	-1	0	0	0	1	0	1	-1
x7	250	1	2	1	0	0	0	1	0	0
x4	80	1	0	1	1	0	1	0	0	0
F(X2)	560	3	-3	1	0	0	7	0	0	M

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

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

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

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

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

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

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

min (200 : 1 , - , 250 : 2 , - ) = 125

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5	200	1	1	0	0	1	-1	0	0	0	200
x8	80	0	-1	0	0	0	1	0	1	-1	-
x7	250	1	2	1	0	0	0	1	0	0	125
x4	80	1	0	1	1	0	1	0	0	0	-
F(X3)	560	3	-3	1	0	0	7	0	0	M	0

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
200-(250 * 1):2	1-(1 * 1):2	1-(2 * 1):2	0-(1 * 1):2	0-(0 * 1):2	1-(0 * 1):2	-1-(0 * 1):2	0-(1 * 1):2	0-(0 * 1):2	0-(0 * 1):2
80-(250 * -1):2	0-(1 * -1):2	-1-(2 * -1):2	0-(1 * -1):2	0-(0 * -1):2	0-(0 * -1):2	1-(0 * -1):2	0-(1 * -1):2	1-(0 * -1):2	-1-(0 * -1):2
250 : 2	1 : 2	2 : 2	1 : 2	0 : 2	0 : 2	0 : 2	1 : 2	0 : 2	0 : 2
80-(250 * 0):2	1-(1 * 0):2	0-(2 * 0):2	1-(1 * 0):2	1-(0 * 0):2	0-(0 * 0):2	1-(0 * 0):2	0-(1 * 0):2	0-(0 * 0):2	0-(0 * 0):2
(M)-(250 * (-3)):2	(3)-(1 * (-3)):2	(-3)-(2 * (-3)):2	(1)-(1 * (-3)):2	(0)-(0 * (-3)):2	(0)-(0 * (-3)):2	(7)-(0 * (-3)):2	(0)-(1 * (-3)):2	(0)-(0 * (-3)):2	(M)-(0 * (-3)):2

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	75	1/2	0	-1/2	0	1	-1	-1/2	0	0
x8	205	1/2	0	1/2	0	0	1	1/2	1	-1
x2	125	1/2	1	1/2	0	0	0	1/2	0	0
x4	80	1	0	1	1	0	1	0	0	0
F(X3)	935	41/2	0	21/2	0	0	7	11/2	0	M

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	75	1/2	0	-1/2	0	1	-1	-1/2	0	0
x8	205	1/2	0	1/2	0	0	1	1/2	1	-1
x2	125	1/2	1	1/2	0	0	0	1/2	0	0
x4	80	1	0	1	1	0	1	0	0	0
F(X4)	935	41/2	0	21/2	0	0	7	11/2	0	M

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

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

x₂ = 125

x₄ = 80

F(X) = 3*125 + 7*80 = 935

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

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

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

Значение 4¹/₂> 0 в столбце x₁ означает, что использование x₁ - не выгодно.

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

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

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

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

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

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

2. ГЕОМЕТРИЧЕСКИЙ МЕТОД

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

2x1+x2?6 (1)

7x1+8x2?56 (2)

x1+2x2?6 (3)

x1+x2?0 (4)

x1?0 (5)

x2?0 (6)

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

Построим уравнение 2x1+x2 = 6 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 6. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 3. Соединяем точку (0;6) с (3;0) прямой линией.

Построим уравнение 7x1+8x2 = 56 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 7. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;7) с (8;0) прямой линией.

Построим уравнение x1+2x2 = 6 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 3. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 6. Соединяем точку (0;3) с (6;0) прямой линией.

Построим уравнение x1+x2 = 0 по двум точкам. Для нахождения первой точки приравниваем x1 = 1. Находим x2 = -1. Для нахождения второй точки приравниваем x2 = 1. Находим x1 = -1. Соединяем точку (1;-1) с (-1;1) прямой линией.

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = x1+x2 > min.

Построим прямую, отвечающую значению функции F = 0: F = x1+x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (1; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб

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

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (2) и (6), то ее координаты удовлетворяют уравнениям этих прямых:

7x1+8x2=56

x1=0

Решив систему уравнений, получим: x1 = 0, x2 = 7

Откуда найдем минимальное значение целевой функции:

F(X) = 1*0 + 1*7 = 7

3. Транспортная задача

Постановка задачи:

Пункты отправления	Пункты назначения	Запасы
	B1	B2	B3	B4
A1	2	4	7	9	200
A2	5	1	8	12	270
A3	11	6	4	13	130
Потребности	80	80	60	80

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

F = ??c_ijx_ij, (1)

при условиях:

?x_ij = a_i, i = 1,2,…, m, (2)

?x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	2	4	7	9	200
2	5	1	8	12	270
3	11	6	4	13	130
Потребности	80	80	60	80

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

?a = 200 + 270 + 130 = 600

?b = 80 + 80 + 60 + 80 = 300

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

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

	1	2	3	4	5	Запасы
1	2	4	7	9	0	200
2	5	1	8	12	0	270
3	11	6	4	13	0	130
Потребности	80	80	60	80	300

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

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

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

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

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

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

x₂₂ = min(270,80) = 80.

2	x	7	9	0	200
5	1	8	12	0	270 - 80 = 190
11	x	4	13	0	130
80	80 - 80 = 0	60	80	300	0

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

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

x₁₁ = min(200,80) = 80.

2	x	7	9	0	200 - 80 = 120
x	1	8	12	0	190
x	x	4	13	0	130
80 - 80 = 0	0	60	80	300	0

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

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

x₃₃ = min(130,60) = 60.

2	x	x	9	0	120
x	1	x	12	0	190
x	x	4	13	0	130 - 60 = 70
0	0	60 - 60 = 0	80	300	0

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

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

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

2	x	x	9	0	120 - 80 = 40
x	1	x	x	0	190
x	x	4	x	0	70
0	0	0	80 - 80 = 0	300	0

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

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

x₁₅ = min(40,300) = 40.

2	x	x	9	0	40 - 40 = 0
x	1	x	x	0	190
x	x	4	x	0	70
0	0	0	0	300 - 40 = 260	0

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

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

x₂₅ = min(190,260) = 190.

2	x	x	9	0	0
x	1	x	x	0	190 - 190 = 0
x	x	4	x	0	70
0	0	0	0	260 - 190 = 70	0

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

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

x₃₅ = min(70,70) = 70.

2	x	x	9	0	0
x	1	x	x	0	0
x	x	4	x	0	70 - 70 = 0
0	0	0	0	70 - 70 = 0	0

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

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

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

F(x) = 2*80 + 9*80 + 0*40 + 1*80 + 0*190 + 4*60 + 0*70 = 1200

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

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

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

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

u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

u₂ + v₅ = 0; 0 + u₂ = 0; u₂ = 0

u₂ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₃ + v₅ = 0; 0 + u₃ = 0; u₃ = 0

u₃ + v₃ = 4; 0 + v₃ = 4; v₃ = 4

	v1=2	v2=1	v3=4	v4=9	v5=0
u1=0	2[80]	4	7	9[80]	0[40]
u2=0	5	1[80]	8	12	0[190]
u3=0	11	6	4[60]	13	0[70]

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

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

F(x) = 2*80 + 9*80 + 0*40 + 1*80 + 0*190 + 4*60 + 0*70 = 1200

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

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

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

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

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

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

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

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

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

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

4. ТЕОРИЯ ИГР

Постановка:

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	a = min(Ai)
A1	3	5	3
A2	4	6	4
b = max(Bi)	4	6

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 4, которая указывает на максимальную чистую стратегию A₂.

Верхняя цена игры b = min(b_j) = 4.

Седловая точка (2, 1) указывает решение на пару альтернатив (A2,B1). Цена игры равна 4.

3. Находим решение игры в смешанных стратегиях.

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии A₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A₂.

Решение игры (<i>2 x n</i>) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B₁B₁ и B₄B₄, для которых можно записать следующую систему уравнений:

y = 3 + (4 - 3)p₂

Откуда

p₁ = 0

p₂ = 1

Цена игры, y = 4

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B₂, которая дает явно больший проигрыш игроку B, и, следовательно, q₂ = 0.

3q₁ = y

4q₁ = y

q₁+q₂ = 1

или

3q₁ = 4

4q₁ = 4

q₁+q₂ = 1

Решая эту систему, находим:

q₁ = 1.

Ответ:

Цена игры: y = 4, векторы стратегии игроков:

Q(1, 0), P(0, 1)

4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (3*1) + (5*0) = 3 ? v

M(P₂;Q) = (4*1) + (6*0) = 4 = v

M(P;Q₁) = (3*0) + (4*1) = 4 = v

M(P;Q₂) = (5*0) + (6*1) = 6 ? v

Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Задача:

Матричная игра задана следующей платежной матрицей :

	Стратегии "B"
Стратегии "A"	B1	B2
A1	3	5
A2	4	6

Определим нижнюю цену игры - б

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

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец

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

	Стратегии "B"
Стратегии "A"	B1	B2	Минимумы строк
A1	3	5	3
A2	4	6	4*

В нашем случае нижняя цена игры равна: б = 4, и для того чтобы гарантировать себе выигрыш не хуже чем 4 мы должны придерживаться стратегии A₂

Определим верхнюю цену игры - в

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

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

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

	Стратегии "B"
Стратегии "A"	B1	B2	Минимумы строк
A1	3	5	3
A2	4	6	4*
Максимумы столбцов	4+	6

В нашем случае верхняя цена игры равна: в = 4, и для того чтобы гарантировать себе проигрыш не хуже чем 4 противник ( игрок "B") должен придерживаться стратегии B₁

Сравним нижнюю и верхнюю цены игры, в данной задаче они совпадают, т.е. б = в = 4 . Это значит, что игра имеет решение в так называемых "чистых", минимаксных стратегиях. Это как раз те стратегии для игроков "A" и "B" которые были найдены выше, при поиске нижней и верхней цен игры. То есть, в нашем случае для игрока "A" оптимальной будет стратегия A₂, а для игрока "В" - B₁. Нетрудно заметить, что элемент платежной матрицы расположенный на пересечении чистых оптимальных стратегий (строка 2, столбец 1) является одновременно минимальным в строке и максимальным в столбце (отмечен знаками *+ см.). Такие элементы называются седловыми точками, именно их наличие и определяет существование решения игры в чистых стратегиях, а его значение (в нашем случае 4) совпадает с чистой ценой игры или просто ценой игры - v. Пара оптимальных стратегий, в играх имеющих седловую точку, всегда проходит через последнюю.

	Стратегии "B"
Стратегии "A"	B1	B2	Минимумы строк
A1	3	5	3
A2	4*+	6	4*
Максимумы столбцов	4...

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

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

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

• Моделирование процессов и объектов в металлургии

  Основы понятия регрессионного анализа и математического моделирования. Численное решение краевых задач математической физики методом конечных разностей. Решение стандартных и оптимизационных задач, систем линейных уравнений. Метод конечных элементов.
  
  реферат [227,1 K], добавлен 18.04.2015
  

• Моделирование оптимизационных задач экономики с использованием теории игр

  Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Деловая игра "Снабжение". Решение матричной игры в смешанных стратегиях.
  
  курсовая работа [1,8 M], добавлен 15.10.2012
  

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

  Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
  
  курсовая работа [56,9 K], добавлен 04.05.2011
  

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

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

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

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

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

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

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

  Задачи операционного исследования. Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе технологии симплекс-метода. Анализ результатов базовой аналитической модели и предложения по модификации.
  
  курсовая работа [1,5 M], добавлен 12.12.2009
  

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

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

• Модифицированный симплексный метод

  Сущность модифицированного симплексного метода при решении задач линейного программирования. Характеристика подходов к вычислительной схеме симплекс-метода. Использование в экономическом моделировании. Графический способ решения транспортной задачи.
  
  контрольная работа [32,0 K], добавлен 15.03.2016
  

• Формирование и решение линейных задач

  Моделирование экономических систем: понятие и принципы, типы моделей и оценка их адекватности. Примеры задач линейного программирования: транспортная задача, ее общая формулировка и графическая интерпретация решения задачи. Анализ симплекс-таблиц.
  
  курсовая работа [237,9 K], добавлен 22.11.2012
  

• Анализ использования теории игр как механизма решения практических задач "Закупка угля" и "Вступление на рынок"

  Основные понятия и критерии теории игр. Решение практических экономических задач с использованием механизма теории игр, а также создание необходимых рекомендаций к данным задачам. Научное обоснование снижения розничных цен и уровня товарных запасов.
  
  научная работа [184,7 K], добавлен 12.10.2011
  

• Метод статистического моделирования (метод Монте-Карло)

  Изучение особенностей метода статистического моделирования, известного в литературе под названием метода Монте-Карло, который дает возможность конструировать алгоритмы для ряда важных задач. Решение задачи линейного программирования графическим методом.
  
  контрольная работа [1,2 M], добавлен 17.12.2014
  

• Использование симплексного метода для решения задач линейного программирования. Способы решения транспортной задачи

  Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
  
  контрольная работа [135,3 K], добавлен 01.06.2014
  

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

  Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
  
  контрольная работа [613,3 K], добавлен 18.02.2014
  

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

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

• Методы решения транспортных задач

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

• Решение транспортных задач

  Понятие классической транспортной задачи, классификация задач по критерию стоимости и времени. Методы решения задач: симплекс, северо-западного угла (диагональный), наименьшего элемента, потенциалов решения, теория графов. Определение и применение графов.
  
  курсовая работа [912,1 K], добавлен 22.06.2015
  

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

  Особенности решения задач линейного программирования симплекс-методом. Управляемые параметры, ограничения. Изучение метода потенциалов в процессе решения транспортной задачи. Создание концептуальной модели. Понятие стратификации, детализации, локализации.
  
  лабораторная работа [869,0 K], добавлен 17.02.2012
  

• Решение экономических задач оптимизационного типа

  Исследование методики построения модели и решения на ЭВМ с ее помощью оптимизационных экономико-математических задач. Характеристика программных средств, позволяющих решать такие задачи на ЭВМ. Определение оптимального варианта производства продукции.
  
  лабораторная работа [79,3 K], добавлен 07.12.2013
  

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