Методические указания и задания
К изучению раздела курса прикладной математики
«Математическое программирование»
(для студентов экономических специальностей заочной и дневной форм обучения)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
ДОНБАССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ СТРОИТЕЛЬСТВА И АРХИТЕКТУРЫ
Методические указания и задания
К изучению раздела курса прикладной математики
«Математическое программирование»
(для студентов экономических специальностей заочной и дневной форм обучения)
Утверджено на заседании Утверждено на заседании кафедры
учебно – методического совета высшей и прикладной математики
И информатики
Протокол № ___ от __________2013 г. протокол № ___ от __________2013 г.
Макеевка 2013
Методические указания и задания к изучению раздела курса прикладной математики
«Математическое программирование» (для студентов экономических специальностей заочной и дневной форм обучения)/ Сост.: О.В. Александрова, Т.В. Жмыхова.. – Макеевка: ДонНАСА, 2013 г., - 25 с.
Содержат задачи по разделу курса прикладной математики «Математическое программирование» с примерами решений. Необходимые теоретические сведения приводятся в разобранных задачах.
Составители: О.В, Александрова, доц.
Т.В. Жмыхова, доц.,
Рецензент: И.Н. Ковалев, к.ф.-м. н., доцент
СОДЕРЖАНИЕ
Стр.
1. Постановка задачи линейного программирования.................................................................. 4
2. Существующие математические программные системы........................................................ 5
3. Решение задачи линейного программирования графическим методом................................ 6
4. Геометрическая интерпретация двойственныхз задач............................................................. 6
5. Симплексный метод..................................................................................................................... 8
6. Транспортная задача................................................................................................................... 11
7. Задачи теории игр и линейное программирование................................................................ 14
8. Сведение задач теории игр к задачам линейного программирования................................. 19
9. Задания........................................................................................................................................ 22
10. Литература................................................................................................................................ 25
Математически эта задача формулируется следующим образом.
Переменные.
Так как нужно определить объем производства каждого вида продукции, переменными в модели являются:
– объем производства продукции ;
– объем производства продукции .
Целевая функция. Конечную цель задачи - получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных и .
Суммарная прибыль .
Ограничения.
При решении рассматриваемой задачи должны быть учтены ограничения на расход сырья.
Добавим ограничения на неотрицательность значений объемов производства продукции
.
Итак, математическая модель формулируется следующим образом.
Определить объемы производства продукции вида и в тоннах, при которых достигается максимум целевой функции при ограничениях:
Таким образом, задача ЛП заключается в отыскании вектора , максимизирующего линейную целевую функцию
(1)
при следующих линейных ограничениях
(2)
(3)
Запись задачи ЛП в виде (1)-(3) называется нормальной формой задачи.
Эту же задачу ЛП можно представить в векторно-матричной записи:
, , .
Здесь С - вектор коэффициентов целевой функции, А - матрица коэффициентов.
Область называется областью допустимых значений (ОДЗ) задач линейного программирования.
Соотношения (2), (3) называются системами ограничений задачи ЛП.
Так как
,
то можно ограничиться изучением задачи одного типа.
Определение 1. Решением задачи ЛП называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.
Другая форма представления задачи ЛП – каноническая. Она имеет вид:
, , .
Наряду с задачей ЛП в нормальной форме (1)-(3) рассмотрим задачу:
, (4)
, (5)
Где - переменные двойственной задачи.
Задача (4), (5) называется двойственной по отношению к задаче (1)-(3).
СУЩЕСТВУЮЩИЕ МАТЕМАТИЧЕСКИЕ ПРОГРАММНЫЕ СИСТЕМЫ.
Решение задач линейного программирования – это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ. Табличный симплекс-метод хорошо приспособлен для программирования и машинного счета. Существуют программные реализации симплекс-метода. В настоящее время появились интегрированные математические программные системы для научно-технических расчетов: Eureka, PC MatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.
Широкую известность и заслуженную популярность приобрели математические системы класса MathCAD, разработанные фирмой MathSoft (США). Это единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков [4].
Транспортная задача.
Транспортная задача является важной задачей линейного программирования. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость перевозок была бы минимальной. В других случаях это означает выигрыш во времени.
Первая задача получила название транспортной задачи по критерию стоимости, вторая – по критерию времени.
Транспортная задача формулируется следующим образом [7]: предположим, что имеется складов, где хранится некоторый продукт в количествах , и имеется n пунктов реализации этого продукта, потребности которых равны . Требуется найти наиболее экономичный способ перевозки продукта со складов к потребителям, если затраты на перевозку продукта с - того склада на пункт равны . Обозначим - количество продукта, перевозимого - того склада на пункт потребителя, тогда требуется найти минимум стоимости перевозок:
.
Суммы и являются количествами вывезенного продукта с - того склада и потребленного продукта потребителем. Так как весь продукт должен быть вывезен и все потребители удовлетворены, то накладывается система ограничений:
, ,
, , .
План перевозок записывается в виде матрицы
.
План, минимизирующий суммарные транспортные издержки, называется оптимальным или решением транспортной задачи.
Совокупность величин записывается в виде матрицы, которая называется матрицей транспортных издержек:
.
Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса:
,
т.е. чтобы суммарный объем производства был равен суммарному объему потребителя.
Замечание.Количество неизвестных должно быть равно .
Решение транспортной задачи начинается с первоначального базисного распределения поставок. Базисное распределение поставок производится методом северо-западного угла или методом минимального элемента. Рассмотрим на следующем примере эти методы.
Пример 3[7]. Пусть дано:
Поставщики | Мощность поставщиков | Потребители и их спрос | |||
Составим базисный план распределения поставок методом северо-западного угла. Для этого в крайнюю левую ячейку (северо – западный угол) таблицы дадим максимально
возможное значение – 20. После этого спрос первого потребителя будет полностью удовлетворен. Остальные клетки первого столбца заполняем нулями. Следующий северо – западный угол таблицы – клетка . Ей придаем максимально возможное значение 40, так как мощность первого поставщика равна 60, а 20 он уже отдал. Остальные клетки первой строки заполняем нулями. Следующий северо – западный угол – это клетка . В нее мы можем дать 70, так как 110-40=70. Остальные клетки второго столбца закрываем нулями. Действуя далее аналогично, в итоге получим таблицу:
Суммарные транспортные издержки согласно данному плану:
Существенным недостатком метода северо – западного угла является то, что план построен без учета значений коэффициентов затрат задачи.
Более эффективное базисное решение может быть получено методом минимального элемента. Сущность этого метода состоит в выборе клетки с минимальным тарифом. Выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок, а именно, на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то можно выбрать любую из них), и рассмотреть пункты назначения и отправления, соответствующие выбранной клетке [Акулич].
В данном случае таких клеток две: и . Максимально возможные поставки . Так как они совпадают, то максимально возможная поставка дается в любую из них – например, в клетку . Далее алгоритм тот же. В итоге получим следующий опорный план:
1\20 | 2\40 | 5\0 | 3\0 | |
1\0 | 6\0 | 5\10 | 2\110 | |
6\0 | 3\70 | 7\30 | 4\0 |
Суммарные транспортные издержки согласно данному плану:
Что значительно меньше, чем в методе северо – западного угла. Полученный план проверим на оптимальность методом потенциалов [8].
Если , то - свободная переменная. Каждому пункту отправления ставится в соответствие потенциал . Потенциалы находятся из системы для базисных переменных. В нашем случае:
, , , .
Пусть , тогда , , , , , , .
Для свободных переменных найдем косвенные стоимости:
, , , , , , .
Для свободных переменных находим коэффициенты:
.
Итак, , ,
, ,
, .
Если , то эта клетка должна быть закрыта. В нашем случае таковой является клетка (1,3). Закроем ее клетками (2,3) и (2,4). Из первой строки 10 переведем из клетки (1,1) на (2,1) а 30 с (1,2) на (3,2). Получим:
1\10 | 2\10 | 5\40 | 3\0 | |
1\10 | 6\0 | 5\0 | 2\110 | |
6\0 | 3\100 | 7\0 | 4\0 |
Суммарные транспортные издержки согласно данному плану:
Проверка плана на оптимальность:
, , , , .
Пусть , тогда , , , , .
Для свободных переменных найдем косвенные стоимости:
, , , , ,
.
Для свободных переменных находим коэффициенты:
, ,
, ,
, .
Так как все , то полученный план является оптимальным.
РИС 3.
В точках и восстановим перпендикуляры и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (он совпадает с осью 0z) отложим выигрыш игрока А при стратегии А1, а на втором – при стратегии А2. Если игрок А применяет стратегию А1, то его выигрыш равен 2 при условии, что игрок В применяет стратегию В1, и равен 5 при условии, что игрок В применяет стратегию В2. Числам 2 и 5 на оси 0z соответствуют точки В1 и В2. Если же игрок А применяет стратегию А2, то его выигрыш равен 6 при условии, что игрок В применяет стратегию В1, и равен 4 при условии, что игрок В применяет стратегию В2. Эти два числа определяют точки и на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки В1, В2, и , получим две прямые, расстояние до которых от оси 0u определяет средний выигрыш при любом сочетании соответствующих стратегий. Таким образом, ординаты точек, принадлежащих ломаной определяют минимальный выигрыш игрока А при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке M; следовательно, этой точке соответствует оптимальная стратегия , а ее ордината равна цене игры. Координаты точки М находим как координаты точек пересечения прямых и . Соответствующие три уравнения имеют вид:
Решая полученную систему, найдем , , .
Аналогично находится оптимальная стратегия для игрока В. Для ее определения мы имеем систему (1). Следовательно, решением игры являются смешанные стратегии , , а цена игры .
Обобщая изложенные выше результаты решения игры , можно указать основные этапы решения игры и .
1. Строят прямые, соответствующие стратегиям второго (первого) игрока.
2. Определяют нижнюю (верхнюю) границу выигрыша.
3. Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой.
4. Находят цену игры и оптимальные стратегии
Пример 5. Найти решение игры, заданной матрицей
.
Решение.
На рисунке прямые , и соответствуют стратегиям, а ломаная - нижней границе выигрыша игрока В. Игра имеет решение , , .
Пример 6.Найти решение игры, заданной матрицей
.
Решение.
Матрица имеет размерность . Строим прямые, соответствующие стратегиям игрока А:
Ломаная соответствует верхней границе выигрыша игрока А, а отрезок NK – цене игры. Решение таково: , , .
Сведение задач теории игр к задачам линейного программирования.
Чтобы найти решение данной игры, определяемой матрицей А, нужно составить следующую пару двойственных задач и найти их решение [6].
Прямая задача: найти максимальное значение функции при условиях , , .
Двойственная задача: найти минимальное значение функции при условиях , , ,..
Используя решение пары двойственных задач, получаем формулы для определения оптимальных стратегий и цены игры:
, ,
, , .
Итак, процесс нахождения решения игры с использованием методов линейного программирования включает в себя следующие этапы:
Пример 7.Найти решение игры, заданной матрицей:
.
Решение. Составим двойственную пару задач линейного программирования. Прямая задача: найти максимум функции при ограничениях
.
Двойственная задача: найти минимум функции при ограничениях
.
Находим оптимальные планы прямой и двойственной задач:
базис | Сб | Р0 | |||||||
Р1 | Р2 | Р3 | Р4 | Р5 | Р6 | ||||
Р4 | |||||||||
Р5 | |||||||||
Р6 | |||||||||
-1 | -1 | -1 | |||||||
Р4 | |||||||||
Р3 | |||||||||
Р6 | |||||||||
-1 | |||||||||
Р2 | |||||||||
Р3 | |||||||||
Р6 | |||||||||
Из таблицы видно, что исходная задача имеет оптимальный план , а двойственная задача- оптимальный план . Следовательно, цена игры , а оптимальные стратегии игроков , .
Задания.
Задача 1. Решить задачи симплекс-методом, дать решению геометрическую интерпретацию. Во всех заданиях иметь в виду, что переменные неотрицательны.
1. 2.
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13. 14.
15.
Задача 2. На трех складах А, В, С находится горючее, соответственно 50, 90, 110 тонн, которое надо доставить в три пункта: в пункт 1 – 70 т, в пункт 2 – 100 т, в пункт 3 – Х т. Стоимость доставки одной тонны горючего со склада А в указанные пункты соответственно равны , , грн., со склада В - , , грн., со склада С - , , грн.
Используя условия баланса транспортной задачи, найти потребности в горючем пункта 3, определить оптимальный план перевозки горючего в три пункта, минимизирующий стоимость перевозок.
1. . 2. . 3. . 4.
5. . 6. . 7. . 8. .
9. . 10. . 11 . . 12. .
13. . 14. . 15. .
Задача 3. Проанализировать игру, используя принцип минимакса. Найти решение в смешанных стратегиях методами линейного программирования.
1. . 2. . 3. . 4. . 5. .
6. . 7. . 8. . 9. .
10. . 11. . 12. . 13. .
14. . 15. .
Задача 4.Найти решение игр, определяемых следующими матрицами:
1. . 2. . 3 .
4. . 5. . 6.. 7. . 8. .
9. . 10. . 11 . 12. .
13. . 14. . 15. .
ЛИТЕРАТУРА
1. Системный анализ в экономике и организации производства.– Ленинград: Политехника, 1991.
2. Зайченко Ю.П. Исследование операций. Сборник задач – Киев: Вища школа, 1988.
3. Зайченко Ю.П., Шумилова С.А. Исследование операций. Сборник задач. – Киев: Вища школа, 1990.
4. Дьяконов В.П. Справочник по MathCAD PLUS 7.0 PRO –М: СК Пресс, 1998.
5. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец.вузов.- М.: Высш. шк., 1986. – 319 с., ил.
6. Пенина Г.Г. Математическое программирование. – Донецк, ДГКИ, 1998, 31 с.
7. Решетняк С.А., Савенко С.М. Индивидуальные задания и методические указания к изучению курсов «Теория вероятностей и математическая статистика» и «Исследование операций» (для студентов экономических специальностей заочной и ускоренной форм обучения). – Макеевка, ДонНАСА, 2001, 48 с.
8. Вентцель Е.С. Исследование операций. – М.: Советское радио, 1972.г., 552 с.
9. Кремер Н.Ш. Исследование операций в экономике. – М.: Банки и биржи, 1999 г.