Математическое моделирование экономических систем

Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«Ивановский государственный политехнический университет»
Институт управления и организации производства
А.Г. Печникова,
Н.А. Грузинцева,
В.И. Роньжин
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
ЭКОНОМИЧЕСКИХ СИСТЕМ
Рекомендовано научно-методическим советом ИВГПУ в качестве
учебного пособия для студентов экономического профиля
Иваново 2015
УДК 657 (07)
ББК 65.052
Печникова, А.Г. Математическое моделирование экономических систем:
учебное пособие / А.Г. Печникова, Н.А. Грузинцева, В.И. Роньжин. – Иваново:
ИВГПУ, 2015. − 96 с.
Учебное пособие написано на базе материала лекций, которые читаются
студентам дневной и заочной форм обучения. В учебном пособии содержатся
задания для самостоятельной работы студентов по важнейшим вопросам математического моделирования экономических систем, призванные способствовать более глубокому пониманию и усвоению этой дисциплины.
Учебное пособие предназначено для студентов, обучающихся по направлению подготовки 080100 Экономика, аспирантов и преподавателей экономических высших учебных заведений.
Рецензенты: профессор кафедры менеджмента ФГБОУ ВО «Ивановский государственный университет», д-р экон. наук О.Ю. Гурьева
заведующий кафедрой бухгалтерского учета, анализа и аудита
Ивановского филиала ФГБОУ ВО «Российский экономический
университет им. Г.В. Плеханова» канд. экон. наук, доцент
Л.И. Шарова
Научный редактор д-р экон. наук, проф. А.Б. Петрухин
ISBN 978-5-88954-417-3
© ФГБОУ ВО «ИВГПУ», 2015
2
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ………………………………………………………………………
Глава 1. Линейное программирование………………………………………..
4
6
1.1. Общая постановка задачи линейного программирования …………
1.2. Геометрический метод решения задач линейного программирования..
1.3. Симплексный метод решения задач линейного программирования..
1.4. Метод искусственного базиса (М-метод) …………………………….
Вопросы для самоконтроля и задания……………………………………
Глава 2. Двойственная задача линейного программирования……………
2.1. Взаимно-двойственные задачи линейного программирования
и их свойства…………………….............................................................
2.2. Теоремы двойственности……………………………………………..
Вопросы для самоконтроля и задания…………………………………….
Глава 3. Транспортная задача……………………………………………….
3.1. Экономико-математическая модель транспортной задачи. Основные
методы решения транспортной задачи ………………………………
3.2. Модели транспортной задачи. Незамкнутая транспортная задача……
3.3. Модели транспортной задачи. Транспортная задача с ограничением
на объем перевозок………………………………………………………
Вопросы для самоконтроля и задания…………………………………….
Глава 4. Теория игр……………………………………………………………..
4.1. Понятие об игровых моделях…………………………………………..
4.2. Платежная матрица. Нижняя и верхняя цена игры…………………..
4.3. Сокращение порядка платёжных матриц (доминирование стратегий)
4.4. Смешанные стратегии. Аналитический метод решения игры типа 2 x 2.
4.5. Геометрическая интерпретация игры типа 2 x 2…………………….
4.6. Приведение матричной игры к задаче линейного программирования
Вопросы для самоконтроля и задания……………………………………..
СПИСОК ЛИТЕРАТУРЫ ……………………………………………………...
6
16
19
24
31
38
3
38
41
44
48
48
59
62
66
73
73
75
79
81
83
86
91
94
ВВЕДЕНИЕ
Математическое моделирование широко используется в различных областях экономики, при принятии управленческих решений, в финансовой сфере, в маркетинговых исследованиях в зависимости от разработанности математического аппарата и возможности практической реализации.
Общая задача дисциплины «Математическое моделирование экономических систем» – дать основополагающее представление об особенностях экономико-математического моделирования распределительных процессов на предприятиях, моделях сетевого планирования, моделях оптимальной специализации производства, моделях прогнозирования ресурсного обеспечения, учитывающего специфику отрасли, и некоторых широко используемых процедурах
поиска решений в экономических системах.
Цель дисциплины – развить способности студентов к овладению методологией построения и применения математических моделей экономических процессов и объектов, принятию обоснованных, объективных хозяйственных решений в ситуациях исключительной сложности с помощью моделей и количественных методов; углубить теоретические знания о проблемах современной
экономики, которые исследуются средствами математического моделирования.
Основное назначение настоящей дисциплины – ознакомиться с возможностями
математического моделирования, приобрести навыки приложения математических методов к практическим задачам функционирования хозяйственной организации [1, 2].
Учебное пособие содержит комплекс практических заданий, основной
целью которых является развитие и закрепление навыков студентов по важному направлению, находящемуся на стыке экономики и прикладной математики, –
построению и применению математических моделей для анализа разнообразных экономических систем и процессов. Комплекс заданий вкупе с преамбулами к ним призван дать студенту необходимый минимум базовых теоретических
4
знаний по некоторым типовым группам математических моделей и будет способствовать формированию практических навыков построения и исследования
таких моделей с использованием данных реальной экономической и социальной статистики, что является необходимым требованием для качественной подготовки экономиста. В пособие включены задания, для выполнения которых
необходимы основательные знания по математике и статистике, полученные
студентом на предыдущих курсах. Выполнение представленных в настоящем
пособии практических заданий (ПЗ) позволит студенту освоить этот важный
для экономиста предмет.
В процессе освоения учебного материала настоящей дисциплины студент
должен уметь строить и исследовать основные модели макро- и микроэкономических процессов, применяя адекватные методические подходы к исследованию этих моделей, понимать алгоритмы оценки параметров моделей с помощью методов эконометрического анализа, уметь обосновывать и объяснять полученные решения.
По способу построения пособие состоит из обзорных примеров и практических заданий, которые следует выполнить и сдать преподавателю.
5
Глава 1. Линейное программирование
1.1. Общая постановка задачи линейного программирования
Математическое программирование подразделяется на линейное, целочисленное, нелинейное, динамическое программирование.
Одним из направлений математического программирования является линейное программирование, в котором ярко проявляются специфические трудности нахождения экстремума на границе допустимой области переменных.
Задачи линейного программирования (ЛП) относятся к категории оптимизационных. Они находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных
систем.
Линейное программирование – раздел теории оптимизации, посвященный
изучению и решению экстремальных задач, в которых линейная функция и ограничения, задающие допустимое множество, являются линейными.
Задача линейного программирования формулируется так:
определить максимум (минимум) линейной формы
F(x1,…,xn )=c1x1+…+cnxn
max(min)
(1.1)
при условии, что точка (х1, х2,..., хn) принадлежит некоторому множеству D, которое определяется системой линейных неравенств
 a11 x1  a12 x 2  ...  a12 x n  b1 ;
 a x  a x  ...  a x  b ;
 21 1
22 2
2n n
2

..........
..

 a m 1 x1  a m 2 x 2  ...  a mn x n  bm .
(1.2)
Любое множество значений (х1*, х2*,..., хn*), которое удовлетворяет системе неравенств (1.2) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство
c1х1o+ c2 х2o+..+ cn хno ≥ c1х1+ c2 х2+..+ cn хn
6
для всего множества значений x1, х2,..., хn, то значение х1o..хno является оптимальным решением задачи линейного программирования.
Каноническая задача линейного программирования заключается в минимизации (максимизации) линейной целевой функции
F(x) = c1x1+c2x2+... + cnxn
(1.3)
при ограничениях
a11х1 +а12х2 +...+а1пхn=b1
а21х1 +а22х2 +...+а2пхn=b1…
…
аm1х1 +аm2х2 +...+аmпхn=b1
(1.4)
xt,x2,...,xn>0,
где с1,с2,...,сп - коэффициенты целевой функции;
aij, i =1, 2,...,n,j = 1, 2,...,m -коэффициенты системы ограничений;
b1,b2,...,bn - свободные члены, которые считаются неотрицательными.
Вектор X = (xi, х2,..., xj), удовлетворяющий ограничениям задачи ЛП, называется допустимым решением или планом. Допустимый план X*
=(xl,x'2,...,x'n), при котором целевая функция задачи ЛП принимает максимальное (минимальное) значение, называется оптимальным планом [4,10].
Таким образом, каноническая задача линейного программирования состоит в нахождении среди всех решений выписанной выше системы линейных
уравнений такого ее неотрицательного решения, на котором достигает своего
минимального (максимального) значения линейная целевая функция.
Для того чтобы построить экономико-математическую модель задачи линейного программирования, необходимо определить:
1) искомые величины задачи;
2) цель решения, т.е. параметр задачи, который будет критерием эффективности (оптимальности) решения, и направление его изменения (увеличение
или уменьшение) для достижения наилучших результатов;
7
3) какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены. Эти условия устанавливают, как должны соотноситься
друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе.
К математическим задачам линейного программирования относятся:
- задача об оптимальном использовании ресурсов при производственном
планировании;
- задача о смесях (планирование состава продукции);
- задача об использовании мощностей (задача о загрузке оборудования);
- задача о раскрое материала;
- транспортные задачи (анализ размещения предприятия, перемещение
грузов).
Общий смысл задачи об оптимальном использовании ресурсов при производственном планировании сводится к следующему.
Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и
т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц.
Известны также технологические коэффициенты aij, которые показывают,
сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида.
Прибыль, получаемая предприятием при реализации изделия j-го вида,
равна cj.
В планируемом периоде значения величин aij, bi и cj остаются постоянными.
Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.
Пример 1.1. Для изготовления двух видов продукции Р1 и Р2 используют
три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в табл. 1.1.
8
Таблица 1.1
Исходные данные задачи об использовании производственных ресурсов
Количество единиц сырья, идущих на
Вид сырья
Запас сырья
изготовление единицы продукции
Р1
Р2
S1
40
4
7
S2
60
10
7
S3
50
7
8
70
60
Прибыль от единицы продукции, руб.
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Решение. По данному условию сформулируем задачу линейного программирования.
Обозначим: x1 - количество единиц продукции Р1, x2 - количество единиц
продукции Р2.
Тогда, учитывая количество единиц сырья, расходуемое на изготовление
продукции, а также запасы сырья, получим систему ограничений:
4х1 + 7х2 ≤ 40,
10х1 + 7х2 ≤ 60,
7х1 + 8х2 ≤ 50.
Система ограничений показывает, что количество сырья, расходуемое на
изготовление продукции, не может превысить имеющихся запасов. Если продукция Р1 не выпускается, то х1=0; в противном случае x1 >0. То же самое получаем и для продукции Р2. Таким образом, на неизвестные х1 и х2 должно быть
наложено ограничение неотрицательности: х1 ≥ 0, х2 ≥ 0.
9
Конечную цель решаемой задачи – получение максимальной прибыли
при реализации продукции – выразим как функцию двух переменных х1 и х2.
Реализация х1 единиц продукции Р1 и х2 единиц продукции Р2 дает соответственно 70х1 и 60х2 руб. прибыли, суммарная прибыль Z(х) = 50х1 + 40х2 (руб.)
Формулировка задачи линейного программирования:
Требуется найти такие х1 и х2, при которых функция Z(х) достигает максимум, т.е. найти максимальное значение линейной функции
Z(х) = 70х1 + 60х2 → max
при ограничениях
4х1 + 7х2 ≤ 40,
10х1 + 7х2 ≤ 60,
7х1 + 8х2 ≤ 50,
х1 ≥ 0, х2 ≥ 0.
К группе задач о смесях относят задачи по отысканию наиболее дешевого
набора из определенных исходных материалов, обеспечивающих получение
смеси с заданными свойствами. Иными словами, получаемые смеси должны
иметь в своем составе m различных компонентов в определенных количествах,
а сами компоненты являются составными частями n исходных материалов.
Пример 1.2. На птицеферме употребляются два вида кормов – I и II. В
единице массы корма I содержатся единица вещества A, единица вещества В и
единица вещества С. В единице массы корма II содержатся четыре единицы
вещества А, две единицы вещества В и не содержится вещество C. В дневной
рацион каждой птицы надо включить не менее единицы питательного вещества
А, не менее четырех единиц питательного вещества В и не менее единицы питательного вещества С. Цена единицы массы корма I составляет 4 рубля, корма
II – 3 рубля.
Составьте ежедневный рацион кормления птицы так, чтобы обеспечить
наиболее дешевый рацион.
10
Решение. Представим условие задачи в табл. 1.2.
Таблица 1.2
Исходные данные задачи о смесях
Питательные ве-
Требуемое коли-
Содержание веществ в единице массы
щества
чество в смеси, ед.
корма, ед.
корм I
корм II
А
1
1
4
В
4
1
2
С
1
1
-
4
3
Цена единицы массы корма, руб.
Сформулируем задачу линейного программирования.
Обозначим: x1 - количество корма I в дневном рационе птицы, x2 - количество корма II в дневном рационе птицы.
Принимая во внимание значения, приведенные в табл. 1.2, и условие, что
дневной рацион удовлетворяет требуемой питательности только в случае, если
количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений
х1 + 4х2 ≥ 1,
х1 + 2х2 ≥ 4,
х1 ≥ 1.
Если корм первого вида не используется в рационе, то х1=0; в противном
случае x1 >0. Аналогично имеем x2 >0, то есть должно выполняться условие неотрицательности переменных: х1 ≥ 0, х2 ≥ 0.
Цель данной задачи – добиться минимальных затрат на дневной рацион,
поэтому общую стоимость рациона можно выразить в виде линейной функции
Z(х) = 4х1 + 3х2 (руб.).
11
Требуется найти такие х1 и х2, при которых функция Z(х) принимает минимальное значение. Таким образом, необходимо найти минимальное значение
линейной функции
Z(х) = 4х1 + 3х2 → min
при ограничениях
х1 + 4х2 ≥ 1,
х1 + 2х2 ≥ 4,
х1
≥ 1,
х1 ≥ 0, х2 ≥ 0.
Задача об использовании мощностей заключается в следующем. Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n1, n2, …, nk единиц продукции Р1, P2, …, Рk. Продукция производится на станках S1S2, …, Sm. Для каждого станка известны производительность аij (т. е. число единиц продукции Рj, которое можно произвести на станке Si) и затраты bij на изготовление продукции Pj на станке Si в единицу времени.
Необходимо составить такой план работы станков (т. е. так распределить
выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными.
Составим экономико-математическую модель задачи.
Обозначим xij — время, в течение которого станок Si будет занят изготовлением продукции Pj (i = 1, 2,…, m; j = 1, 2, …, k).
Так как время работы каждого станка ограничено и не превышает Т, то
справедливы неравенства:
х11 + х12 + … + х1k ≤ Т,
х21 + х22 + … + х2k ≤ Т,
…………………………
xm1 + хm2 + … + хmk ≤ Т.
(1.5)
12
Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:
a11х11 + a21х21 + … + am1хm1 = n1,
a12х12 + a22х22 + … + am2хm2 = n2,
…………………………………..
a1kх1k + a2kх2k + … + amkхmk = nk.
(1.6)
Кроме того,
xij ≥ 0 (i = 1, 2, …, m; j = 1, 2, …, k).
(1.7)
Затраты на производство всей продукции выразятся функцией
F(x) = b11x11 + b12x12 + …+ bmkxmk.
(1.8)
Экономико-математическая модель задачи об использовании мощностей
примет вид: найти такое решение Х = (x11, x12, …, xmk), удовлетворяющее системам (1.5) и (1.6) и условию (1.7), при котором функция (1.8) принимает минимальное значение [5, 14].
Задача оптимального раскроя материалов является одной из самых важных в ресурсосберегающих технологиях для заготовительного производства,
поскольку напрямую ведет к экономии материалов и снижению отходов.
Суть задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый
комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.
На раскрой поступает материал одного образца в количестве a единиц.
Требуется изготовить из него l разных комплектующих изделий в количествах
пропорциональных числам b1, b2, …, bl (условие комплектности). Каждая единица материала может быть раскроена n различными способами, при этом использование i-го способа (i =1, 2, …, n) дает aik единиц k-го изделия (k = 1, 2, …, l).
Требуется составить план раскроя, обеспечивающий максимальное количество
комплектов.
13
Составим экономико-математическую модель задачи. Обозначим через xi
количество единиц материала, раскраиваемых i-м способом, и x – количество
изготавливаемых комплектов изделий.
Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то
(1.9)
Условие комплектности выразится уравнениями
(1.10)
По смыслу задачи переменные
хi ≥ 0 (i = 1, 2, …, n).
(1.11)
Итак, экономико-математическая модель задачи: найти такое решение
Х = (x11, x12, …, xn), удовлетворяющее системе уравнений (1.9) – (1.10) и условию (1.11), при котором функция F = x принимает максимальное значение [14].
Пример 1.3. Требуется разработать оптимальный план раскроя стандартных листов стали, обеспечивая выход планового числа заготовок разного вида
при минимальных суммарных отходах, если известно, что из партии листовой
стали необходимо нарезать четыре вида различных заготовок в количестве bi (i
= 1, 2,…,4) штук. Лист стали стандартных размеров может быть раскроен четырьмя способами. Каждому возможному способу раскроя соответствует карта
раскроя. Из карт раскроя известен выход заготовок в штуках разных видов aij (i
= 1, 2,…4; j = 1,2,…,4), а также площадь отходов cj (j = 1, 2,…,n) при раскрое
одного листа стали по j-му способу раскроя. Какое количество листов стали необходимо раскроить тем или иным способом, чтобы отходы были минимальными?
14
Решение. Представим условие задачи в табл. 1.3.
Таблица 1.3
Исходные данные задачи о раскрое материалов
План-задание
Виды
заготовок
по количеству
Выход заготовок (шт) разных видов
из карт раскроя (aij)
заготовок (b1)
1
2
3
4
1
240
1
4
0
1
2
200
1
0
4
0
3
120
1
0
0
3
4
140
1
1
0
3
1,4
0,1
2,1
0,1
Площадь отходов, м2 (cj)
Составим экономико-математическую модель задачи.
Обозначим через xj количество исходного материала (листов стали), которое необходимо раскроить по одному из способов j. Ограничения в задаче
должны соответствовать плановому выходу заготовок различных видов. Целевая функция сводится к нахождению минимума отходов при раскрое.
Целевая функция будет иметь вид
F(х) =1,4x1+0,1x2+2,1x3+0,1x4→ min.
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:
х1 + 4х2 + х4 ≥ 240,
х1 + 4х3
≥ 200,
х1 + 3х4
≥ 120,
х1 + х2 + 3х4 ≥ 140,
х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0.
Под транспортной задачей понимают целый ряд задач, имеющих определенную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов отправления в пункты назначения при минимальных затратах на перевозку. Модели задач данного класса будут рассмотрены ниже.
15
1.2. Геометрический метод решения задач линейного программирования
Наиболее простыми и распространенными методами решения канонической задачи линейного программирования являются геометрический и симплексный методы.
Если количество переменных в неравенствах, задающих область допустимых планов задач, равно двум, то ее можно изобразить на координатной
плоскости. Каждое неравенство определяет некоторую полуплоскость. Пересечение данных полуплоскостей является областью допустимых планов задач.
Поведение целевой функции в рамках двумерной иллюстрации может быть
охарактеризовано с помощью линии уровня.
Линией уровня функции называется множество точек из области ее определения, в которых функция принимает одно и то же фиксированное значение.
Градиент функции – это вектор, указывающий направление наиболее быстрого
возрастания функции [3, 6].
Таким образом, с геометрической точки зрения задача максимизации сводится к определению такой точки области допустимых планов, через которую
проходят линии уровня, соответствующие наибольшему из возможных значений. Для этого необходимо сначала построить линию уровня для некоторого
произвольного значения функции. Затем осуществить ее параллельное движение (перпендикулярно вектору градиента функции) до тех пор, пока она не достигнет такой точки области допустимых планов (решений), из которой смещение в направлении вектора градиента функции было бы невозможно.
Алгоритм геометрического (графического) метода:
1) построить многоугольник допустимых решений на основании заданной
системы ограничений;
2) найти вершины многоугольника как точки пересечения полуплоскостей ограничений;
16
3) найти вершину, для которой целевая функция приобретает оптимальное решение (максимальное или минимальное), отвечает разыскиваемому решению. Координаты этой вершины являются оптимальными значениями переменных.
Рассмотрим решение задачи линейного программирования графическим
методом.
Пример 1.4. Решить задачу линейного программирования графическим
методом:
Z  x   3 x1  x2  max
4 x1  7 x2  56,
 5 x  4 x  40,
 1
2

 24,
6 x1
 x1  0, x2  0.
Решение. Построим область допустимых решений (множество точек
пересечения полуплоскостей, каждая из которых задана соответствующим
неравенством):
1. Начертим систему координат ( x1 - ось абсцисс, x 2 - ось ординат).
2. Отметим сразу, что область допустимых решений задачи будет
находиться в первом квадранте координатной плоскости, что вытекает из
последних двух неравенств в системе ограничений.
3. Начертим прямую, задаваемую уравнением
4 x1  7 x 2  56 ,
(1.12)
по двум точкам 0; 8  и 14; 0  . Координаты точек вычисляем из уравнения
(1.12), полагая для первой точки x1  0 , а для второй x 2  0 .
4. Так как любая прямая разделяет всю плоскость на две полуплоскости, то
каждое неравенство в системе ограничений задает полуплоскость. Определяем,
какую из двух полуплоскостей задает первое неравенство в системе ограничений.
17
Для этого подставляем в неравенство любую точку плоскости, например точку
0; 0  . Так как эта точка удовлетворяет неравенству, то неравенство задает ту
полуплоскость, которой принадлежит эта точка, а именно нижнюю.
5. Аналогичным способом строим две другие полуплоскости, границами
для которых служат соответственно прямые
5 x1  4 x2  40 ,
(1.13)
6 x1  24 .
(1.14)
Тогда область допустимых решений, определяемая как пересечение всех
трех полуплоскостей, представлена на рис. 1.1.
x2
(1.13)
(1.12)
(1.14)
10
8
A

N
0
4
8
14
x1
Z
Рис.1.1. Решение задачи линейного программирования графическим
методом
6. Начертим вектор возрастания линии уровня целевой функции. Его

координаты соответствуют коэффициентам при переменных x1 , x 2 : N 3; 1 .
7. Перпендикулярно вектору

N
изобразим линию уровня целевой
функции Z.
18
8. На области допустимых значений целевая функция принимает
максимум в точке А, находящейся на пересечении прямых (1.13) и (1.14). Решив
5 x1  4 x2  40,
систему уравнений: 
, находим координаты точки A  4; 5 .
 24
6 x1
9. Таким образом, максимальное значение целевой функции равно
Z max  3  4  1 5  17 .
Ответ. Максимальное значение целевой функции Z max  17 достигается в
точке с координатами A  4; 5 .
1.3. Симплексный метод решения задач линейного программирования
В основе симплекс-метода лежит идея поиска базисного решения с последующим переходом от одного базиса к другому таким образом, чтобы целевая функция при этом все время увеличивалась, если речь идет о задаче максимизации. Для начала работы требуется, чтобы заданная система ограничений
выражалась равенствами, причем в этой системе ограничений должны быть
выделены базисные неизвестные. Решение задачи при помощи симплексметода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б1 с таким расчетом, чтобы значение функции
f(x) уменьшалось, т. е. fБ1≥fБ. Для перехода к новому базису из старого базиса
удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б(k) , для которого fБ(k) есть искомый максимум для линейной функции f, а соответствующее
базисное решение является оптимальным либо выясняется, что задача не имеет
решения [7].
Переход от одного базисного решения к другому удобно осуществлять с
помощью симплексных таблиц (табл. 1.4). Каждая такая таблица представляет
базисное решение. В симплексной таблице введены следующие обозначения:
19
Сбаз – коэффициенты при базисных переменных в целевой функции;
хб – базисные переменные;
b – свободные члены соответствующих ограничений;
с1 … сn – коэффициенты при переменных в целевой функции;
х1 … хn – переменные;
а11 … аmn – коэффициенты при соответствующих переменных из системы
ограничений;
Zk - cn – индексная строка, каждый элемент которой получают расчетным
путем. Zk определяют как сумму попарных произведений элементов первого
столбца (Сбаз) и соответствующих элементов столбца при переменных;
b/а – оценочные отношения, которые рассчитываются для определения
ключевой строки путем отношения элементов столбца свободных членов (В) к
соответствующим элементам ключевого столбца.
Таблица 1.4
Симплексная таблица
Сбаз
хб
b
с1
c2
…
сn
х1
х2
…
хn
сб1
хб1
b1
а11
а12
…
а1n
сб2
хб2
b2
а21
а22
…
а2n
…
…
…
…
…
…
…
сбm
хбm
bm
аm1
аm2
…
аmn
Z(x)
Z1-c1
Z2-c2
…
Zn-cn
Zk - cn
b/а
Полученное в симплексной таблице решение оптимально, если при нахождении максимального значения целевой функции все коэффициенты индексной строки положительны. При отыскании минимума решение оптимально, когда все коэффициенты индексной строки отрицательны. Если же данное условие не выполняется, то необходимо решение улучшить. Для этого нужно в число базисных переменных ввести новую переменную.
20
Новая переменная, которая войдет в базисное решение, определяется следующим образом. В индексной строке отыскивается максимальное по абсолютной величине отрицательное число (при отыскании максимума целевой функции) или наибольшее положительное число (при отыскании минимума целевой
функции). Соответствующий выбранному числу столбец симплексной таблицы
называется ключевым.
Далее следует установить, какую же из прежних базисных переменных
заменит новая базисная переменная. С этой целью определяют ключевую строку. Ключевая строка отыскивается по отношению свободных членов к соответствующим положительным элементам ключевого столбца. Наименьшее отношение определяет ключевую строку.
На пересечении ключевой строки и ключевого столбца расположен генеральный элемент.
Для перехода от одной симплексной таблицы к другой существуют следующие правила:
1. Для нахождения элементов вводимой строки (соответствующей старой
ключевой) необходимо все элементы ключевой строки поделить на генеральный элемент.
2. Элементы ключевого столбца, кроме находящегося в ключевой строке,
переносятся в новую таблицу в виде нулей.
3. Те столбцы старой таблицы, у которых элемент в ключевой строке равен нулю, переносятся в новую таблицу без изменений.
4. Все остальные элементы новой таблицы находятся расчетным путем по
следующей формуле:
ак.столб
(1.15)
где ан – новый элемент,
ас – соответствующий старый элемент,
ак.столб. – элемент ключевого столбца,
ак.стр. – элемент ключевой строки,
аг – генеральный элемент.
21
Составленную новую симплексную таблицу проверяют, вычисляя индексную строку. Далее устанавливают, получено оптимальное решение или нет.
Решение в симплексной таблице находится в столбце свободных членов:
в индексной строке дано значение целевой функции, а все остальные элементы
определяют значения базисных переменных.
Для того чтобы решить задачу симплексным методом, необходимо выполнить следующее:
1. Привести задачу к каноническому виду.
2. Найти начальное опорное решение с "единичным базисом" (если
опорное решение отсутствует, то задача не имеет решения ввиду несовместимости системы ограничений).
3.
Вычислить оценки разложений векторов по базису опорного реше-
ния и заполнить таблицу симплексного метода.
Если выполняется признак единственности оптимального решения, то
решение задачи заканчивается.
Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.
Рассмотрим решение задачи линейного программирования симплексным
методом.
Пример 1.5. Решить задачу линейного программирования симплексным
методом:
Z(x) = 11х1 + 2,5х2 + 2,1х3
max
0,25х1 + 0,05х2 + 0,025х3 ≤ 150,
2х1 + 0,5х2 +
0,4х3 ≤ 1600,
х1, х2, х3 ≥ 0.
Прежде чем составить первую симплексную таблицу, необходимо привести задачу к каноническому виду. Для этого в каждое выражение системы ограничений вводим базисные переменные: х4 – в первое выражение и х5 – во
второе выражение:
Z(x) = 11х1 + 2,5х2 + 2,1х3 + 0х4 + 0х5
max
0,25х1 + 0,05х2 + 0,025х3 + х4 = 150,
2х1 + 0,5х2 + 0,4х3 + х5 = 1600,
х1, х2, х3, х4, х5 ≥ 0.
22
Переносим данные в симплексную таблицу.
Таблица 1.5
Симплексная таблица № 1
Сбаз
хб
b
11
2,5
2,1
0
0
х1
х2
х3
х4
х5
b/x
0
х4
150
0,25
0,05
0,025
1
0
150/0,25=600
0
х5
1600
2
0,5
0,4
0
1
1600/2=800
0
-11
-2,5
-2,1
0
0
Zk - cn
Элементы индексной строки показывают, что оптимальное решение не
найдено, так как имеются отрицательные значения. Необходимо улучшить решения. Для этого определяем ключевой столбец, который будет располагаться
по попеременной х1, так как в индексной строке по этому столбцу находится
максимальное по абсолютной величине отрицательное число. Далее находим
ключевую строку, для чего рассчитываем оценочные отношения (последний
столбец симплексной таблицы) и выбираем наименьшее положительное число.
Наименьшее отношение принадлежит переменной х4. Генеральный элемент равен 0,25.
Применяя правила перехода, перечисленные выше, составляем новую
симплексную таблицу.
Таблица 1.6
Симплексная таблица № 2
Сбаз
хб
b
11
2,5
2,1
0
0
х1
х2
х3
х4
х5
b/x
11
х1
600
1
0,2
0,1
4
0
600/0,1=6000
0
х5
400
0
0,1
0,2
-8
1
400/0,2=2000
6600
0
-0,3
-1,0
4,4
0
Zk - cn
23
В индексной строке два отрицательных значения. Следовательно, оптимальное решение не получено. Улучшаем решение. Для этого определяем ключевой столбец, который будет располагаться по попеременной х3, так как в индексной строке по этому столбцу находится максимальное по абсолютной величине отрицательное число. Далее находим ключевую строку, для чего рассчитываем оценочные отношения (последний столбец симплексной таблицы) и
выбираем наименьшее положительное число. Наименьшее отношение принадлежит переменной х5. Генеральный элемент равен 0,2.
Переходим к следующей симплексной таблице.
Таблица 1.7
Симплексная таблица № 3
Сбаз
хб
b
11
2,5
2,1
0
0
х1
х2
х3
х4
х5
11
х1
400
1
0,15
0
8
-0,5
2,1
х3
2000
0
0,5
1
-40
5
8600
0
0,2
0
4
5
Zk - cn
b/x
Теперь имеем лишь неотрицательные значения в индексной строке. Следовательно, достигнут максимум целевой функции.
Получено оптимальное решение х1 = 400, х2 = 0, х3 = 2000, х4 = 0, х5 = 0
или Х=(400,0,2000,0,0). Максимальное значение целевой функции равно 8600.
1.4. Метод искусственного базиса (М-метод)
Данный метод решения применяется при наличии в системе ограничений
и условий-равенств, и условий-неравенств и является модификацией симплексного метода. Решение системы производится путём ввода искусственных переменных уi со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отри24
цательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации – с положительными M. Таким
образом, из исходной получается новая M-задача (поэтому метод искусственного базиса также называют M-методом).
Если в оптимальном решении М-задачи нет искусственных переменных,
это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична
от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Симплекс-таблица, которая составляется в процессе решения с использованием метода искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, а другая – для составляющей M ∑ уi. При составлении
симплекс-таблицы полагают, что исходные переменные являются небазисными, а дополнительные (xn+m) и искусственные (уi)- базисными [8].
Исходная таблица для метода искусственного базиса (М-метода) имеет
следующий вид.
Таблица 1.8
Исходная таблица для М-метода
хб, уиск
b
с01
c02
…
с0n
х1
х2
…
хn
хn+1
b1
а11
а12
…
а1n
хn+2
b2
а21
а22
…
а2n
уi
bi
аi1
аi2
…
аmn
…
…
…
…
…
…
F
-b0
- c01
- c02
…
- c0n
M
-∑bi1
-∑ai1
-∑ai2
…
-∑ain
25
b/а
Элементы дополнительной строки M рассчитываются как сумма соответствующих коэффициентов условий-равенств (условий, в которые после приведения
к каноническому виду введены переменные уi), взятая с противоположным знаком.
Алгоритм метода искусственного базиса:
1. Подготовительный этап
Приводим задачу линейного программирования к каноническому виду
F(х)=с01x1+с02x2+...с0nxn → max
а11x1+a12x2+...a1nxn+xn+1=b1,
а21x1+a22x2+...a2nxn+xn+2=b2,
........................................
аi1x1+ai2x2+...ainxn+yi=bi,
......................................
аm1x1+am2x2+...amnxn+xn+m=bm.
В случае, если в исходной задаче необходимо найти минимум, знаки коэффициентов целевой функции F(x) меняются на противоположные a0n =-a0n.
Знаки коэффициентов ограничивающих условий со знаком ≥ также меняются
на противоположные. В случае, если условие содержит знак ≤ или =, коэффициенты запишутся без изменений. К каждому условию-неравенству при переходе к каноническому виду добавляем дополнительную переменную xn+m, к каждому i-му условию-равенству добавляем искусственную переменную уi.
2. Составляем симплексную таблицу, соответствующую исходной задаче.
3. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены).
Если среди них нет отрицательных, то найдено допустимое решение (решение,
соответствующее одной из вершин многогранника условий) и мы переходим к
шагу 4. Если в столбце свободных членов имеются отрицательные элементы, то
выбираем среди них максимальный по модулю – он задает ключевую строку k.
В этой строке также находим максимальный по модулю отрицательный элемент ak1 – он задает ключевой столбец и является генеральным элементом. Пе26
ременная, соответствующая ключевой строке, исключается из базиса, переменная, соответствующая ключевому столбцу, включается в базис. Пересчитываем
симплекс-таблицу согласно правилам.
Если же среди свободных членов есть отрицательные элементы, а в соответствующей строке – нет, то условия задачи несовместимы и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к третьему шагу, если таких нет, то к четвертому.
4. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на
оптимальность. Если среди элементов симплексной таблицы, находящихся в
строках M и F(в расчет не берется элемент b0 – текущее значение целевой
функции и элемент ∑ bi), нет отрицательных, то найдено оптимальное решение.
Если в строке M есть отрицательные элементы, то решение требует
улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая ∑ bi). Столбец, в котором он находится, будет ключевым. Для того чтобы найти ключевую строку, находим отношение соответствующего свободного члена к элементу из ключевого столбца при условии, что
они неотрицательны.
Переменная, соответствующая ключевой строке, исключается из базиса,
переменная, соответствующая ключевому столбцу, включается в базис.
Пересчитываем симплекс-таблицу согласно правилам перехода от одной
симплексной таблицы к другой. Если в новой таблице после перерасчета в
строке M остались отрицательные элементы – переходим к шагу 4.
Если невозможно найти ключевую строку, так как нет положительных
элементов в ключевом столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке M и в столбце свободных членов все элементы положительные, то проверяем положительность элементов строки F.
27
Если имеются отрицательные элементы (b0 не считаем), выбираем среди
отрицательных элементов строки F максимальный элемент по модулю. Столбец, в котором он находится, будет ключевым. Для того чтобы найти ключевую
строку, находим отношение соответствующего свободного члена к элементу из
ключевого столбца при условии, что они неотрицательны. Строка, для которой
это отношение минимально, – ключевая. Элемент, находящийся на пересечении
ключевого столбца и ключевой строки, – генеральный. Переменная, соответствующая ключевой строке, исключается из базиса, переменная, соответствующая ключевому столбцу, включается в базис.
Пересчитываем симплекс-таблицу согласно правилам перехода от одной
симплексной таблицы к другой. Если в новой таблице после перерасчета в
строке F остались отрицательные элементы, то переходим к новой симплексной
таблице и заново проверяем положительность элементов строки F.
Если невозможно найти ключевую строку, так как нет положительных
элементов в ключевом столбце, то функция в области допустимых решений задачи не ограничена – алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
Пример 1.6. Решить задачу линейного программирования симплексным
методом:
F(x) = x1 + 5x2 + 4x3 - 3x4→max
2x1 + 7x2 + x3
≤ 5,
x1 + 4x2 + 2x3 + 8x4 = 6,
-x1 + 2x3 + 5x4 = 9,
х1, х2, х3, х4 ≥ 0.
Решение. Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак ≥, то при
28
переходе к равенству знаки всех его коэффициентов и свободных членов меняются на противоположные знаки. Тогда система запишется в виде:
2х1 + 7х2 + х3 + х5 = 5,
х1 + 4х2 + 2х3 + 8х4 + у1 = 6,
-х1 + 2х3 + 5х4 + у2 = 9,
х1, х2, х3, х4, х5, у1, у2 ≥ 0.
Целевая функция будет иметь вид:
F(x) = x1 + 5x2 + 4x3 - 3x4 + 0х5 – М(у1 + у2) →max
Переходим к формированию исходной симплекс-таблицы. В строку F
таблицы заносятся коэффициенты целевой функции. Так как необходимо найти
максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком.
Так как среди исходного набора условий были равенства, то введены искусственные переменные у. Это означает, что в симплекс-таблицу необходимо
добавить дополнительную строку M, элементы которой рассчитываются как
сумма соответствующих элементов условий-равенств (тех, которые после приведения к каноническому виду содержат искусственные переменные у), взятая с
противоположным знаком.
Из данных задачи составляем исходную симплекс-таблицу.
Таблица 1.9
Исходная таблица
хб,
b
уиск
1
5
4
-3
0
-М
-М
х1
х2
х3
х4
х5
у1
у2
b/а
х5
5
2
7
1
0
1
0
0
∞
у1
6
1
4
2
8
0
1
0
0,75
у2
9
-1
2
0
5
0
0
1
1,8
F
0
-1
-5
-4
3
0
0
0
M
-15
0
-6
-2
-13
0
-1
-1
29
Так как в столбце свободных членов нет отрицательных элементов, то
найдено допустимое решение. В строке M имеются отрицательные элементы,
это означает что полученное решение не оптимально. Определим ключевой
столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент – это -13. Ключевой будет строка, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является у1, а генеральный элемент 8.
По правилам перехода составляем новую симплексную таблицу.
Таблица 1.20
Симплексная таблица
хб,
b
уиск
1
5
4
-3
0
-М
х1
х2
х3
х4
х5
у2
b/а
х5
5
2
7
1
0
1
0
5
х4
0,75
0,125
0,5
0,25
1
0
0
3
у2
5,25
-1,625
-2,5
0,75
0
0
1
7
F
-2,25
-1,375
-6,5
-4,75
0
0
0
M
-5,25
1,625
2,5
-0,75
0
0
-1
В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ключевой столбец. Для этого найдем в
строке M максимальный по модулю отрицательный элемент – это -0,75. Ключевой будет строка, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является
х4, а ведущий элемент – 0,25.
По правилам перехода составляем следующую симплексную таблицу.
30
Таблица 1.21
Симплексная таблица
хб,
b
уиск
1
5
4
-3
0
-М
х1
х2
х3
х4
х5
у2
х5
2
1,5
5
0
-4
1
0
х3
3
0,5
2
1
4
0
0
у2
3
-2
-4
0
-3
0
1
F
12
1
3
0
19
0
0
M
-3
2
4
0
3
0
-1
b/а
В столбце свободных членов и в строке F нет отрицательных элементов.
Выполнение алгоритма на этом завершено, однако не все искусственные переменные (у) были исключены из базиса (условия исходной задачи не совместимы).
Вопросы для самоконтроля и задания
1. Каков состав математической модели задачи линейного программирования?
2. Записать математическую модель общей задачи линейного программирования.
3. Сформулировать задачу оптимального использования ресурсов. Что в
ней представляет целевая функция, ограничения на переменные и условия неотрицательности переменных?
4. Записать экономико-математическую модель задачи о смесях. Что в
ней представляет целевая функция, ограничения на переменные и условия неотрицательности переменных?
5. Какова суть геометрической интерпретации задачи линейного программирования?
6. Каким образом в решении задачи линейного программирования можно
найти минимум целевой функции?
7. В каком случае многогранник допустимых решений будет называться
незамкнутым?
31
8. Каков алгоритм графического метода задачи линейного программирования?
9. В каких случаях решение задачи линейного программирования геометрическим методом целесообразно?
10.
Каков алгоритм симплекс-метода задачи линейного программирования?
11.
Какое решение задачи линейного программирования называется оп-
тимальным и как выбирается генеральный элемент в симплекс-таблице?
Задание 1.1
Предприятие производит изделия трех видов, поставляет их заказчикам и
реализует на рынке. Заказчикам требуется 1000 изделий первого вида. 2000 изделий второго вида и 2500 изделий третьего вида.
Условия спроса на рынке ограничивают число изделий первого вида 2000
единицами, второго – 3000 и третьего – 5000 единицами.
Для изготовления изделий используется четыре типа ресурсов.
Количество ресурсов, потребляемых для производства одного изделия,
общее количество ресурсов и прибыль от реализации каждого вида изделия заданы в табл. 1.22.
Таблица 1.22
Исходные данные
Вид изделий
Тип ресурса
Всего ресурсов
И1
И2
И3
1
250 000
500
300
1000
2
300 000
1000
200
100
3
200 000
150
300
200
4
400 000
100
200
400
20
40
50
Прибыль от единицы изделия, руб.
Составить экономико-математическую модель, которая позволила бы обеспечить заказчиков, не допустить затоваривания и получить максимальную прибыль.
32
Задание 1.2
Для изготовления двух видов продукции P1 и P2 используют четыре вида
ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых
на изготовление единицы продукции, приведены в табл. 1.23.
Прибыль, получаемая от единицы продукции P1 и P2, соответственно
2 руб. и 3 руб.
Необходимо составить такой план производства продукции, при котором
прибыль от ее реализации будет максимальной.
Составить экономико-математическую модель и решить задачу графическим методом.
Таблица 1.23
Исходные данные
Тип ресурса
Запас ресурсов
Число единиц ресурсов, затрачиваемых
на изготовление единицы продукции
Р1
Р2
S1
18
1
3
S2
16
2
1
S3
5
-
1
S4
21
3
-
Задание 1.3
Имеется два вида корма I и II, в состав которых входят питательные вещества (витамины) S1, S2 и S3. Число единиц питательных веществ в 1кг каждого вида
корма и необходимый минимум питательных веществ приведены в табл. 1.24.
33
Таблица 1.24
Исходные данные
Питательное
вещество
Необходимый минимум
питательных веществ
Число единиц питательных единиц
в 1 кг корма
Р1
Р2
S1
18
3
1
S2
16
1
2
S3
5
1
6
Стоимость 1 кг корма I и II соответственно равна 4 руб. и 6 руб.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не
менее установленного предела.
Составить экономико-математическую модель и решить задачу графическим методом.
Задание 1.4
Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г жиров, 700 г белков и 900 г
углеводов. Содержание в 1 кг каждого вида комбикорма жиров, белков и углеводов (граммы) приведено в табл. 1.25.
Таблица 1.25
Исходные данные
Комбикорм
Питательные вещества
А
В
С
Жиры
320
240
300
Белки
170
130
110
Углеводы
380
440
450
Стоимость 1 кг, руб.
31
23
20
34
Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?
Составить экономико-математическую модель и решить задачу симплексным методом.
Задание 1.5
Для изготовления различных изделий А, В и С предприятие использует
три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество
сырья каждого вида, которое может быть использовано предприятием, приведены в табл. 1.26.
Таблица 1.26
Исходные данные
Вид сырья
Общее количество
сырья (кг)
Нормы затрат сырья на одно изделие
А
В
С
I
360
18
15
12
II
192
6
4
8
III
180
5
3
3
9
10
16
Цена одного изделия, руб.
Изделия А, В и С могут производиться в любых соотношениях (сбыт
обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.
Составить план производства изделий, при котором общая стоимость
всей произведенной предприятием продукции является максимальной.
Составить экономико-математическую модель и решить задачу симплексным методом.
35
Задание 1.6
При продаже двух видов товара используется четыре типа ресурсов.
Норма затрат ресурсов на реализацию единицы товара, общий объем каждого
ресурса заданы в табл. 1.27.
Прибыль от реализации одной единицы товара первого вида составляет
2 усл. ед., второго вида – 3 усл. ед.
Требуется найти оптимальный план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль.
Составить экономико-математическую модель, решить задачу графическим и симплексным методами.
Таблица 1.27
Исходные данные
Норма затрат ресурсов на товары
Тип ресурса
Всего ресурсов
1-го вида
2-го вида
1
12
2
2
2
8
1
2
3
16
4
0
4
12
0
4
Задание 1.7
Колхоз имеет возможность приобрести не более 19 трехтонных автомашин
и не более 17 пятитонных. Отпускная цена трехтонного грузовика – 4000 руб.,
пятитонного – 5000 руб. Колхоз может выделить для приобретения автомашин
141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная
грузоподъемность была максимальной, если грузоподъемность одного трехтонного грузовика 3 усл. ед., а пятитонного – 5 усл. ед.?
Составить экономико-математическую модель, решить задачу графическим и симплексным методами.
36
Задание 1.8
Решить задачу графическим методом.
а) Z(x)= 12х1 + 15х2
max(min)
б) Z(x)= х1 + 6х2
min
5х1 + 3х2 ≥ 30,
-2х1 + 12х2 ≥ 8,
х1 - х2 ≤ 3,
4х1 + 2х2 ≤ 10,
-3х1 + 5х2 ≤ 15,
3х1 - 4х2 ≤ 2,
х1, х2 ≥ 0.
4х1 + 5х2 ≥ 8,
х1, х2 ≥ 0.
Задание 1.9
Решить задачу симплексным методом.
а) Z(x)= х1 + 4х2 - 10х3
max
б) Z(x)= -х1 + 2х2 - х3
2х1 + 3х2 + 4х3 = 18,
2х1 + 3х2 + х3 = 3,
3х1 + 9х2 + х3 = 54,
х1 + 3х3 = 2,
х1, х2, х3 ≥ 0.
в) F(x) = 2x1 + 3x2 - x3
max
х1, х2, х3 ≥ 0.
min
г) F(x) =2x1 - x2 +7x3 +11 х4 +5 х5
2x1 + x2 - 3x3 ≥ 6,
2x1 +5 x3 + x4 + 8х5 = 4,
x1 - x2 + 2x3 = 4,
-3x1 + 6x2 + 2x3 - 2х4 ≤ 5,
х1, х2, х3, х4, х5 ≥ 0.
x1 + x2 + x3 ≤5,
х1, х2, х3 ≥ 0.
37
min
Глава 2. Двойственная задача линейного программирования
2.1. Взаимно-двойственные задачи линейного программирования
и их свойства
Двойственная задача в линейном программировании строится по формальным правилам на базе другой задачи линейного программирования, называемой основной. Например, если основная задача имеет вид
Ах ≤b , х≥0, f(с,х) → max,
(2.1)
то двойственная к ней задача также является задачей линейного программирования:
АТу≥ с, у≤0, f(b, у)→ min.
(2.2)
Здесь х = (x1,х2,... ,хn); b = (b1, b2,…,bт); с = (с1, с2,..., сn); у = (y1,y2,... ,уm);
 a11 a12

a22
a
A   21
...
...

 am1 am 2
... a1n 

... a2 n 
.. ;
... ... 

... amn 
n
c x ;
f(c,x)= j 1
j
j
(2.3)
m
T
 b y ; A  транспонированная матрица A.
(b,y)= i 1
i
i
Основная и двойственная к ней задачи образуют пару взаимно двойственных задач: двойственная задача к двойственной оказывается основной задачей.
Модель основной задачи можно записать следующим образом:
n
F x    c j x j  max(min)
j 1
при
n
 a x  b , i  1, 2, m ,
ij
j
i
j 1
x j  0,
j  1, 2,  n .
38
(2.4)
Тогда модель двойственной задачи будет иметь вид:
m
Z  y    bi yi  min(max)
(2.5)
i 1
при
m
 a y  c , j  1, 2, n ,
ij
i
j
i 1
yi  0, i  1, 2,  m .
Переменные yi называются двойственными оценками.
Отношение между прямой и двойственной задачами находит выражение
в виде следующих правил:
1) если прямая задача является задачей максимизации, то двойственная
задача будет задачей минимизации, и наоборот;
2) коэффициенты целевой функции прямой задачи с = (с1, с2,..., сn) становятся свободными членами ограничений двойственной задачи;
3) свободные члены ограничения прямой задачи b = (b1, b2,…,bт) становятся свободными членами целевой функции двойственной задачи;
4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничения прямой задачи;
5) знаки неравенств в ограничениях изменяются на обратные;
6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи [11].
Пример 2.1. Пусть для выпуска четырех видов продукции Р1, Р2, Р3, Р4 на
предприятии используют три вида сырья S1, S2 и S3. Объемы выделенного сырья, нормы расхода сырья и прибыль на единицу продукции при изготовлении
каждого вида продукции приведены в табл. 2.1. Требуется определить план выпуска продукции, обеспечивающий наибольшую прибыль. Составить двойственную задачу линейного программирования.
39
Таблица 2.1
Исходные данные
Вид продукции
Вид сырья
Запасы сырья
Р1
Р2
Р3
Р4
S1
35
4
2
2
3
S2
30
1
1
2
3
S3
40
3
1
2
1
14
10
14
11
Прибыль от единицы продукции, руб.
Решение. Составим экономико-математическую модель задачи оптимального использования ресурсов на максимум прибыли. В качестве неизвестных
примем объем выпуска продукции j-го вида xj (j = 1, 2, 3, 4).
Модель задачи по критерию «максимум прибыли»:
F(x) =14x1 + 10x2 +14x3 +11 х4
max
4x1 + 2x2 + 2x3 + 3х4 ≤ 35,
x1 + x2 + 2x3 + 3х4 ≤ 30,
3x1 + x2 + 2x3 + х4 ≤ 40,
х1, х2, х3, х4 ≥ 0.
Сформулируем двойственную задачу. Пусть некая организация решила
закупить все ресурсы рассматриваемого предприятия. При этом необходимо
установить оптимальную цену на приобретаемые ресурсы у1, у2, y3 исходя из
следующих объективных условий:
1) покупающая организация старается минимизировать общую стоимость
ресурсов;
2) за каждый вид ресурсов надо уплатить не менее той суммы, которую
хозяйство может выручить при переработке сырья в готовую продукцию.
40
Согласно первому условию общая стоимость сырья выразится величиной
Z(y) =35y1 + 30y2 +40y3
min.
Согласно второму требованию вводятся ограничения: на единицу первого
вида продукции расходуются четыре единицы первого ресурса ценой y1, одна
единица второго ресурса ценой у2 и три единицы третьего ресурса ценой у3.
Стоимость всех ресурсов, расходуемых на производство единицы первого вида
продукции, равна 4y1 + y2 +3y3
и должна составлять не менее 14, то есть
4y1 + y2 +3y3 ≥ 14. В результате аналогичных рассуждений относительно производства второго, третьего и четвертого видов продукции получаем систему неравенств:
4y1 + y2 +3y3 ≥ 14,
2y1 + y2 + y3 ≥ 10,
2y1 + 2y2 +2y3 ≥ 14,
3y1 + 3y2 + y3 ≥ 11.
По экономическому смыслу цены неотрицательные: у1, у2, у3 ≥ 0.
2.2. Теоремы двойственности
Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности.
Первая (основная) теорема двойственности:
если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых
функций равны: F (x*) = Z (y*). Здесь х*,у* - оптимальные планы пары двойственных задач. Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система
ограничений другой задачи противоречива.
41
Рассмотрим пару симметричных двойственных задач (2.4) и (2.5). Вводя
дополнительные переменные хn+1, ..., хn+m в прямую задачу и ym+1, ..., уr+n в двойственную, приводим модели задач к каноническому виду.
Теперь между переменными двойственных задач можно установить соответствие, сопоставляя свободные переменные одной задачи и базисные переменные другой, и наоборот (табл. 2.2).
Таблица 2.2
Соответствие между переменными двойственных задач
Переменные основной задачи
Первоначальные
Дополнительные
x1
x2
…
xj
…
xn
xn+1
xn+2
…
xn+i
…
xn+m
ym+1
ym+2
…
ym+j
…
ym+n
y1
y2
…
yj
…
ym
Дополнительные
Первоначальные
Переменные двойственной задачи
Экономическое содержание первой теоремы двойственности состоит в
следующем: если задача определения оптимального плана, максимизирующего
выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана,
совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций
для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор
оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают
как инструмент балансирования затрат и результатов. Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.
е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность
всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы [20].
42
Таким образом, оптимальность плана означает точное воплощение в
оценке произведенной по этому плану продукции оценки всех израсходованных ресурсов, т. е. полное отсутствие непроизводительных затрат.
Вторая теорема двойственности (о дополняющей нежесткости). Для того
чтобы планы х* и у* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
m
*
j
x ( aij yi*  c j )  0, j  1, 2,  n ,
(2.6)
i 1
n
*
i
y ( aij x*j  bi )  0, i  1, 2,  m .
(2.7)
j 1
Условия (2.6), (2.7) называются условиями дополняющей нежесткости. Из
них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какаялибо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом
должно обращаться в строгое равенство.
Экономически это означает, что если по некоторому оптимальному плану
х* производства расход i-го ресурса строго меньше его запаса, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна
нулю. Если же в некотором оптимальном плане оценок его i-я компонента
строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу:
n
 a x   b
ij
opt
j
i

yiopt   0 ,
(2.8)

yiopt   0 ,
(2.9)
j 1
тогда yi является дефицитным ресурсом;
n
 a x   b
ij
opt
j
i
j 1
тогда yi является недефицитным ресурсом.
43
Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.
Третья теорема двойственности (об оценках):
двойственные оценки показывают приращение функции цели, вызванное
малым изменением свободного члена соответствующего ограничения задачи
математического программирования, точнее
 
z х*
 yi* .
bi
(2.8)
Для того чтобы выяснить экономическое содержание третьей теоремы
двойственности, необходимо в равенстве (2.8) дифференциалы заменить приращениями. В результате получаем
 
z x *  yi* bi . При
bi  1 имеем
 
z x *  y i* . Отсюда следует, что величина двойственной оценки численно рав-
на изменению целевой функции при изменении соответствующего свободного
члена ограничений на единицу. В прикладных задачах двойственные оценки
y i* называют скрытыми, теневыми ценами или маргинальными оценками ресурсов [8, 20].
Вопросы для самоконтроля и задания
1. Какая задача линейного программирования называется двойственной?
2. По каким правилам получается двойственная задача линейного программирования из основной?
3. Какими свойствами обладают пары двойственных задач линейного
программирования?
4. Привести примеры двойственных задач, следующих из основных задач
линейного программирования.
44
Задание 2.1
На основании информации, приведенной в табл. 2.3, составить план производства, максимизирующий объем прибыли.
Таблица 2.3
Исходные данные
Затраты ресурсов на единицу
Ресурсы
продукции
Наличие ресурсов
Р1
Р2
Труд
2000
2
4
Сырье
1400
4
1
Оборудование
800
2
1
40
60
Прибыль на единицу продукции, руб.
На основе исходных данных записать экономико-математическую модель. Решить полученную модель графическим методом. Составить двойственную задачу, найти значение двойственных оценок.
Задание 2.2
Решить задачу графическим методом, составить задачу, двойственную
данной, и найти её решение, используя теоремы двойственности.
а) Z(x)= 2х1 + 7х2
max
б) Z(x)= -2х1 - 3х2
-2х1 + 3х2 ≤ 14,
-4х1 + 2х2 ≥ 4,
х1 + х2 ≤ 8,
х1 + х2 ≥ 6,
х1, х2 ≥ 0.
х1, х2 ≥ 0.
45
min
в) F(x) = x1 + x2
max
г) F(x) =3x1 + x2
x1 - 4x2 - 4 ≤ 0,
-2x1 + x2 ≥ 4,
3x1 - x2
≥ 0,
2x1 + x2 ≤ 8,
x1 + x2 - 4 ≥ 0,
х1, х2 ≥ 0.
3x1 + 2x2 ≥ 6,
х1, х2 ≥ 0.
min
Задание 2.3
Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве,
соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов
сырья на единицу продукции данного вида и цена единицы продукции каждого
вида приведены в табл. 2.4.
Таблица 2.4
Исходные данные
Нормы затрат сырья на единицу продукции
Вид сырья
А
В
С
I
4
2
1
II
3
1
3
III
1
2
5
Цена единицы продукции, руб.
10
14
12
Определить план выпуска продукции, при котором обеспечивается ее
максимальная стоимость, и оценить каждый из видов сырья, используемых для
производства продукции. Оценки, приписываемые каждому из видов сырья,
должны быть такими, чтобы оценка всего используемого сырья была мини-
46
мальной, а суммарная оценка сырья, используемого на производство единицы
продукции каждого вида,– не меньше цены единицы продукции данного вида.
На основе исходных данных записать экономико-математическую модель. Решить полученную модель симплексным методом. Составить двойственную задачу, найти значение двойственных оценок.
Задание 2.4
Решить задачу симплексным методом, составить задачу, двойственную
данной, и найти её решение, используя теоремы двойственности.
а) Z(x)= х1 + 2х2 - х3
max
б) Z(x)= 2х1 + 3х2
-х1 + 4х2 - 2х3 ≤ 12,
х1 + 3х2 ≤ 18,
х1 + х2 + 2х3 ≤ 17,
2х1 + х2 ≤ 16,
2х1 - х2 + 2х3 = 4
х2 ≤ 5,
х1, х2, х3 ≥ 0.
3х1 ≤ 21,
min
х1, х2 ≥ 0.
в) F(x) = x1 - x2 + 3x3 – 2х4
max
г) F(x) =3x1 + 5x2 + 4x3 + 5х4
max
x1 - x2 - 2x3 – х4 = -3,
5x1 + 0,4 x2 + 2x3 + 0,5х4 ≤ 400,
2x1 - x2 - x3 + 2х4 = 3,
5x2 + x3 + х4 ≤ 300,
х1, х2, х3, х4 ≥ 0.
x1 + x3 + х4 ≤ 100
х1, х2, х3, х4 ≥ 0.
47
Глава 3. Транспортная задача
3.1. Экономико-математическая модель транспортной задачи. Основные
методы решения транспортной задачи
Важным частным случаем задачи линейного программирования является
транспортная задача.
В общей постановке транспортной задачи предполагается, что из любого
пункта производства в любой пункт потребления может быть перевезено любое
количество груза.
Математическая модель транспортной задачи (ТЗ).
Пусть хij – количество груза, перевозимого с i-го в j-й пункт.
m
n
Целевая функция: W  c11 x11  c12 x12  ...  cmn xmn   cij xij  min .
(3.1)
i 1 j 1
Система ограничений:
 x11  x12  ...  x1n  a1

ограничения по запасам : ......................................
 x  x  ...  x  am
m2
mn
 m1
 x11  x21  ...  xm1  b1

ограничения по спросу : .....................................
 x  x  ...  x  bn.
2n
mn
 1n
(3.2)
Для решения задачи составляется табл. 3.1.
В клетки таблицы записывают стоимость соответствующих перевозок сij
и в них же заносят значения перевозок xij, удовлетворяющие поставленным ограничениям. Клетки с ненулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками
транспортная задача называется сбалансированной или несбалансированной.
48
Таблица 3.1
Матрица (план) перевозок
Аi
Bj
B1
A1
c11
B2
…
Am
…
…
c12
x11
A2
Запасы
c21
x21
…
x11n
x22
…
a1
a2
c2n
…
x2n
…
…
…
cm2
xm1
c1n
x12
c22
cm1
Bn
...
am
cmn
xm2
xmn
m
Потребности
a
b1
b2
bn
…
i
i 1
n
b
j
j 1
m
n
Сбалансированная (закрытая) ТЗ:  a i   b j .
i 1
j 1
m
n
Несбалансированная (открытая) ТЗ:  a i   b j .
i 1
j 1
Опорный план является допустимым решением транспортной задачи и
используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения
опорных планов: метод северо-западного угла, метод минимального элемента и
метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.
Все существующие методы нахождения опорных планов отличаются
только способом выбора клетки для заполнения. Само заполнение происходит
одинаково - независимо от используемого метода.
Базисный план составляется последовательно, из нескольких шагов (точнее, m + n - 1 шагов). На каждом из этих шагов заполняется одна клетка, притом
так, чтобы либо полностью удовлетворялся один из заказчиков (тот, в столбце
49
которого находится заполняемая клетка), либо полностью вывозился весь запас
груза с одной из баз (с той, в строке которой находится заполняемая клетка).
В первом случае можно исключить столбец, содержащий заполненную
на этом шаге клетку. Считается, что задача свелась к заполнению таблицы с
числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем
же количеством строк и с соответственно измененным запасом груза на одной
из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
Во втором случае исключается строка, содержащая заполняемую клетку,
и считается, что таблица сузилась на одну строку при неизменном количестве
столбцов и при соответствующем изменении потребности заказчика, в столбце
которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, приходят к “таблице”, состоящей из одной строки и одного столбца (из одной пустой клетки). Таким образом, пришли к задаче с одной базой и с
одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Когда заполняется последняя клетка, освобождается последняя база и удовлетворяется потребность последнего
заказчика. В результате, совершив (m + n - 1) шагов, приходят к искомому
опорному плану.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на
очередной базе. Тогда после заполнения очередной клетки объем таблицы как
бы одновременно уменьшается на один столбец и на одну строку. Но и при
этом должно считаться, что уменьшение объема таблицы происходит либо на
один столбец, а на базе сохраняется "остаток", равный нулю, либо на одну
строку, а у заказчика еще осталась неудовлетворенная "потребность" в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль ("запас" или "потребность" – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при
50
этом оказывается равной нулю одна из базисных неизвестных, то имеет место
вырожденный случай [9].
При методе северо-западного угла на каждом шаге построения первого
опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с
клетки неизвестного x11 и заканчивается в клетке неизвестного xmn, т. е. идет по
диагонали таблицы перевозок.
При методе наименьшей стоимости (минимального элемента) на каждом шаге построения опорного плана первой заполняется та клетка оставшейся
части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.
Суть метода Фогеля состоит в следующем: в распределительной таблице
по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с
нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом
этапе заполняется только одна клетка. Распределение груза производится, как и
ранее.
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы.
Циклом пересчета или циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:
1. Одно из неизвестных последовательности свободное, а все остальные –
базисные.
2. Каждые два соседних в последовательности неизвестных лежат либо в
одном столбце, либо в одной строке.
3. Три последовательных неизвестных не могут находиться в одном
столбце или в одной строке.
51
4. Если, начиная с какого-либо неизвестного, будут последовательно переходить от одного к следующему за ним неизвестному, то через несколько шагов вернутся к исходному неизвестному.
Второе условие означает, что у двух соседних неизвестных в цикле либо
первые, либо вторые индексы одинаковы.
Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин
которой находится в свободной клетке, а остальные - в базисных клетках.
Для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и число
вершин в цикле всегда четно.
В зависимости от методов подсчета алгебраических сумм тарифов для
свободных клеток различают два метода отыскания оптимального решения
транспортной задачи:
1. Распределительный метод. При этом методе для каждой пустой клетки
строят цикл и для каждого цикла непосредственно вычисляют алгебраическую
сумму тарифов.
2. Метод потенциалов. При этом методе предварительно находят потенциалы баз и потребителей, а затем вычисляют для каждой пустой клетки алгебраическую сумму тарифов с помощью потенциалов.
Преимущества метода потенциалов по сравнению с распределительным
методом состоят в том, что отпадает необходимость построения циклов для каждой из пустых клеток и упрощается вычисление алгебраических сумм тарифов. Цикл строится только один – тот, по которому производится пересчет.
Необходимо иметь в виду, что потенциалы (так же, как и циклы) для каждого нового базисного плана определяются заново [12, 15].
Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.
52
Предварительный этап:
1.
Каким-либо способом ищется допустимый план
(методом северо-
западного угла, минимального элемента или методом Фогеля).
Для полученного плана строится система m+n чисел
2.
, таких, что
3.
,
Построенная система
есть план
,
.
и
исследуется на потенциальность (то
исследуется на оптимальность). Для этого проверяется
,
.
Если система не потенциальна, то переходят к основному этапу, т.к. план
не оптимален, иначе оптимальный план найден.
Основной этап:
1. Улучшаем план, то есть от плана
что
переходим к плану
; такому,
.
2. Для плана
,
строим новую систему
,
,
, такую, что
.
3. Исследуем систему
на потенциальность. Если система не потен-
циальна, то переходим на п.1. Иначе найден оптимальный план.
Пример 3.1. По данным о запасах груза на трех складах, потребностях в
грузе у четырех магазинов и тарифах на перевозки, приведенным в табл. 3.2,
записать экономико-математическую модель задачи оптимального планирования
перевозок груза. Построить первоначальный опорный план методом северозападного угла и методом наименьшего тарифа. Опираясь на план, построенный
методом наименьшего тарифа, найти оптимальный план методом потенциалов.
53
Таблица 3.2
Исходные данные
Аi
Bj
B1
Запасы
B2
В3
B4
A1
7
1
7
4
A2
2
5
8
8
A3
6
1
6
8
Потребности
3
6
7
7
8
6
5
Решение. Обозначим xij - количество груза, перевозимого из пункта i в
пункт j , где i  1, 2, 3 ; j  1, 2, 3, 4 .
Балансовое равенство выполняется (суммарная потребность в грузе
равняется суммарным запасам: 7+8+6=3+6+7+5), значит, транспортная задача закрытая. Тогда экономико-математическая модель задачи выглядит следующим
образом:
Z x   7 x11  x12  7 x13  4 x14  2 x21  5 x22  8 x23  8 x24 
6 x31  x32  6 x33  8 x34  min
 x11  x12  x13  x14  7,
 x  x  x  x  8,
22
23
24
 21
 x31  x32  x33  x34  6,

 x11  x21  x31  3,

 x12  x22  x32  6,
 x13  x23  x33  7,

 x14  x24  x34  5,
 xij  0, i  1, 2, 3; j  1, 2, 3, 4.

Построим первоначальный опорный план методом северо-западного угла.
В левую верхнюю клетку делаем
максимально возможную поставку
x11  min a1 ; b1   min 7; 3  3 . Тем самым на первом складе остается 4
54
единицы груза, а потребности первого магазина удовлетворены полностью,
поэтому следующую перевозку будем осуществлять с первого склада ко
второму потребителю: x12  min a1  3; b2   min 4; 6  4 . Так как при этом на
первом складе запас груза исчерпан, а потребности второго потребителя
удовлетворены не полностью, то производим поставку со второго склада
второму магазину: x 22  2 . Продолжаем до тех пор, пока все запасы не будут
исчерпаны, а потребности магазинов не удовлетворены полностью. В итоге
получаем план перевозок (табл. 3.3).
Таблица 3.3
Опорный план методом северо-западного угла
Аi
Bj
B1
A1
7
B2
1
3
A2
2
Потребности
7
5
6
B4
4
0
8
2
1
0
3
В3
4
0
A3
Запасы
8
6
6
0
6
7
0
8
0
8
1
7
5
5
6
21
21
Посчитаем стоимость перевозки:
Z min  7  3  1  4  5  2  8  6  6  1  8  5  129 (д. ед.).
Построим первоначальный опорный план методом наименьшего тарифа.
На первом шаге заполняется клетка с наименьшим тарифом 1. Заметим, что
клеток с наименьшим тарифом две, но так как максимальные объемы поставок
в обе клетки одинаковы, то заполнение таблицы можно начать как с той, так и с
другой клетки. Будем осуществлять перевозку с первого склада ко второму
потребителю: x12  mina1 ; b2   min7; 6  6 . Тем самым на первом складе
осталась одна единица груза, а потребности второго магазина удовлетворены
полностью. Поэтому далее выбираем клетку с наименьшим тарифом из
второго, четвертого и пятого столбцов таблицы. Это клетка с тарифом 2:
55
x 21  min a 2 ; b1   min 8; 3  3 .
Далее
заполнение
таблицы
происходит
следующим образом:
x13  min a1  6; b3   min 1; 5  1
x33  min a3 ; b3   min 6; 7   6
x23  min a 2  3; b3  6   min 5; 1  1
x24  min a 2  3  1; b4  1  min 4; 4   4 .
Первоначальный опорный план, построенный методом наименьшего
тарифа, представлен в табл. 3.4.
Таблица 3.4
Опорный план методом наименьшего тарифа
Аi
Bj
B1
A1
7
B2
1
0
A2
2
7
5
6
Потребности
B4
4
0
8
0
1
0
3
В3
6
3
A3
Запасы
8
1
6
0
6
7
1
8
4
8
6
7
0
5
6
21
21
тарифа,
на
Стоимость перевозки Z min  92 д. ед.
Проверим
план,
построенный
методом
наименьшего
оптимальность. Для этого по занятым объемами перевозок клеткам составим
систему уравнений:
u1  v 2  1,
u  v  4,
 1 4
u 2  v1  2,

u 2  v 3  8,
u 2  v 4  8,

u 3  v3  6.
56
Неизвестные потенциалы
u1 , u 2 , u3 , v1 , v 2 , v3 , v 4 находим из этой
системы уравнений, полагая u1  0 . Тогда из первого и второго уравнений
v 2  1, v 4  4 , далее из предпоследнего u 2  4 , затем из третьего и четвертого
уравнений v1  2, v3  4 и, наконец, из последнего u3  2 .
Перепишем матрицу перевозок, добавив справа столбец с потенциалами
ui , а внизу строку с потенциалами v j (табл. 3.5).
Таблица 3.5
План перевозок
Аi
Bj
B1
A1
7
B2
1
0
A2
2
Потребности
vj
7
6
5
3
A3
6
В3
0
0
1
0
3
-2
0
6
1
1
8
1
6
ui
7
0
8
4
6
2
B4
4
8
Запасы
4
8
6
7
4
0
5
4
Посчитаем оценки свободных клеток:
11  0  (2)  7  0,
13  0  4  7  0,
 22  4  1  5  0,
 31  2  ( 2)  6  0,
 32  2  1  1  0,
 34  2  4  8  0.
План не оптимальный, так как оценка  32 положительна. Поэтому ставим
в этой клетке знак «+» и строим цикл (табл. 3.6).
57
Таблица 3.6
Цикл пересчета
Bj
Аi
B1
0
B2
1 6
5
0
1
+
3
-2
6
1
7
А1
0
2
А2
3
5
А3
Потребности
vj
B3
+
1
6
B4
4 +
4
8 4
8
0
7
4
5
4
7
0
8
6
Запасы
ui
7
0
8
4
6
2
Заметим, что такой цикл всегда существует и он единственный.
Наименьший объем груза в «минусовых» клетках
d  4 . Новый план
перевозок (табл. 3.7) составляем с учетом следующих изменений: в клетках со
знаком «+» объем перевозок увеличится на 4 ед., в клетках со знаком «-»
уменьшится на 4, а в остальных останется без изменений.
Таблица 3.7
Новый план перевозок
Аi
Bj
B1
A1
7
B2
1
0
A2
2
Потребности
vj
7
2
5
3
A3
6
0
0
4
6
1
8
8
5
6
0
8
2
7
6
ui
7
0
8
2
6
0
B4
4
8
1
0
3
0
В3
Запасы
0
5
4
Для проверки полученного плана на оптимальность составляем систему
уравнений:
58
u1  v2  1,
u  v  4,
 1 4
u2  v1  2,

u2  v3  8,
u3  v2  1,

u3  v3  6.
Решив систему, получаем новые значения для потенциалов ui , v j ,
которые заносим в таблицу перевозок. Проверяя план на оптимальность,
замечаем, что все оценки свободных клеток не положительны, то есть
полученный план перевозок является оптимальным:
0 2 0 8


x opt   3 0 5 0 
 0 4 2 0


Стоимость перевозки Z min  96 д. ед.
3.2. Модели транспортной задачи. Незамкнутая транспортная задача
Если транспортная задача
открытого типа
, то ее всегда
можно привести к закрытому типу введением фиктивного пункта производства
или фиктивного пункта потребления:
1. Если
2.
, то
. Тогда
причем
.
Если
, то
,
59
,
и
.
Транспортная
задача
представляет
собой задачу линейного про-
граммирования, и ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточнения оценок. В этом
случае основная трудность бывает связана с числом переменных задачи (nm) и
числом ограничений (m+n) [18].
Пример 3.2. Для задачи оптимального планирования перевозок груза тарифы перевозок, запасы груза и потребности в грузе такие же, как в примере
3.1, за исключением потребности 3-го магазина, которая составляет 9 ед. Найти
оптимальный план перевозок.
Решение. Задача открытая, так как суммарная потребность в грузе
превышает суммарный запас на три единицы. Поэтому для решения этой
задачи вводим фиктивного поставщика с запасом груза 2 ед. (табл. 3.8).
Таблица 3.8
Матрица тарифов
Аi
Bj
B1
Запасы
B2
В3
B4
A1
7
1
7
4
A2
2
5
8
8
A3
6
1
6
8
A4
0
0
0
0
Потребности
3
6
9
Модель задачи запишется следующим образом:
Z  x   7 x11  x12  7 x13  4 x14  2 x21  5 x22  8 x23  8 x24
 6 x31  x32  6 x33  8 x34  min
60
7
8
6
2
5
 x11  x12  x13  x14  7,

 x21  x22  x23  x24  8,
 x31  x32  x33  x34  6,

 x41  x42  x43  x44  2,

 x11  x21  x31  3,
 x  x  x  6,
22
32
 12
 x13  x23  x33  9,

 x14  x24  x34  5,
 xij  0, i  1, 2, 3, 4; j  1, 2, 3, 4.

Построение первоначального опорного плана, проверка плана на
оптимальность и переход в случае неоптимального плана к новому для
открытой транспортной задачи осуществляются точно так же, как и для
закрытой.
Решая закрытую задачу, находим её оптимальный план:
0

3
~
x opt  
0

0
2
0
4
0
0
5
2
2
5

0
0

0 
Чтобы получить оптимальный план исходной задачи, нужно отбросить
последнюю строку, соответствующую фиктивному поставщику:
x
opt
Отброшенная строка плана
 0 2 0 5


  3 0 5 0
 0 4 2 0


~
x opt
означает, сколько единиц груза
недополучат потребители, а именно третий магазин недополучит 2 ед. груза.
61
3.3. Модели транспортной задачи. Транспортная задача
с ограничением на объем перевозок
В экономике предприятия классические транспортные задачи, рассмотренные выше, встречаются крайне редко. Обычно при составлении экономикоматематической модели задачи транспортного типа приходится вводить целый
ряд дополнительных ограничений, а затем пользоваться методом потенциалов.
Ряд экономических задач легко сводится к транспортной задаче. Наиболее часто встречающиеся ситуации в экономике предприятия:
1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это ограничение требует,
чтобы в матрице перевозок, содержащей оптимальный план, определенные
клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки cij в клетках, перевозки через которые следует запретить. При этом производят завышение величины cij до таких значений, которые заведомо больше всех.
2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей
сталкиваются при решении вопросов, связанных с оптимальным размещением
производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей
его себестоимости. В таких задачах за критерий оптимальности принимают
сумму затрат на производство и транспортировку продукции.
3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеет ограничения по пропускной способности. Если, например, по маршруту AiBj можно провести не более q единиц груза, то Bj -й столбец матрицы
разбивается на два столбца
и
. В первом столбце спрос принимается рав-
62
ным разности между действительным спросом и ограничением q:
во втором – равным ограничению q, т.е.
,
. Затраты cij в обоих столбцах
одинаковы и равны данным, но в первом столбце
в клетке, соответствующей
ограничению q, вместо истинного тарифа cij ставится искусственно завышенный тариф M (клетка блокируется). Затем задача решается обычным способом.
4. Поставки по определенным маршрутам обязательны и должны войти в
оптимальный план независимо от того, выгодно это или нет. В этом случае
уменьшают запас груза у поставщиков и спрос потребителей и решают задачу
относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок.
5. Экономическая задача не является транспортной, но в математическом
отношении подобна транспортной, т.к. описывается аналогичной моделью, например, распределение производства изделий между предприятиями, оптимальное закрепление механизмов по определенным видам работы.
6. Необходимо максимизировать целевую функцию задачи транспортного
типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателя cij . Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице
, а по максимальной положительной разнице
.
Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположительными элементами: все разности
≤ 0.
7. Необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики m родов грузов разбиваются на m
условных поставщиков, а потребители n родов грузов разбиваются на n условных потребителей. С учетом этой разбивки составляют полную транспортную
63
таблицу. При этом заметим, что некоторые маршруты AiBj должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода
не могут заменять друг друга. Этим маршрутам AiBj должна соответствовать
очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, то задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами различного рода
существует связь (например, одни из грузов можно заменить другими), то в
общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач [9].
Пример 3.3. Для задачи оптимального планирования перевозок груза
данные сведены в табл. 3.9.
Таблица 3.9
Исходные данные
Аi
Bj
B2
B1
Запасы
В3
A1
1
2
1
A2
2
3
5
A3
4
2
5
Потребности
10
40
30
30
40
50
Кроме этого наложены дополнительные ограничения на объемы перевозок:
x12  15 ,
(3.3)
x13  10 ,
(3.4)
x33  15 .
(3.5)
Найти оптимальный план перевозок груза.
Решение. Условие (3.3) – это фиксированная перевозка. Чтобы ее учесть,
уменьшим запас a1 и потребность b2 на 15 единиц и положим тариф c12  M ,
64
где
M
− некоторое очень большое число. Для того чтобы учесть
гарантированную перевозку (условие (3.4)), уменьшим запас a1 и потребность
b3 на 10 единиц. Тогда запас a1 уменьшится в целом на 25 единиц.
Ограниченную перевозку (условие (3.5)) учитываем, разбивая столбец b3 на два
столбца: b3 с потребностью 15 и b3 с потребностью 50-10-15=25. В клетке
a3 ; b3 поставим запретительный тариф M , а в остальных клетках столбца b3
продублируем тарифы столбца b3 . Тогда матрица перевозок (табл. 3.10) будет
выглядеть следующим образом.
Таблица 3.10
План перевозок
Аi
Bj
B1
A1
1
B2
1
2
Потребности
1
5
х22
2
х32
25
5
х13//
5
х
/
23
х
/
33
х33//
15
25
5
х31
10
В
х
3
4
//
3
/
13
х12
х21
A3
В
М
х11
A2
Запасы
/
3
//
х 23
М
30
40
Решая вспомогательную задачу, получаем следующий оптимальный план:
~ opt
x
0 0 0 5


  10 0 0 20 
 0 25 15 0 


Чтобы получить оптимальный план исходной задачи, надо просуммировать
два последних столбца матрицы ~
x opt и добавить 15 к x12 и 10 к x13 . Тогда
x
opt
 0 15 15 


 10 0 20  .
 0 25 15 


65
Вопросы для самоконтроля и задания
1. Какова принципиальная суть транспортной задачи и ее особенностей?
2. Какая экономико-математическая модель транспортной задачи называется открытой (закрытой)? Структура экономико-математической модели
транспортной задачи.
3. Какие специальные методы используются для получения допустимого
базисного и оптимального решения транспортной задачи?
4. Охарактеризовать суть и алгоритм метода северо-западного угла. Почему он так называется?
5. В чем состоит проверка исходного плана транспортной задачи на вырожденность?
6. Пояснить суть и алгоритм метода минимального элемента и метода
Фогеля.
7. Охарактеризовать суть и алгоритм метода потенциалов.
8. Что называется потенциалом строки (столбца) транспортной таблицы?
9. Пояснить понятие цикла в транспортной таблице метода потенциалов.
10. Назвать правила построения цикла транспортной таблицы.
11. Каковы условия оптимальности допустимого базисного решения?
12. Какова экономико-математическая модель открытой транспортной задачи? Структура экономико-математической модели транспортной задачи.
13. Приведите алгоритм решения открытой транспортной задачи.
14. Раскрыть понятия «фиктивный поставщик» и «фиктивный потребитель».
15. Какие специальные методы используются для получения допустимого
базисного и оптимального решения незамкнутой транспортной задачи?
16. Какие существуют ограничения на перевозки в транспортных задачах?
17. Каков алгоритм решения транспортной задачи с запретом на перевозки?
18. Каков алгоритм решения транспортной задачи, если перевозка фиксированная?
66
19. Каков алгоритм решения транспортной задачи, если перевозка гарантированная?
20. Каков алгоритм решения транспортной задачи, если перевозка ограниченная?
21. Какие задачи называются многопродуктовыми транспортными задачами?
Задание 3.1
Три ткацкие фабрики А1, А2 и А3 поставляют суровую ткань на отделочные
фабрики В1, В2 и В3. Годовая мощность фабрики А1 - 15 т, А2 – 25 т, А3 – 20 т. Годовая потребность отделочных фабрик В1, В2 и В3 в ткани составляет соответственно 10 т, 20 т, 30 т. Транспортные расходы в рублях на одну тонну ткани следующие:
2
1 4
6
3 5
3
1 4
.
Требуется составить:
- экономико-математическую модель задачи;
- план перевозок суровой ткани с ткацких фабрик на отделочные фабрики, который бы удовлетворял годовую потребность всех трех отделочных фабрик, методами северо-западного угла и минимального элемента.
Задание 3.2
Найти начальный план перевозок в транспортной задаче, заданной матрицей, двумя методами (северо-западного угла и минимального элемента).
Пункты
В1
В2
В3
Запасы
А1
2
3
4
20
А2
1
2
5
40
Потребности
10
20
30
67
Задание 3.3
Методами северо-западного угла и минимального элемента найти план
перевозок в транспортной задаче, заданной матрицей перевозок.
Матрица условий
Пункты
В1
В2
В3
В4
В5
Запасы
А1
3
4
5
1
1
40
А2
2
5
6
1
1
50
А3
3
1
2
3
4
50
А4
2
3
5
6
10
10
Потребности
40
30
10
10
60
Задание 3.4
Найти тремя методами (северо-западного угла, минимального элемента, Фогеля) опорный план транспортной задачи, в которой запасы на трех складах равны 210,
170, 65 ед. продукции. Потребности четырех магазинов равны 125, 90, 130, 100 ед.
продукции. Тарифы перевозки в рублях за единицу продукции следующие:
5 8 1 2
2 5 4 9
9 2 3 1 .
Задание 3.5
Найти тремя методами (северо-западного угла, минимального элемента, Фогеля) опорный план перевозок в транспортной задаче, заданной матрицей перевозок. Проверить на оптимальность план поставок, полученный методом Фогеля.
Матрица условий (перевозок)
Пункты
В1
В2
В3
В4
Запасы
А1
А2
А3
Потребности
1
4
1
30
2
1
2
20
3
1
5
50
5
2
10
50
50
40
60
68
Задание 3.6
На двух складах А1 и А2 имеется соответственно 11 и 14 ед. однородного
груза. Спрос в нем магазинов В1, В2 и В3 соответственно 10, 8 и 7 ед. груза. Тарифы перевозки в рублях за единицу груза следующие:
8 6 5
4 5 7 .
Составить экономико-математическую модель плана перевозок грузов,
чтобы расходы были минимальными. Найти оптимальное распределение поставок и минимальные затраты на перевозку, выполнив первоначальное распределение поставок методом северо-западного угла.
Задание 3.7
Требуется:
- составить экономико-математическую модель задачи;
- найти оптимальное распределение поставок и минимальные затраты на
перевозку, выполнив первоначальное распределение поставок методом северозападного угла.
Матрица условий (перевозок)
Пункты
В1
В2
В3
Запасы
А1
2
3
2
50
А2
2
4
5
70
А3
6
5
7
60
Потребности
60
60
50
69
Задание 3.8
Требуется:
- составить экономико-математическую модель задачи;
- найти оптимальное распределение поставок и минимальные затраты на
перевозку, выполнив первоначальное распределение поставок методом наименьших затрат.
Матрица условий (перевозок)
Пункты
В1
В2
В3
В4
Запасы
А1
2
3
5
7
10
А2
5
4
3
2
20
А3
6
8
9
5
70
А4
4
6
4
3
60
Потребности
30
10
60
50
Задание 3.9
Решить транспортную задачу, выполнив первоначальное распределение
поставок методом наименьших затрат.
Матрица условий (перевозок)
Пункты
В1
В2
В3
В4
В5
В6
Запасы
А1
5
7
1
5
4
9
30
А2
7
5
8
6
3
4
5
А3
6
4
8
3
2
5
45
А4
3
1
7
4
2
3
50
Потребности
10
35
15
25
55
10
70
Задание 3.10
Требуется найти оптимальное распределение поставок и минимальные
затраты на перевозку, выполнив первоначальное распределение поставок методом северо-западного угла. Поставщик А2 гарантированно должен все вывезти.
Матрица условий (перевозок)
Пункты
В1
В2
Запасы
А1
1
2
25
А2
3
4
15
Потребности
10
20
Задание 3.11
Требуется найти оптимальное распределение поставок и минимальные
затраты на перевозку, выполнив первоначальное распределение поставок методом Фогеля.
На перевозки наложены дополнительные ограничения:
- перевозка А1
В2 фиксирована: х12 =15;
- гарантирована перевозка А1
- перевозка А3
В3 в объеме не менее 10: х13≥10;
В3 ограничена: х33≤15.
Решить задачу без ограничений и с ограничениями. В какую сумму
обошлись ограничения на перевозки?
Матрица условий (перевозок)
Пункты
А1
1
2
1
Запасы
30
А2
2
3
5
30
А3
4
2
5
40
Потребности
В1
10
В2
40
В3
50
71
Задание 3.12
Требуется найти оптимальное распределение поставок и минимальные затраты на перевозку, выполнив первоначальное распределение поставок методом Фогеля.
На перевозки наложены дополнительные ограничения:
- перевозка А1
В2 фиксирована: х12 =50;
- гарантирована перевозка А2
- перевозка А2
В3 в объеме не менее 100: х23≥100;
В4 ограничена: х24≤20.
Матрица условий (перевозок)
Пункты
В1
В2
В3
В4
Запасы
А1
2
4
3
5
150
А2
5
3
7
10
200
А3
1
4
3
8
150
Потребности
100
200
140
60
Задание 3.13
Требуется найти оптимальное распределение поставок и минимальные
затраты на перевозку, выполнив первоначальное распределение поставок методом наименьших затрат.
На перевозки наложены дополнительные ограничения:
- запрет на перевозку А3
В4 фиксирован: х34 =0;
- гарантирована перевозка А1
- перевозка А2
В3 в объеме не менее 10: х13≥10;
В2 ограничена: х22≤5.
Матрица условий (перевозок)
Пункты
В1
В2
В3
В4
Запасы
А1
1
1
13
4
20
А2
5
11
5
3
10
А3
6
7
2
8
16
А4
2
13
1
5
7
Потребности
14
17
15
7
72
Глава 4. Теория игр
4.1. Понятие об игровых моделях
В практике организационно-экономической работы иногда имеют место
ситуации, в которых фигурируют две стороны с противоположным отношением к тому или иному экономическому явлению. В условиях такой конфликтной
ситуации или неопределенности поведение каждой стороны носит название игры, а теория принятия оптимальных решений – теории игр.
Теория игр – это математическая теория конфликтных ситуаций. Цель
теории игр – это выработка рекомендаций по разумному поведению участников
конфликта (определение оптимальных стратегий поведения игроков).
От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила устанавливают последовательность ходов, объем
информации каждой стороны о поведении другой и результат игры в зависимости от сложившейся ситуации. Правилами устанавливается также конец игры,
когда некоторая последовательность ходов уже сделана и больше ходов делать
не разрешается.
Теория игр, как и всякая математическая модель, имеет свои ограничения.
Одним из них является предположение о полной (“идеальной”) разумности
противников. В реальном конфликте зачастую оптимальная стратегия состоит в
том, чтобы угадать, в чем противник “глуп”, и воспользоваться этой глупостью
в свою пользу.
Еще одним недостатком теории игр является то, что каждому из игроков
должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации
нередко будет именно выход за пределы известных противнику стратегий,
“ошарашивание” его чем-то совершенно новым, непредвиденным.
73
Теория игр не включает элементов риска, неизбежно сопровождающего
разумные решения в реальных конфликтах. Она определяет наиболее осторожное, “перестраховочное” поведение участников конфликта.
Кроме того, в теории игр находятся оптимальные стратегии по одному
показателю (критерию). В практических ситуациях часто приходится принимать во внимание не один, а несколько числовых критериев. Стратегия, оптимальная по одному показателю, может быть неоптимальной по другим.
Участвующие в игре стороны называются коалициями действия или игроками. Понятие «игрок» может включать не только отдельных действующих
лиц, но и целые производственные коллективы, отрасли промышленности.
Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая:
1) варианты действий игроков;
2) объем информации каждого игрока о поведении партнеров;
3) выигрыш, к которому приводит каждая совокупность действий. Выигрыш или проигрыш может быть задан количественно; например, проигрыш
можно оценить нулем, выигрыш – единицей, а ничью – ½.
В теории игр предполагается, что игра состоит из ходов, выполняемых
игроками одновременно или последовательно.
Ходы бывают личными и случайными. Ход называется личным, если игрок сознательно выбирает его из совокупности возможных вариантов действий
и осуществляет его (например, любой ход в шахматной игре).
Ход называется случайным, если его выбор производится не игроком, а
каким-либо механизмом случайного выбора (например, по результатам бросания монеты).
Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией (ситуацией игры).
Одним из основных понятий теории игр является понятие стратегии.
Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от ситуации,
74
сложившейся в процессе игры. В простых (одноходовых) играх, когда в каждой
партии игрок может сделать лишь по одному ходу, понятия стратегии и возможного варианта действий совпадают. В этом случае совокупность стратегий
игрока охватывает все возможные его действия, а любое возможное для игрока i
действие является его стратегией.
Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от
того, какие стратегии применяет противник.
Могут быть использованы и другие критерии оптимальности.
Возможно, что стратегия, обеспечивающая максимальный выигрыш, не
обладает другим важным представлением оптимальности, как устойчивостью
(равновесностью) решения. Решение игры является устойчивым (равновесным),
если соответствующие этому решению стратегии образуют ситуацию, которую
ни один из игроков не заинтересован изменить [16].
Задача теории игр – нахождение оптимальных стратегий. Целью теории
игр является определение оптимальной стратегии для каждого игрока.
4.2. Платежная матрица. Нижняя и верхняя цена игры
Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим A1, A2, …, Аm. Пусть у игрока В имеется n
личных стратегий, обозначим их B1, B2, …, Bm. Таким образом, игра имеет размерность m × n. В результате выбора игроками любой пары стратегий однозначно определяется исход игры, т. е. выигрыш аij игрока А (положительный или отрицательный) и проигрыш (–аij) игрока В. Предположим, что значения аij известны для
любой пары стратегий (Ai, Bj). Матрица P=( аij), элементами которой являются
выигрыши, соответствующие стратегиям Ai и Bj, называется платежной матрицей
или матрицей игры. Общий вид такой матрицы представлен в табл. 4.1.
75
Таблица 4.1
Платежная матрица
Вj
В1
В2
…
Вn
А1
а11
а12
…
а1n
А2
а21
а22
…
а2n
…
…
…
…
…
Аm
аm1
аm2
…
аmn
Аi
Матричной игрой называется игра, осуществляемая по следующим правилам:
1. В игре участвуют два игрока.
2. Каждый из игроков обладает конечным набором стратегий.
3. Игра заключается в том, что каждый из игроков, не имея информации о
действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами.
Рассмотрим игру m × n с матрицей P=(аij) и определим наилучшую среди
стратегий A1, A2, …, Аm. Выбирая стратегию Аi, игрок А должен рассчитывать,
что игрок В ответит на нее той из стратегий Bj, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).
Обозначим через  наименьший выигрыш игрока А при выборе им стратегии А и для всех возможных стратегий игрока В (наименьшее число в i-й
строке платежной матрицы).
Назовем  нижней ценой игры или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В.
Следовательно,
  max min aij .
i 1,...,m j 1,...,n
76
(4.1)
Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Bj, он учитывает максимально возможный при этом выигрыш
для А. Назовем  верхней ценой игры или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно,
  min max aij .
j 1,..., n i 1,...,m
(4.2)
Cтратегия, соответствующая минимаксу, называется минимаксной стратегией.
Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь
цели, противоположной цели противника.
Если верхняя и нижняя цены игры совпадают, то общее значение верхней
и нижней цены игры  =  =  называется чистой ценой игры или ценой игры.
Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный
(не зависящий от поведения игрока В) выигрыш ν, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока А) проигрыша ν. Говорят, что решение игры обладает устойчивостью, т. е. если один из
игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.
Пара чистых стратегий Ai и Bj дает оптимальное решение игры тогда и
только тогда, когда соответствующий ей элемент аij является одновременно
наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация,
если она существует, называется седловой точкой (по аналогии с поверхностью
седла, которая искривляется вверх в одном направлении и вниз – в другом).
Обозначим А* и В* – пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша первого
77
игрока на каждой паре стратегий: P(Ai Bj) = аij. Тогда из условия оптимальности
в седловой точке выполняется двойное неравенство: P(Ai, B*) ≤ Р(А*, В*) ≤
P(A*, Bj), которое справедливо для всех i  1,..., m; j  1,..., n . Действительно,
выбор стратегии А* первым игроком при оптимальной стратегии В* второго
игрока максимизирует минимальный возможный выигрыш: Р(А*, В*) ≥ P(Ai,
B*), а выбор стратегии В* вторым игроком при оптимальной стратегии первого
минимизирует максимальный проигрыш: Р(А*, В*) ≤ P(A*, Bj) [21].
Пример 4.1. Найти нижнюю и верхнюю цены игры с платежной матрицей
3 2 1
4
с= 10 4 3 10
-2 4 1 2 .
Решение. В каждой строке платежной матрицы найдем наименьший элемент
и запишем его справа от матрицы. В каждом столбце платежной матрицы найдем
наибольший элемент и запишем его снизу от матрицы. В результате получим таблицу:
min aij
j 1,...,n
3 2 1 4
1
10 4 3 10
3
-2 4 1 2
-2
max = 10 4
i  1 ,..., m
max min aij  3
i 1,..., m j 1,..., n
3 10
min max aij  3
j 1,...,n i 1,...,m
Нижняя
цена
игры
  max1,3,2  3 .
Верхняя
цена
игры
  min10,4,3,10  3 . Нижняя и верхняя цены игры совпадают и равны 3, т.е.
рассмотренная игра является игрой с седловой точкой. Седловой точкой является пара (А2,В3), при которой  =  =3.
78
4.3. Сокращение порядка платёжных матриц (доминирование стратегий)
Доминирование в теории игр – ситуация, при которой одна из стратегий
некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов. Обратное понятие – нетранзитивность – возникает, если некоторая стратегия может давать меньшие выигрыши, чем другая, в зависимости
от поведения остальных участников.
При выборе своей стратегии из множества допустимых игрок сравнивает
по предпочтительности исходы от их применения. Может возникать три типа
результатов:
1. Стратегия В доминирует над стратегией A, если при любом поведении
остальных игроков использование стратегии В приводит к не худшему исходу,
нежели использование А. Различают строгое доминирование, когда В дает
больший выигрыш, чем А, в любых условиях, и слабое доминирование, если
при некоторых действиях других игроков В обеспечивает больший выигрыш,
чем А, а при других – одинаковый с А.
2. Стратегия А доминирует над стратегией В, если при любом поведении остальных игроков стратегия В приводит к не лучшему исходу, нежели стратегия А.
Аналогично предыдущему случаю стратегия может доминировать строго и слабо.
3. Стратегии А и В называются нетранзитивными, если В не доминирует
над А и А не доминирует над В. Это означает, что в зависимости от выбора
стратегий другими игроками большие выигрыши игроку может обеспечивать
как выбор стратегии А, так и выбор В [19].
Это понятие обобщается на сравнении более чем двух стратегий.
Стратегия Ak будет доминирующей для 1го игрока, а стратегия As – доминируемой, если выполнено равенство akj  asj для всех индексов j (в доминирующей строке платёжной матрицы все элементы больше или равны соответствующим элементам другой строки).
79
Стратегия Br для 2го игрока является доминирующей, а стратегия Bl доминируемой, если выполнено неравенство air  ail для всех индексов i (в доминирующем столбце платёжной матрицы все элементы меньше или равны соответствующим элементам другого столбца).
Доминируемые стратегии (строки или столбцы) можно исключать из платежной матрицы, так как они заведомо не выгодны для игрока и положение
седловой точки (цена игры) от этого не изменяется.
Пример 4.2. Исключить доминируемые стратегии игроков из платежной
матрицы
 4 1 3 2


 2 0 1 4 .
1 2 5 3


Решение. Замечаем, что все элементы третьего столбца больше элементов
второго столбца матрицы, а также элементы четвертого столбца больше элементов второго столбца, то есть стратегии B3 и B4 являются доминируемыми
стратегиями, а значит, их можно исключить. Получаем матрицу
 4 1


2
0

.
1 2


Далее очевидно, что элементы второй строки полученной матрицы меньше элементов первой строки, поэтому стратегия A2 является доминируемой.
Окончательно получаем платежную матрицу
 4 1

 .
1 2
80
4.4. Смешанные стратегии. Аналитический метод
решения игры типа 2 x 2
Смешанной стратегией S A игрока A называется
применение чистых
стратегий A1 , A2 , Am с вероятностями p1 , p 2 , pm , причем сумма вероятноm
стей равна 1:  pi  1 . Смешанные стратегии игрока A записываются в виде
i 1
строки S A   p1 , p2 , pm  . Аналогично смешанные стратегии игрока B обозначаются S B  q1 , q2 , qn  , где сумма вероятностей появления стратегий равна
n
единице:  q j  1 [17].
j 1
Рассмотрим игру размера 2 x 2, которая является простейшим случаем
конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.
В игре, в которой отсутствует седловая точка, в соответствии с основной
теоремой теории игр оптимальное решение существует и определяется парой


смешанных стратегий S *A   p1* , p2*  и S B  q1 , q2 .
*
*
*
Пусть игра задана платежной матрицей
a
P   11
 a21
a12 
.
a22 
Средний выигрыш игрока A , если он использует оптимальную смешан-


ную стратегию S *A  p1* , p*2 , а игрок B − чистую стратегию B1 (это соответствует 1му столбцу платежной матрицы P ), равен цене игры v [14]:
a11 p1*  a 21 p 2*  v .
Тот же выигрыш получает игрок A , если 2й игрок применяет стратегию
B2 , т. е. a12 p1*  a22 p2*  v . Учитывая, что p1*  p2*  1 , получаем систему уравне*
ний для определения оптимальной стратегии S A и цены игры v :
81
a11 p1*  a21 p2*  v,

*
*
a12 p1  a 22 p2  v,
 *
*
 p1  p2  1.
(
(4.3)
Решая эту систему, получим оптимальную стратегию
p1* 
a22  a 21
,
a11  a 22  a12  a21
p2* 
a11  a12
a11  a22  a12  a21
v
a22 a11  a12 a21
.
a11  a22  a12  a21
(4.4)
и цену игры
(4.5)
При отыскании S B* - оптимальной стратегии игрока B , получаем, что при
любой чистой стратегии игрока A ( A1 или A2 ) средний проигрыш игрока B
равен цене игры v , т. е.
a11q1*  a21q2*  v,

*
*
a12 q1  a22 q2  v,
 *
*
q1  q 2  1.
(
(4.6)
Тогда оптимальная стратегия S B*  q1* , q 2*  определяется формулами [14]:
q1* 
a22  a12
,
a11  a22  a12  a21
q2* 
(4.7)
a11  a21
.
a11  a22  a12  a21
 1 1 
 . Найти ре 1  1
Пример 4.3. Игра задана платежной матрицей: P  
шение игры в смешанных стратегиях аналитическим способом.
Решение. Так как седловая точка отсутствует (  1 ,   1 ), ищем решение в смешанных стратегиях. Для игрока A средний выигрыш равен цене игры v
82
(при B1 и B2 ); для игрока B средний выигрыш равен цене игры v ( A1 и A2 ).
Системы уравнений (4.3) и (4.6) в данном случае имеют вид:
 1 p1*  1 p2*  v,
 *
*
1 p1  1 p2  v,
 *
*
 p1  p2  1.
 1 q1*  1 q2*  v,
 *
*
1 q1  1 q2  v,
 *
*
q1  q2  1.
1
2
*
*
*
*
Решая эти системы, получаем p1  p2  q1  q2  , v  0 .
Это означает, что оптимальная стратегия каждого игрока состоит в том,
чтобы чередовать свои чистые стратегии случайным образом, выбирая каждую
из них с вероятностью 1 2 , при этом средний выигрыш равен 0.
4.5. Геометрическая интерпретация игры типа 2 x 2
Пусть игра задана платежной матрицей
a
P   11
 a21
a12 
.
a22 
По оси абсцисс отложим единичный отрезок A1 A2 (рис. 4.1); точка
A1  x  0  изображает стратегию A1 , а все промежуточные точки этого отрезка –
смешанные стратегии S A 1го игрока. На вертикальной оси ординат откладываются выигрыши при стратегии A1 (то есть числа a11 , a12 ), на вертикальной оси
II-II (см. рис 4.1) – выигрыши при стратегии A2 (числа a21 , a22 ). Точки на вертикальной оси, соответствующие проигрышу 2го игрока при применении им
первой стратегии, обозначим B1 и соединим прямой. Аналогично для второй
стратегии 2го игрока.
В соответствии с принципом минимакса оптимальная стратегия S *A такова,
что минимальный выигрыш игрока A (при наихудшем поведении игрока B ) обращается в максимум. Ординаты точек, лежащих на ломаной B1 NB2 (см. рис. 4.1),
83
показывают минимальный выигрыш игрока A при использовании им любой


смешанной стратегии. Оптимальную стратегию S *A  p1* , p*2 определяет точка
N , в которой минимальный выигрыш достигает максимума; её ордината равна
цене игры v [14].
II
I
B2
B1/
N
B2/
а12
а21
v
B1
а22
а11
I
A1
p2
p1 
II
A2
х
Рис. 4.1 Решение игры 22 графическим методом
Графический метод можно применять при решении игры 2×n и 2×m.
Пример 4.4. Решить графическим методом игру, заданную платежной
матрицей
1,5 3 

P  
 2 1 .
Решение. Откладываем на оси абсцисс единичный отрезок A1 A2 . На вертикальной оси ординат откладываем отрезок a11  1,5 , соответствующий стратегии B1 , и отрезок a12  3 , соответствующий стратегии B2 . На вертикальной оси
II-II отрезок a21  2 соответствует стратегии B1 , отрезок a22  1 соответствует
стратегии B2 (рис. 4.2).
84
II
I
B2
B1/
а12=3
N
B2/
а21= 2
v
B1
а22= 1
а11=1,5
I
A1
p1 
p2
II
A2
х
Рис. 4.2. Решение игры графическим методом
Нижняя цена игры   a11  1,5 , верхняя цена игры   a 21  2 . Седловая
точка отсутствует. Из рис. 4.2 видно, что абсцисса точки N определяет оптимальную стратегию S *A , а ордината – цену игры v . Точка N является точкой
/
пересечения прямых B1 B1/ и B2 B2 .
В общем виде уравнение прямой, проходящей через две точки с координатами  x1; y1  и  x2 ; y2  , записывается следующим образом:
x  x1
y  y1

.
x2  x1 y2  y1
Тогда уравнение прямой B1 B1/ , проходящей через точки 0; 1,5 и 1; 2  :
1
x  0 y  1,5
, откуда y  x  1,5 .

1  0 2  1,5
2
Уравнение прямой B2 B2/ , проходящей через точки 0; 3 и 1; 1 :
x 0 y 3

или y  2 x  3 .
1 0 1 3
Решая систему уравнений:
 y  0,5 x  1,5,

 y  2 x  3,
85
получим
координаты
точки
N:
x*  0,6; y *  1,8 .
Тогда
p2*  x*  0,6 ;
p1*  1  x*  0,4 ; v  y *  1,8 , то есть смешанная стратегия 1го игрока имеет вид:
S *A  0,4; 0,6 , а цена игры v  1,8 . Это означает, что тактика 1го игрока заключается в применении первой стратегии с вероятностью 0,4, а второй с вероятностью 0,6.
4.6. Приведение матричной игры к задаче
линейного программирования
Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не вызывает, поскольку может быть сведено к решению задачи линейного программирования. Покажем это на примере. Пусть игра m × n задана платежной матрицей p = (aij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A1 , A2 , ..., Am , игрок В — стратегиями B1 , B2, ..., Bm.
Необходимо определить оптимальные стратегии S*A = (p*1 , p*2 , ... , p*m) и
S*B = (q*1 , q*2 , ... , q*n), где p*i, q*j — вероятности применения
соответст-
вующих чистых стратегий Ai , Bj, p*1 + p*2 +...+ p*m =1,q*1 + q*2 +...+ q*n = 1.
Оптимальная стратегия S*A удовлетворяет следующему требованию. Она
обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при
любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной
стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы aij ≥ 0. Если игрок А применяет смешанную стратегию S*A = ( p*1 , p*2 , ... , p*m ) против любой чистой стратегии Bj игрока В, то
он получает средний выигрыш или математическое ожидание выигрыша
aj = a1j p1 + a2j p2 +...+ am j pm , j = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A1 , A2 , ..., Am и результаты складываются).
86
Для оптимальной стратегии S*A все средние выигрыши не меньше цены
игры v, поэтому получаем систему неравенств:
а11р1 + а21р2 + …+ аm1pm ≥ v,
а12р1 + а22р2 + …+ аm2pm ≥ v,
…
а1nр1 + а2nр2 + …+ аmnpm ≥ v.
(4.8)
Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:
x1 =
p1
p
p
, x2 = 2 , ..., m .
v
v
v
(4.9)
а11x1 + а21x2 + …+ аm1xm ≥ 1,
а12x1 + а22x2 + …+ аm2xm ≥ 1,
…
а1nx1 + а2nx2 + …+ аmnxm ≥ 1.
(4.10)
Цель игрока А — максимизировать свой гарантированный выигрыш, т.е.
цену игры v.
Разделив на v ≠ 0 равенство p1 + p2 + ...+ pm = 1 , получаем, что переменные x1 (i = 1, 2, ..., m) удовлетворяют условию: x1 + x2 + ...+ xm =
зация цены игры v эквивалентна минимизации величины
1
. Максимиv
1
, поэтому задача
v
может быть сформулирована следующим образом: определить значения переменных xi ≥ 0, i = 1, 2, ..., m так, чтобы они удовлетворяли линейным ограничениям (4.10) и при этом линейная функция
Z = x1 + x2 + ...+ xm
(4.11)
обращалась в минимум. Это задача линейного программирования. Решая задачу (4.10)—(4.11), получаем оптимальное решение p*1 + p*2 + ...+ p*m и оптимальную стратегию SA .
87
Для определения оптимальной стратегии S*B = (q*1 + q*2 + ...+ q*n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти max
1
. Переменные q1 , q2 , ..., qn удовлетворяют неравенствам:

а11q1 + а12q2 + …+ а1nqn ≤ v,
а21q1 + а22q2 + …+ а2nqn ≤ v,
…
аm1q1 + аm2q2 + …+ аmnqn ≤ v,
(4.12)
которые следуют из того, что средний проигрыш игрока В не превосходит цены
игры, какую бы чистую стратегию ни применял игрок А.
Если обозначить
yj =
qj
v
, j = 1, 2, ..., n,
(4.13)
то получим систему неравенств:
а11y1 + а12y2 + …+ а1nyn ≤ 1,
а21y1 + а22y2 + …+ а2nyn ≤ 1,
…
аm1y1 + аm2y2 + …+ аmnyn ≤ 1,
(4.14)
Переменные yj (1, 2, ..., n) удовлетворяют условию y1 + y2 +… + yn =
1
.
v
Игра свелась к следующей задаче:
определить значения переменных yj ≥ 0, j = 1, 2, ..., n, которые удовлетворяют системе неравенств (4.14) и максимизируют линейную функцию
Z' = y1 + y2 + ...+ yn.
(4.15)
Решение задачи линейного программирования (4.13), (4.14) определяет
оптимальную стратегию S*B = (q*1 + q*2 + ...+ q*n) . При этом цена игры
v=
1
1

.
/
min Z
max Z
(4.16)
Задачи линейного программирования (4.10), (4.11) и (4.14), (4.15) являются взаимно-двойственными. Очевидно, при определении оптимальных страте88
гий в конкретных задачах следует выбрать ту из взаимно-двойственных задач,
решение которой менее трудоемко, а решение другой задачи найти с помощью
теорем двойственности. Приведем примеры экономических задач, которые
описываются игровыми моделями m х n и могут быть решены методами линейного программирования [14].
Пример 4.5. Предприятие может выпускать три вида продукции
 A1 , A2 , A3  , получая при этом прибыль, зависящую от спроса, который может
быть в одном из четырех состояний  B1 , B2 , B3 , B4  . Дана матрица, элемент aij
которой характеризует прибыль, получаемую предприятием при выпуске i -й
3

продукции с j -м состоянием спроса: P   9
7

3
6
10
4
7
5
8

2 .
4 
Определить оптимальные пропорции, гарантирующие среднюю величину
прибыли при любом состоянии спроса.
Решение. Замечаем, что 2я стратегия 2го игрока является дублируемой 1й
стратегией, значит, ее можно исключить. Тогда преобразованная матрица при-
 3 6 8


мет вид: P   9 4 2  . Так как нижняя цена игры   4 не равна верхней цене
 7 5 4




игры   6 , то решение игры ищем в смешанных стратегиях: S *A  p1* , p2* , p3* ,


S B*  q1* , q2* , q3* .
Обозначим xi 
qj
pi
, y j  , где v - цена игры. Составим две взаимноv
v
двойственные задачи линейного программирования. Для оптимальной стратегии 1го игрока все средние выигрыши (то есть элементы j -го столбца платежной матрицы почленно умножаются на соответствующие вероятности выбора
стратегий 1го игрока и результаты складываются) не меньше цены игры. В силу
введенных обозначений получаем:
89
3 x1  9 x2  7 x3  1,
6 x  4 x  5 x  1,
 1
2
3

8 x1  2 x2  4 x3  1,
 xi  0, i  1, 2, 3.
Цель игрока A - максимизировать свой гарантированный проигрыш, то
есть цену игры. Максимизация цены игры эквивалентна минимизации величины
1
. Поэтому целевая функция запишется следующим образом:
v
Z  x   x1  x2  x3  min .
Для оптимальной стратегии 2го игрока все средние проигрыши не больше
цены игры, а цель игрока B - минимизировать свой проигрыш (т.е. максимизировать величину
1
). Тогда задача линейного программирования запишется
v
следующим образом:
F  y   y1  y2  y3  max
3 y1  6 y 2  8 y3  1,
9 y  4 y  2 y  1,
 1
2
3

7 y1  5 y2  4 y3  1,
 y j  0, j  1, 2, 3.

Решив одну из двух задач симплекс-методом, другую можно решить,
применив
свойства
двойственных
оценок.
Получим
3
2
p*   ; 0;
,
5
5
4 
1
q*   ; 0;
; 0  . Это означает, что оптимальные пропорции выпуска про5 
5
дукции, гарантирующие среднюю величину прибыли, – это 40% продукции 1го
вида и 60% 3го. Оптимальный спрос находится в 20% в состоянии B1 и в 80% в
состоянии B3 .
90
Вопросы для самоконтроля и задания
1. Что такое игра с точки зрения теории?
2. Основные виды игр. Их различия.
3. Какие игры называются антагонистическими?
4. Какие игры называются матричными?
5. Как представляется игра в нормальной форме?
6. Какие игры называются биматричными?
7. Какая ситуация в игре называется равновесной?
8. В каком случае в матричной игре есть равновесие в чистых стратегиях?
9. Что такое максимин и как его найти?
10. Что такое минимакс и как его найти?
11. Что такое нижняя цена игры и как её найти?
12. Что такое верхняя цена игры и как её найти?
13. Как найти решение матричной игры, если в ней нет равновесия в чистых
стратегиях?
Задание 4.1
Игра Мора. Каждый из двух игроков на поднятой руке показывает один
или два пальца.
Правила игры:
1. Оба игрока на опущенной вниз руке показывают, сколько по их предположению покажет другой игрок на поднятой вверх руке.
2. Пальцы, предварительно сжатые в кулак, разжимаются одновременно.
3. Если предположение одного из игроков оправдалось, а у другого не
оправдалось, то он выигрывает.
4. Выигрыш равен сумме пальцев обоих игроков на поднятых руках.
5. Если ни один игрок не угадал число пальцев на поднятой руке противника, то игра заканчивается вничью.
6. Если оба игрока угадали, то тоже ничья.
Построить платежную матрицу игры, определить нижнюю и верхнюю
цену игры и проверить наличие седловой точки.
91
Задание 4.2
Игрок А записывает одно из двух чисел: 1 или 2, игрок В – одно из трех
чисел: 1, 2 и 3. Если оба числа одинаковой четности, то игрок А выигрывает и
выигрыш равен сумме этих чисел. Если четности выбранных игроками чисел не
совпадают, то игрок В выигрывает, выигрыш равен сумме этих чисел.
Построить платежную матрицу игры, определить нижнюю и верхнюю
цену игры и проверить наличие седловой точки.
Задание 4.3
Два игрока, один из которых представляет швейную фабрику (игрок А), а
другой – сбытовую организацию (игрок В), на оптовой ярмарке пытаются
прийти к соглашению о заключении договора на производство новых изделий.
Игрок А уверен в перспективности предлагаемых моделей; наоборот, игрок В
считает, что их производство принесет торговле убытки. Далее игрок А для осуществления своей цели располагает тремя стратегиями (m=3), игрок В – двумя
(n=2). Результаты этой игры характеризуются данными платежной матрицы
11,6 9,8
9,3
9,6
12,5 7,8
.
Построить платежную матрицу игры, определить нижнюю и верхнюю
цену игры и проверить наличие седловой точки.
Задание 4.4
Игра задана платежной матрицей
а)
5 1
3 4
0 0
2 -2
-1 5
2 1 ,
в) 4
3
7
8
5 6 7 9
4 6 7 6
6 10 8 11
5 4 7 3
,
б) 5 3 8 2
1 6 4 3
9 5 4 7 ,
г) 10 9 -13 -15
16 11 3
14
7 -9 -17 5
-9 15 -14 -10
1 18 -14 -14 .
92
Найти решение игры, т.е. определить нижнюю и верхнюю цену игры и
минимаксные стратегии.
Задание 4.5
Аналитическим и графическим методами найти решение и цену игры, заданной следующими платежными матрицами:
а)
12 22
32
б)
2 ,
г) 1 3
д)
8 2 ,
-2
2
1
-1 ,
в)
5 6
7 2
,
8 9
10 5 .
Задание 4.6
Найти решение игры аналитическим и графическим методами, предварительно исключив доминируемые стратегии из заданной матрицы:
а) 3 1 2 0 -1 2 5
4 4 3 -1 2 2 7
г) 2
2
5
0
1
5
2
1
1
4
1
1
2
2
3
2
2 0
2 3
4 3
3 2 ,
,
б) 4 1 3 2
2 0 1 4
1 2 5 3 ,
д)
3 5 2 0
6 -1 3 5
93
.
в)
5 1
-2 2
3 -1
4 0 ,
СПИСОК ЛИТЕРАТУРЫ
1. Приказ Минобрнауки РФ от 20.05.2010 № 543 (ред. от 31.05.2011) «Об
утверждении и введении в действие федерального государственного образовательного стандарта высшего профессионального образования по направлению
подготовки 080100 Экономика (квалификация (степень) "магистр")» [Электронный ресурс] // Режим доступа: КонсультантПлюс.
2. Приказ Минобрнауки РФ от 20.05.2010 № 544 (ред. от 31.05.2011) «Об
утверждении и введении в действие федерального государственного образовательного стандарта высшего профессионального образования по направлению
подготовки 080200 Менеджмент (квалификация (степень) "бакалавр")» [Электронный ресурс] // Режим доступа: КонсультантПлюс.
3. Гинзбург, А.И. Экономический анализ: Предмет и методы. Моделирование ситуаций. Оценка управленческих решений: учебник для вузов. Стандарт
третьего поколения / А.И. Гинзбург. – СПб.: Питер, 2011. – 448 c.
4. Красс, М.С. Математика для экономического бакалавриата: учебник по
направлению «Экономика» / М.С. Красс, Б.П. Чупрынов. – М.: ИНФРА-М,
2013. – 472 с.
5. Лугинин, О.Е. Экономико-математические методы и модели: теория и
практика с решением задач: учебное пособие / О.Е. Лугинин, В.Н. Фомишина. –
Ростов н/Д: Феникс, 2010. – 440 с.
6. Орлова, И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров / И.В. Орлова. – М.: Юрайт, 2013. – 328 с.
7. Чупрынов, Б.П. Математика в экономике: математические методы и
модели: учебник для бакалавров / Б.П. Чупрынов, М.С. Красс. – М.: Юрайт,
2013. – 541 с.
8. Федосеев, В.В. Экономико-математические методы и прикладные модели: учебник для бакалавриата и магистратуры / В.В. Федосеев, А.Н. Гармаш
[и др.]. – 4-е изд., доп. и перераб. – М.: Юрайт, 2014. – 327 с.
9. Афонин, В.В. Моделирование систем: учебно-практическое пособие
/ В.В. Афонин. – М.: БИНОМ. ЛЗ, ИНТУИТ, 2012. – 231 c.
94
10. Барботько, А.И. Основы теории математического моделирования: учебное пособие / А.И. Барботько, А.О. Гладышкин. – Ст. Оскол: ТНТ, 2013. – 212 c.
11. Власов, М.П. Моделирование экономических систем и процессов:
учебное пособие / М.П. Власов, П.Д. Шимко. – М.: ИНФРА-М, 2013. – 336 c.
12. Волгина, О.А. Математическое моделирование экономических процессов и систем: учебное пособие для бакалавриата / О.А. Волгина, Н.Ю. Голодная, Н.Н. Одияко. – 3-е изд., стереотип. и доп. – М.: КНОРУС, 2014. – 200 c.
13. Дуплякин, В.М. Теория игр: учеб. пособие / В.М. Дуплякин. – Самара:
Изд-во Самар. гос. аэрокосм. ун-та, 2011. – 191 с.
14. Кремер, Н.Ш. Исследование операций в экономике: учеб. пособие для
вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман. – 3-е изд., перераб. и доп. – М.: Юрайт, 2013. – 438 с.
15. Орлова, И.В. Экономико-математическое моделирование: практическое
пособие по решению задач / И.В. Орлова. – М.: Вузовский учебник, ИНФРА-М,
2013. – 140 c.
16. Самаров, К.Л. Элементы теории игр: учебное пособие / К.Л. Самаров.
– М.: Резольвента, 2010. – 21 с.
17. Теория игр: программа учебной дисциплины и методические указания
к выполнению контрольной работы / сост. Л. В. Березина. – Рыбинск: РГАТА,
2011. – 24 с.
18. Кривошеева, В.С. Математические методы исследований в экономике:
программа курса. Проблемно-тематический курс / В.С. Кривошеева. – 4-е изд.,
перераб. и доп. – М.: МИЭП, 2010. – 60 с.
19. Доминирование (теория игр) [Электронный ресурс] // Режим доступа:
http://49l.ru/a/dominirovanie_teoriya_igr.
20. Основные теоремы двойственности [Электронный ресурс] // Режим
доступа: http://studopedia.ru/3_76324_osnovnie-teoremi-dvoystvennosti-i-ihekonomi-cheskoe. html.
21.
Теория
игр
[Электронный
ресурс]
//
Режим
доступа:
http://edu.dvgups.ru/METDOC/EKMEN/ETR/EK_MATM_M/METOD/U_P_PR/W
EBUMK/frame/5.htm.
95
Учебное издание
Печникова Алена Геннадьевна
Грузинцева Наталья Александровна
Роньжин Владимир Иванович
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
ЭКОНОМИЧЕСКИХ СИСТЕМ
Научный редактор А.Б. Петрухин
Редактор Т.В. Лукьянова
Подписано в печать 23.06.2015. Формат 1/16 60х84.
Бумага писчая. Офсетная печать. Усл. печ. л. 5,58. Уч.-изд. л. 3,0.
Тираж 50 экз. Заказ №
ФГБОУ ВО «Ивановский государственный политехнический университет»
Издательский центр ДИВТ
153000 г. Иваново, Шереметевский проспект, 21
Отпечатано в ОАО «Информатика»
153032 г. Иваново, ул. Ташкентская, 90
96