Методические указания и задания Математическое программирование

Методические указания и задания

К изучению раздела курса прикладной математики

«Математическое программирование»

(для студентов экономических специальностей заочной и дневной форм обучения)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ДОНБАССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ СТРОИТЕЛЬСТВА И АРХИТЕКТУРЫ

Методические указания и задания

К изучению раздела курса прикладной математики

«Математическое программирование»

(для студентов экономических специальностей заочной и дневной форм обучения)

Утверджено на заседании Утверждено на заседании кафедры

учебно – методического совета высшей и прикладной математики

И информатики

Протокол № ___ от __________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. Вид сырья Запас сырья, Т Затраты сырья на единицу продукции …

Математически эта задача формулируется следующим образом.

Переменные.

Так как нужно определить объем производства каждого вида продукции, переменными в модели являются:

– объем производства продукции ;

– объем производства продукции .

Целевая функция. Конечную цель задачи - получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных и .

Суммарная прибыль .

Ограничения.

При решении рассматриваемой задачи должны быть учтены ограничения на расход сырья.

Добавим ограничения на неотрицательность значений объемов производства продукции

.

Итак, математическая модель формулируется следующим образом.

Определить объемы производства продукции вида и в тоннах, при которых достигается максимум целевой функции при ограничениях:

Таким образом, задача ЛП заключается в отыскании вектора , максимизирующего линейную целевую функцию

(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].

 

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ.

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях (2) знаков неравенств на знаки точных равенств. 2. Находят полуплоскости, определяемые каждым из ограничений задачи. 3. Находят многоугольник решений.

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННЫХ ЗАДАЧ.

1). обе задачи имеют планы; 2). планы имеет только одна задача; 3). для каждой задачи двойственной пары множество планов пусто.

Симплексный метод.

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

Транспортная задача.

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

Первая задача получила название транспортной задачи по критерию стоимости, вторая – по критерию времени.

Транспортная задача формулируется следующим образом [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

Суммарные транспортные издержки согласно данному плану:

Проверка плана на оптимальность:

, , , , .

Пусть , тогда , , , , .

Для свободных переменных найдем косвенные стоимости:

, , , , ,

.

Для свободных переменных находим коэффициенты:

, ,

, ,

, .

Так как все , то полученный план является оптимальным.

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

Пусть имеется два игрока, один из которых может выбрать тую стратегию из m своих возможных, а второй - тую стратегию из n своих возможных. В… . Строки матрицы соответствуют стратегиям первого игрока, а столбцы – стратегиям второго. Эти стратегии называются…

РИС 3.

В точках и восстановим перпендикуляры и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (он совпадает с осью 0z) отложим выигрыш игрока А при стратегии А₁, а на втором – при стратегии А₂. Если игрок А применяет стратегию А₁, то его выигрыш равен 2 при условии, что игрок В применяет стратегию В₁, и равен 5 при условии, что игрок В применяет стратегию В₂. Числам 2 и 5 на оси 0z соответствуют точки В₁ и В₂. Если же игрок А применяет стратегию А₂, то его выигрыш равен 6 при условии, что игрок В применяет стратегию В₁, и равен 4 при условии, что игрок В применяет стратегию В₂. Эти два числа определяют точки и на перпендикуляре, восстановленном в точке А₂. Соединяя между собой точки В₁, В₂, и , получим две прямые, расстояние до которых от оси 0u определяет средний выигрыш при любом сочетании соответствующих стратегий. Таким образом, ординаты точек, принадлежащих ломаной определяют минимальный выигрыш игрока А при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке M; следовательно, этой точке соответствует оптимальная стратегия , а ее ордината равна цене игры. Координаты точки М находим как координаты точек пересечения прямых и . Соответствующие три уравнения имеют вид:

Решая полученную систему, найдем , , .

Аналогично находится оптимальная стратегия для игрока В. Для ее определения мы имеем систему (1). Следовательно, решением игры являются смешанные стратегии , , а цена игры .

Обобщая изложенные выше результаты решения игры , можно указать основные этапы решения игры и .

1. Строят прямые, соответствующие стратегиям второго (первого) игрока.

2. Определяют нижнюю (верхнюю) границу выигрыша.

3. Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой.

4. Находят цену игры и оптимальные стратегии

Пример 5. Найти решение игры, заданной матрицей

.

Решение.

 

На рисунке прямые , и соответствуют стратегиям, а ломаная - нижней границе выигрыша игрока В. Игра имеет решение , , .

Пример 6.Найти решение игры, заданной матрицей

.

Решение.

Матрица имеет размерность . Строим прямые, соответствующие стратегиям игрока А:

Ломаная соответствует верхней границе выигрыша игрока А, а отрезок NK – цене игры. Решение таково: , , .

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

Чтобы найти решение данной игры, определяемой матрицей А, нужно составить следующую пару двойственных задач и найти их решение [6].

Прямая задача: найти максимальное значение функции при условиях , , .

Двойственная задача: найти минимальное значение функции при условиях , , ,..

Используя решение пары двойственных задач, получаем формулы для определения оптимальных стратегий и цены игры:

, ,

, , .

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

1. Составляют пару двойственных задач линейного программирования, эквивалентных данной матричной игре.
2. Определяют оптимальные планы пары двойственных задач.
3. используя соотношения между планами пары двойственных задач и оптимальными стратегиями и ценой игры, находят решение игры.

Пример 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 г.