Геометрическая интерпретация и графическое решение ЗЛП.

Понятие симплексного метода.

Симплекс-метод – один из наиболее эффективных методов численного решения задач ЛП. Суть понятия «симплекс» заключается в следующем. Для тела в k -мерном пространстве симплексом называется множество, состоящее из k +1 вершин этого тела. Так, при k = 2, т.е. на плоскости, симплексом будут вершины треугольника; при k = 3 симплексом являются вершины четырехгранника, например тетраэдра, и т.д. Такое название методу дано по той причине, что в его основе лежит последовательный перебор вершин ОДЗП с целью определения координат той вершины, в которой функция цели имеет кстремальное значение.

Решение задачи с помощью симплекс-метода разбивается на два основных этапа. На первом этапе находят одно из решений, удовлетворяющее системе ограничений. Системы, в которых переменных больше, чем ограничений N > m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных. При этом остается система m уравнений с m неизвестными, которая имеет решение, если определитель системы отличен от нуля. В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободными переменными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получим базисное решение.

В системе из m уравнений с N неизвестными общее число базисных решений при N > m определяется числом сочетаний

Базисное решение, в котором все x_i0, i = 1,m, называется допустимым базисным решением. Таким образом, первый этап решения, используя симплекс-метод, завершается нахождением допустимого базисного решения, хотя бы и неудачного.

На втором этапе производится последовательное улучшение найденного решения. При этом осуществляется переход от одного допустимого базисного решения к другому таким образом, чтобы значение целевой функции улучшилось. Процесс решения, используя симплекс-метод, продолжается до тех пор, пока не будет достигнуто наименьшее (или наибольшее) значение функции цели. Геометрически это означает переход по ребрам из одной вершины многогранника допустимых значений в другую по направлению к той, в которой значение функции цели достигает экстремума. Симплекс-метод дает оптимальную процедуру перебора базисных решений и обеспечивает сходимость к экстремальной точке за конечное число шагов. Используя симплекс-метод, вычисления на втором этапе ведутся по следующей схеме:

1) базисные переменные и функция цели выражаются через небазисные переменные;

2) по определенному правилу выбирается та из небазисных переменных, изменение значения которой способно улучшить значение F(x), и она вводитя в базис;

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

4) базисные переменные и функция цели выражаются через новые небазисные переменные, и повторяются операции 2) и 3).

Если на определенном шаге в симплекс-методе окажется, что изменение значений любой из небазисных переменных не может улучшить F(x), то последнее базисное решение оказывается оптимальным.

Рассмотрим пример, относящийся к задачам организационно-экономического управления и помогающий уяснить содержание симплекс-метода.

Понятие двойственности. Построение пары взаимно двойственных

Задач.

92. Первая теорема двойственности и ее экономическое содержание.

93. Вторая теорема двойственности и ее экономическое содержание.

 

1. Понятие о первообразной и неопределенном интеграле.

2. Основные свойства неопределенного интеграла.

3. Основные методы интегрирования. Метод замены переменной интегрирования.

4. Основные методы интегрирования. Интегрирование по частям.

5. Интегрирование простейших иррациональностей.

6. Понятие определенного интеграла.

7. Геометрический смысл определенного интеграла.

8. Основные свойства определенного интеграла.

9. Интеграл с переменным верхним пределом. Формула Ньютона-Лейбница.

10. Замена переменной и интегрирование по частям в определенном интеграле.

11. Несобственные интегралы с бесконечными пределами интегрирования.

12. Несобственные интегралы от неограниченных функций.

13. Дифференциальные уравнения первого порядка. Общие понятия.

14. Дифференциальные уравнения с разделяющимися переменными. Пример.

15. Однородные дифференциальные уравнения первого порядка (определение, метод решения).

16. Линейные дифференциальные уравнения первого порядка (определение, методы решения).

17. Дифференциальные уравнения высших порядков. Общие понятия.

18. Уравнение вида .

19. Уравнения вида , не содержащие искомой функции и ее производных .

20. Уравнения вида , не содержащие независимой переменной.

21. Линейные однородные дифференциальные уравнения с постоянными коэффициентами.

22. Решение линейного неоднородного дифференциального уравнения методом вариации произвольных постоянных.

23. Понятие числового ряда. Основные понятия.

24. Свойства сходящихся рядов.

25. Необходимое условие сходимости числового ряда. Достаточное условие расходимости числового ряда.

26. Признаки сравнения для числовых знакоположительных рядов.

27. Достаточные признаки сходимости числовых знакоположительных рядов.

28. Понятие знакочередующегося ряда. Теорема Лейбница.

29. Предмет теории вероятностей.

30. Виды случайных событий.

31. Классическое определение вероятности.

32. Свойства вероятности.

33. Понятие относительной частоты. Статистическая вероятность.

34. Геометрические вероятности.

35. Основные формулы комбинаторики.

36. Теоремы сложения вероятностей.

37. Теоремы умножения вероятностей.

38. Формула полной вероятности.

39. Вероятность гипотез. Формулы Бейеса.

40. Повторение испытаний. Формула Бернулли.

41. Повторение испытаний. Локальная теорема Лапласа.

42. Повторение испытаний. Интегральная теорема Лапласа.

43. Понятие случайной величины. Закон распределения вероятностей ДСВ.

44. Функция распределения вероятностей случайной величины. Свойства функции распределения.

45. График функции распределения.

46. Плотность распределения вероятностей НСВ. Свойства плотности распределения.

47. Нахождение функции распределения по известной плотности распределения.

48. Математическое ожидание ДСВ.

49. Свойства математического ожидания. Математическое ожидание числа появлений события в независимых испытаниях.

50. Дисперсия дискретной случайной величины.

51. Свойства дисперсии. Дисперсия числа появлений события в независимых испытаниях.

52. Числовые характеристики непрерывных случайных величин.

53. Понятие о теоретических моментах распределения.

54. Биномиальное распределение.

55. Распределение Пуассона.

56. Простейший поток событий.

57. Геометрическое распределение.

58. Гипергеометрическое распределение.

59. Равномерное распределение.

60. Нормальное распределение.

61.Нормальная кривая. Влияние параметров нормального распределения на форму нормальной кривой.

62. Показательное распределение.

63. Функция надежности. Показательный закон надежности.

64. Теорема Чебышева. Ее сущность и значение для практики.

65. Предельные теоремы теории вероятностей. Теорема Бернулли.

66. Задачи математической статистики.

67. Генеральная и выборочная совокупности. Типы выборок.

68. Статистический ряд. Статистическое распределение выборки.

69. Эмпирическая функция распределения.

70. Графическое изображение статистических рядов.

71. Несмещенные, эффективные и состоятельные оценки.

72. Выборочная средняя.

73. Выборочная дисперсия и выборочное среднее квадратическое отклонение.

74. Исправленная выборочная дисперсия.

75. Обычные, начальные и центральные эмпирические моменты.

76. Точность оценки. Метод моментов.

77. Понятие об интервальной оценке. Доверительная вероятность (надежность). Доверительный интервал.

78. Интервальные оценки для математического ожидания и среднего квадратического отклонения СВ, имеющей нормальное распределение.

79. Понятие о гипотезе. Виды гипотез.

80. Статистическая проверка гипотез. Отыскание критической области.

81. Статистическая проверка параметрических гипотез. Ошибки первого и второго рода.

82. Статистический критерий проверки нулевой гипотезы.

83. Сравнение двух дисперсий нормальных генеральных совокупностей.

84. Сравнение двух средних генеральных совокупностей, дисперсии которых известны (большие независимые выборки).

85. Сравнение двух средних нормальных генеральных совокупностей, дисперсии которых неизвестны и одинаковы (малые независимые выборки).

86. Критерий согласия Пирсона.

87. Предмет линейного программирования. Понятие задачи линейного программирования.

88. Формы записи ЗЛП, их эквивалентность. Преобразование ЗЛП к канонической форме.

89. Геометрическая интерпретация и графическое решение ЗЛП.

90. Понятие симплексного метода.

91. Понятие двойственности. Построение пары взаимно двойственных задач.

92. Первая теорема двойственностии ее экономическое содержание.

93. Вторая теорема двойственностии ее экономическое содержание.