- •Учебное пособие
- •Оглавление
- •2. Элементы линейной алгебры 21
- •3. Линейное программирование 48
- •4. Теория двойственности в линейном программировании 100
- •5. Целочисленные модели исследования операций 140
- •6. Экономические задачи, сводящиеся к транспортной модели 163
- •Введение в исследование операций
- •1.1 Основные определения
- •Этапы исследования операций
- •Домашнее задание №1
- •Время, требуемое на обработку каждой модели в каждом цехе
- •2. Элементы линейной алгебры
- •2.1. Алгебра матриц
- •2.1.1. Виды матриц
- •2.1.2. Действия над матрицами
- •Домашнее задание №2
- •2.2. Вычисление определителей
- •Домашнее задание №3
- •2.3. Решение систем алгебраических уравнений
- •2.3.1. Основные понятия и определения
- •2.3.2. Формулы крамера и метод обратной матрицы
- •2.3.3. Метод жордана-гаусса
- •Домашнее задание №5
- •2.4. Векторное пространство
- •2.4.2. Размерность и базис векторного пространства
- •Домашнее задание №6
- •2.5. Решение задач линейной алгебры с помощью ms excel
- •3. Линейное программирование
- •3.1. Постановки задачи линейного программирования
- •3.1.1. Общая постановка задачи линейного программирования
- •3.1.2. Основная задача линейного программирования
- •3.1.3. Каноническая задача линейного программирования
- •3.2. Графический метод решения злп
- •Домашнее задание №7
- •Домашнее задание №8
- •3.3. Анализ решения (модели) на чувствительность
- •Домашнее задание №9
- •3.4. Решение линейных моделей симплекс-методом.
- •Переход от одной к-матрицы злп к другой к-матрице
- •Алгоритм симплекс-метода
- •Домашнее задание №10
- •3.4. Двойственный симплекс-метод (р-метод)
- •Определение р-матрицы злп
- •Условия перехода от одной р-матрицы злп к другой
- •Алгоритм р-метода
- •Решение задач р-методом
- •Домашнее задание №11
- •Домашнее задание №12
- •3.5. Решение злп двухэтапным симплекс-методом
- •Первый этап - решение вспомогательной задачи
- •Второй этап - решение исходной задачи
- •Домашнее задание №13
- •4. Теория двойственности в линейном программировании
- •4.1. Определение и экономический смысл двойственной злп
- •4.2. Основные положения теории двойственности
- •Получение оптимального плана двойственной задачи на основании теоремы 4
- •На первой итерации получен оптимальный план злп (4.24).
- •4.3. Решение злп с помощью Ms Excel
- •4.4. Анализ решения злп на основе отчетов ms excel
- •5. Целочисленные модели исследования операций
- •5.1. Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
- •X1, х2 0, целые.
- •Подробное описание метода
- •5.2. Задача коммивояжера
- •Применение метода ветвей и границ для решения задачи коммивояжера
- •Ветвление
- •Построение редуцированных матриц и и вычисление оценок снизу
- •Формирование списка кандидатов на ветвление
- •6. Экономические задачи, сводящиеся к транспортной модели
- •6.1.Транспортная задача линейного программирования
- •Методы составления первоначальных опорных планов
- •Метод потенциалов решения транспортной задачи
- •Проверка выполнения условия оптимальности для незанятых клеток
- •Выбор клетки, в которую необходимо поместить перевозку
- •Построение цикла и определение величины перераспределения груза
- •Проверка нового плана на оптимальность
- •Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- •6.2.Экономические задачи, сводящиеся к транспортной модели
- •Оптимальное распределение оборудования
- •Формирование оптимального штата фирмы
- •Задача календарного планирования производства
- •Модель без дефицита
- •Модель с дефицитом
- •6.3.Задача о назначениях
- •Венгерский алгоритм
- •Оптимальное исследование рынка
- •Оптимальное использование торговых агентов
Домашнее задание №7
Решить графическим методом задачу из домашнего задания №1.
Домашнее задание №8
Решить графическим методом задачу:
Из трех сортов бензина образуются две смеси. Первая состоит из А1 % бензина первого сорта, В1 % бензина 2-го сорта, С1 % бензина 3-го сорта; вторая – А2 % - 1-го, В2 % - 2-го, С2 % - 3-го сорта. Цена 1-ой смеси - 305 у.е., второй - 200 у.е. за тонну. Сколько смеси первого и второго вида можно изготовить из “а” тонн 1-го сорта, “в” тонн 2-го сорта и “с” тонн 3-го сорта, чтобы получить максимальный доход?
№ задач |
А1 |
В1 |
С1 |
А2 |
В2 |
С2 |
а |
В |
с |
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 |
80 70 70 60 60 60 60 60 70 70 50 60 50 50 40 45 45 50 50 60 45 40 40 50 60 |
10 20 10 20 10 30 - 40 30 - 10 20 10 15 20 30 25 - 15 20 - 30 40 10 10 |
10 10 20 20 30 10 40 - - 30 40 20 40 35 40 25 30 50 35 20 55 30 20 40 30
|
20 20 30 30 30 30 10 20 10 20 10 20 25 30 35 40 45 50 55 10 15 20 25 30 35 |
30 40 40 20 50 30 80 10 60 60 20 40 45 35 30 45 10 15 - 20 25 30 35 40 45
|
50 40 30 50 20 40 10 70 30 20 70 40 30 35 35 5 45 35 45 70 60 50 40 30 20
|
16 28 26 24 39 27 18 24 14 28 14 16 18 22 24 26 28 30 36 38 40 42 44 46 48
|
13 32 18 10 20 15 48 14 45 42 45 40 35 30 25 20 15 55 50 45 40 35 30 25 20
|
21 30 16 16 21 8 14 42 21 20 21 18 27 24 21 27 30 33 21 27 18 15 21 27 30
|