Формулировка задачи.

Даны линейная функция

Z = С₁х₁+С₂х₂+... +С_Nx_N (1.1)

и система линейных ограничений

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

. . . . . . . . . . . . . . . . . . . . . . . . . (1.2)

a_i1x₁ + a_i2x₂ + ... + a_iNХ_N = b_i

. . . . . . . . . . . . . . . . . . . . . . . . .

a_M1x₁ + a_M2x₂ + ... + a_MNХ_N = b_M

x_j 0 (j = 1, 2, ... ,n) (1.3)

где а_ij, b_j и С_j - заданные постоянные величины.

Найти такие неотрицательные значения х₁, х₂, ..., х_n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи.

Минимизировать линейную функцию Z = СХ при ограничениях

А₁х₁ + А₂x₂ + ... + А_Nx_N = А_о, X₀ (1.4)

где С = (с₁, с₂, ..., с_N); Х = (х₁, х₂, ..., х_N); СХ - скалярное произведение; векторы

A1 = , A2 = ,..., AN = , A0 =

состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи.

Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х₀, где С = (с₁, с₂, ..., с_N) - матрица-cтрока; А = (а_ij) - матрица системы;

Х = - матрица-столбец, А₀ = матрица-столбец

Минимизировать линейную функцию Z = С_jх_j при ограничениях.

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, ..., х_N), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х₁, х₂, ..., х_N) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

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

3. Содержание

   • Тема 1. Классификация моделей.
   • Тема 1. Классификация моделей.
   • Основные признаки классификации моделей.
   • Область использования.
   • Учет в модели временного фактора.
   • Способ представления модели.
   • Тема 2. Классификация языков компьютерного моделирования.
   • Тема 3. Этапы и цели компьютерного математического моделирования.
   • Раздел 1. Задачи линейного программирования.
   • Тема 1. Математическое программирование. Общий вид задач линейного программирования.
   • Формулировка задачи.
   • Геометрическая интерпретация задачи линейного программирования.
   • Найти минимальное значение линейной функции
   • Тема 2. Графический метод решения задач линейного программирования.
   • Примеры задач, решаемых графическим методом.
   • Обобщение графического метода решения задач линейного программирования.
   • Тема 3. Симплекс - метод.
   • Каноническая задача лп на максимум.
   • Вспомогательная задача лп.
   • Алгоритм метода искусственного базиса
   • Вспомогательная задача лп.
   • Алгоритм метода искусственного базиса.
   • Тема 4. Транспортная задача.
   • 4.2 Составление опорного плана.
   • 4.3 Метод потенциалов.
   • Раздел 2. Теория графов.
   • Тема 1. Основные понятия теории графов.
   • Элементы множества V называются вершинами графа g (или узлами), элементы множества u-его ребрами. Вершины и ребра графа называют также его элементами и вместо VV и u u пишут Vg и ug.
   • 1.2 Операции над графами.
   • 1.3.Связность графов.
   • 1.4 Эйлеровы графы.
   • 1.5 Гамильтоновы графы.
   • Тема 2. Поиск пути в графе.
   • 2.2 Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Дейкстры).
   • 2.3 .Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).
   • 2.4 Путь с минимальным количеством промежуточных вершин (волновой алгоритм).
   • 2.5 Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена).
   • Тема 3. Задачи о минимальном остове.
   • 3.1 Деревья.
   • 3.1 Построение минимального остовного дерева (алгоритм Краскала).
   • 3.1 Деревья.
   • 3.1 .Построение минимального остовного дерева (алгоритм Краскала).
   • Раздел 3. Динамическое программирование.
   • Тема 1. Метод динамического программирования.
   • 1.2 Идеи метода динамического программирования
   • 1.3 Выбор состава оборудования для технологической линии.
   • Исходные данные для примера
   • Тема 2. Задача инвестирования.
   • Тема 3. Замена оборудования.
   • Тема 4. Задача о загрузке.
   • 4.2 Рекуррентные соотношения для процедур прямой и обратной прогонки.
   • 4.3 Решение задачи о загрузке.
   • Раздел 4. Системы массового обслуживания (смо). (8 часов).
   • Тема 1. Основные понятия теории массового обслуживания.
   • Тема 2. Простейшие смо и нахождение их параметров.
   • Перечень характеристик систем массового обслуживания можно представить следующим образом:
   • 2. Одноканальная смо с неограниченной очередью
   • 3. Одноканальная смо с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания
   • 4. Одноканальная смо с произвольным потоком заявок и произвольным распределением времени обслуживания
   • Раздел 5. Имитационное моделирование.
   • Тема 1. Простейшие задачи, решаемые методом имитационного моделирования.
   • Тема 2. Основные понятия теории Марковских процессов.
   • Тема 3. Метод Монте – Карло.
   • Раздел 6. Прогнозирование.
   • Тема 1. Основная идея прогнозирования. Методы прогнозирования
   • Тема 2.Теории экспертных оценок.
   • Раздел 7. Теория игр.
   • Тема 1. Основные понятия теории игр.
   • 1. 1 Понятие об играх и стратегиях
   • Тема 2. Простейшие методы решения задач теории игр.
   • Раздел 8. Элементы теории принятия решений. (2 часа).
   • Основные понятия.
   • Принятие решений в условиях полной неопределенности
   • Принятие решений при проведении эксперимента.
   • 2. Принятие решений в условиях полной неопределенности
   • 2.1 Максиминный критерий Вальда.
   • Критерий равновозможных состояний.
   • 3. Принятие решений при проведении эксперимента.
   • 3.1. Принятие решений в условиях неопределенности.
   • 3.2. Использование смешанной стратегии
   • 3.3. Принятие решений в условиях риска