- •Учебное пособие
- •Оглавление
- •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.Задача о назначениях
- •Венгерский алгоритм
- •Оптимальное исследование рынка
- •Оптимальное использование торговых агентов
На первой итерации получен оптимальный план злп (4.24).
= (1, 4, 2); = (38, 28, 6),
= (38, 6, 0, 28, 0, 0, 0); f() = 242.
Запишем задачу, двойственную к (2.24):
min(50Y1 + 10Y2 +24Y3); Y1 ≥ 4; 2Y1 – 3Y2 + 4Y3 ≥ 1; 3Y1 + Y2 + ≥ 2. |
(4.25) |
Y2 ≥ 3; –Y1 +2Y2 + Y3 ≥ 0; Y3 ≥ 0; Y1 + 4Y2 – 1/2 Y3 ≥ 0. |
(4.26) |
не ограничены в знаке. |
(4.27) |
Ограничения (4.27) являются избыточными, следовательно, их можно отбросить.
Находим решение ЗЛП (2.25) по формуле
== (4, 3, 1) = (4, 3, 1/2)
или (4.22):
= (0 + 4, 0 + 3, + 0) = (4, 3, );
= 504 + 103 + 24 = 242.
4.3. Решение злп с помощью Ms Excel
Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис»:
Рис.4.2
Если в версии Excel, установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 4.3).
Рис.4.3
Рассмотрим на примере использование данной надстройки. Решим с ее помощью задачу производственного планирования - выпуск продуктов А, В, С, Д из трёх типов ресурсов, математическая модель которой имеет вид:
max f ()=7,5X1+3X2+6X3+12X4 (целевая функция – суммарная стоимость выпуска)
при
Ограничения
по запасам ресурсов и неотрицательности
переменных
2X1+X2+0,5Х3+4Х4 ≤ 2400
X1+5X2+3Х3 ≤ 1200
3X1+6X3+Х4 ≤ 2000
X1,2,3,4 ≥0
Составим шаблон в редакторе Excel,как показано на рис. 4.4
Рис. 4.4 Шаблон оформления задачи
Теперь занесем в данную задачу числовую информацию (рис. 4.5)
Рис. 4.5 Исходные данные задачи
В выделенные пустые ячейки (значения целевой функции и левых частей неравенств) необходимо занести формулы, отображающие связи и отношения между числами на рабочем столе.
Ячейки С4 – F4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., Поиск решения будет изменять их таким образом, чтобы целевая функция приняла оптимальное значение. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения)
Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение 7,5X1+3X2+6X3+12X4, можно рассматривать как произведение вектора (7,5, 3, 6, 12) на вектор (Х1,Х2,X3,X4).
В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку H5 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5:F5) и ячеек, в которые в результате решения будут помещены значения Х1, Х2, X3, X4 (ячейки С4:F4) (рис. 4.6).
Рис. 4.6 Вызов функции СУММПРОИЗВ
Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение 2X1+X2+0,5Х3+4Х4 (для первого ограничения 2X1+X2+0,5Х3+4Х4≤2400) будем рассматривать как произведение вектора коэффициентов (2, 1, 0,5, 4) и вектора переменных (Х1,Х2,X3,X4).
В ячейке, отведенной для формулы левой части первого ограничения (G9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9:F9 и адрес значений переменных C4:F4 (рис.4.7).
Рис.4.7
В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введенными формулами показан на рис. 4.8.
Рис.4.8
К моменту вызова сервиса «Поиск решения» на рабочем столе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.
В меню Сервис выбираем Поиск решения. В появившемся окне задаем следующую информацию:
а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции H5
б) «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;
в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4:F4;
г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (рис.4.9).
Рис.4.9
д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G9, выбирается требуемый знак неравенства (в нашем случае, <=), в поле «Ограничение» заносится ссылка на правую часть ограничения I9 (рис. 4.10).
Рис.4.10
е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».
Таким образом, окно «Поиск решения с занесенной информацией выглядит следующим образом (рис. 4.11)
Рис.4.11
Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (рис. 4.12)
Рис.4.12. Установка параметров.
Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения (рис.4.13)
Рис.4.13. Окно результата решения.
Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи. (рис. 4.14)
Рис.4.14. Результат применения «Поиска решения»
Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (рис. 4.15), это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок», максимизации/минимизации и т.д.).
Рис.4.15. Сообщение об ошибке.
В окне «Поиск решения» имеется кнопка «Параметры»:
Установим флажок «Показывать результаты итераций», после нажимаем «ОК»:
Затем нажать кнопку «Выполнить»:
Ms Excel выдаст следующее окно:
На рабочем листе будут показаны результаты первой итерации:
После чего нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты второй итерации:
Затем снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации:
При следующим нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета:
В данном разделе рассмотрен общий формат решения задач оптимизации в Excel. В зависимости от экономических моделей, выполняют его соответствующие модификации.
Отчеты выглядят следующим образом:
1. Отчет по результатам
2. Отчет по устойчивости
3. Отчет по пределам
Теперь решим задачу, у которой математическая модель имеет тот же вид, но ограничения имеют разные знаки. а) Допустим, математическая модель имеет следующие ограничения:
max f ( )=7,5X1+3X2+6X3+12X4 (целевая функция)
при
2X1+X2+0,5Х3+4Х4 ≥ 2400 ограничения
X1+5X2+3Х3 ≤ 1200
3X1+6X3+Х4 ≤ 2000
X1,2,3,4 ≥0
В итоге имеем следующие результаты по отчетам: 1. Отчет по результатам
2. Отчет по устойчивости
б) Теперь предположим, что математическая модель имеет другие ограничения:
max f ( )=7,5X1+3X2+6X3+12X4 (целевая функция)
при
2X1+X2+0,5Х3+4Х4 ≤ 2400 ограничения
X1+5X2+3Х3 ≥ 1200
3X1+6X3+Х4 = 2000
X1, 2, 3, 4 ≥0
В итоге имеем следующие результаты по отчетам: 1. Отчет по результатам
2. Отчет по устойчивости