ример выполнения первого задания
Пример. Четыре предприятия могут производить некоторую однородную продукцию в количестве соответственно 100, 250, 200 и 300. На эту продукцию есть заказ от пяти потребителей соответственно в количестве 200, 200, 100, 100 и 250. Затраты с производством и доставкой единицы продукции задаются матрицей:
.
1. Постройте математическую модель заданной экономической системы.
2. Найдите опорный план методами: северо-западного угла; минимальной стоимости; двойного предпочтения.
3. Постройте систему потенциалов и проверьте найденные планы на оптимальность.
4. Найдите оптимальный план методом потенциалов, взяв за первоначальный любой из опорных планов, не являющихся оптимальным.
Решение. Построение математической модели заданной экономической системы. Сформулируем математическую задачу: пусть некоторый однородный продукт, сосредоточен у т = 4 поставщиков Аi в количестве аi (i = 1, 2, ..., т) единиц соответственно, необходимо доставить этот продукт п потребителям Вj в количестве bj (j = 1, 2, ..., n) единиц. Известна стоимость cij перевозки единицы продукта от i-го поставщика к j-у потребителю заданная матрицей стоимостей. Необходимо составить такой план перевозки продукта, который имеет минимальную стоимость.
Прежде чем составлять математическую модель заданной системы необходимо проверить условие закрытости задачи: а именно, что суммарные запасы равны суммарным потребностям, т. е. все запасы должны быть вывезены, а потребности удовлетворены:
.
Так как суммарные потребности равны суммарным запасам, имеем закрытую транспортную задачу. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-у потребителю, и запишем условие задачи в виде матрицы планирования(таблица 4.1).
Таблица 4.1 – Матрица планирования
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ai | |
| A1 | x11 | x12 | x13 | x14 | x15 | |
| A2 | x21 | x22 | x23 | x24 | x25 | |
| A3 | x31 | x32 | x33 | x34 | x35 | |
| А4 | x41 | x42 | x43 | x44 | x45 | |
| Потребности bj |
Составим математическую модель задачи. Так как от i-го поставщика к j-у потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит cijxij. Стоимость всего плана выразится двойной суммой:
Систему ограничений получим из следующих условий задачи:
а) все продукты должны быть вывезены, то есть,
, (i = 1, 2, 3, 4),
эти уравнения получаются из строк таблицы 4.1;
б) все потребности должны быть удовлетворены, то есть,
, (j = 1,2, ..., 5),
уравнения получаются из столбцов таблицы 4.1.
Таким образом, математическая модель имеет следующий вид:
(4.1)
при ограничениях:
(4.2)
где 
, 
, 
.
Иначе математическую модель можно записать в следующем виде:
F=10х11+7х12+4х13+1х14+4х15+2х21+7х22+10х23+6х24+11х25+8х31+5х32+3х33+2х34+2х35+11х41+8х42+12х43+16х44+13х45® min
при ограничениях:
Таким образом, математическая постановка данной задачи состоит в нахождении такого не отрицательного решения системы линейных уравнений, при котором целевая функция принимает минимальное значение.
1. Определение опорного плана методами: северо-западного угла; минимальной стоимости; двойного предпочтения.
Найдем опорный план методом северо-западного угла. Для этого запишем условие задачи в виде таблицы 4.2. Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика A1.
Для этого сравниваем а1=100 с b1=200, a1<b1, меньший из объемов, т. е. =100ед. записываем в левый нижний угол клетки A1B1. Запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки вычеркиваем. Потребности B1 остались неудовлетворенными на 200 –100 = 100 ед. Сравниваем этот остаток с запасами поставщика А2: т. к.
100 < 250, то 100 ед. записываем в клетку A2B1, чем полностью удовлетворяем потребности потребителя B1, оставшиеся клетки в первом столбце вычеркиваем.
У поставщика A2 осталось 150 ед. груза. Удовлетворяем потребности потребителя B2 за счет оставшихся у поставщика A2 запасов. Для этого сравниваем этот остаток с потребностями потребителя B2: 150<200, записываем 150 ед. в клетку A2B2 и, т. к. запасы A2 полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности B2 остались неудовлетворенными на 50ед. Удовлетворяем их за счет поставщика А3 и переходим к удовлетворению B3 за счет остатка, имеющегося у поставщика А3, и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного план заканчивается.
Таким образом, в таблице 4.2 в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, в левых нижних углах – числа, определяющие план перевозок. Проверим, является ли план, построенный в таблице опорным. Видим, что начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым клеткам, невозможно. Следовательно, план является опорным. В то же время план является невырожденным, т. к. он содержит точно m + n – 1=4 + 5 – 1 = 8 занятых клеток.
Таблица 1.4 – Построение первоначального опорного плана методом северо-западного угла
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ai | |
| A1 | – | – | – | – | ||
| A2 | – | – | ||||
| A3 | – | |||||
| А4 | – | – | – | |||
| Потребности bj |
Если же занятых клеток будет меньше, чем m + n – 1, то следует ввести в любую незанятую клетку объем груза равный нулю и, таким образом, вырожденный план привести к невырожденному.
Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же клетках:
F = 10010+1002+1507+505+1003+502+5016+25013=6950(ед. стоимости).
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального.
Построение опорного плана удобно выполнять в табличном процессоре Excel. Для этого необходимо ввести данные таблицы 4.2 на рабочий лист Excel, затем эту таблицу скопировать и удалить все числа, оставив название полей. Затем в соответствующие ячейки по строке «Потребности» и столбцу «Запасы» ввести формулы для подсчета сумм перевозок по строкам и столбцам. Затем заполнить ячейки таблицы значениями перевозок.
Рисунок 4.1 – Построение первоначального опорного плана методом северо-западного угла
На рисунке 4.1 представлен рабочий лист Excel с введенными в первой таблице исходными данными задачи: стоимостями, запасами и потребностями, а во второй таблице – формулами для подсчета сумм перевозок по строкам:=СУММ(K3:O3) и столбцам: =СУММ(K3:K6) и найденным опорным планом.
В ячейке А10 введена формула, с помощью которой определяется целевая функция: =СУММПРОИЗВ(B3:F6;K3:O6).
Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то план будет значительно ближе к оптимальному.
Найдем опорный план методом минимальной стоимости. Сущность метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, потребности удовлетворены.Составим с помощью этого метода опорный план уже рассмотренной задачи и запишем ее условие в таблицу 4.3. Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке А1В4), так как а1=b4, 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A2B1 и в клетке A3B5. Заполняем любую из них, например, A2B1.
Имеем 200<250, следовательно, записываем в нее 200 и исключаем из рассмотрения столбец B1. В клетку A3B5 записываем 200 ед. и исключаем из рассмотрения строку A3.
Таблица 4.3 – Построение первоначального опорного плана методом минимальной стоимости
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ai | |
| A1 | – | – | – | – | ||
| A2 | – | – | ||||
| A3 | – | – | – | – | ||
| А4 | – | 100– | – | |||
| Потребности bi |
В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, потребности удовлетворены. В результате получен план Х=(x14=100; x21=200; x22=50; x35=200; x42=150; x43=100; x45=50), остальные значения переменных равны нулю. План не содержит циклов и состоит из семи положительных перевозок, следовательно, является опорным планом. Определим его стоимость:
F = 100 1+200 2+50 7+200 2+ 150 8+ 100 12++50 13=4300 (ед.).
Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.
Определим опорный план методом двойного предпочтения. Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем:
В каждом столбце отмечают знаком «V» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «VV» (рисунок 4.4).
В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком «V». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.
Таблица 4.4 – Выделенные клетки с минимальной стоимостью
| Поставщики, Ai | Потребители, В j | Запасы | ||||
| В 1 | В 2 | В 3 | В 4 | В 5 | ai | |
| A1 | VV 1 | |||||
| A2 | VV 2 | |||||
| A3 | V 5 | V 3 | V 2 | VV 2 | ||
| А4 | V 8 | |||||
| Потребности bj |
Затем сначала заполняем клетки A1B4, A2B1, A3B5, потом клетку A3B5. В оставшейся части таблицы последовательно заполняем клетки по минимальной стоимости A3B2, A3B3, A3B4 , A4B2, (таблица 4.5).
Таблица 4.5 – Опорный план, найденный методом двойного предпочтения
| Поставщики, Ai | Потребители, Вj | Запасы ai | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| A1 | – | – | – | VV 1 | – | |
| A2 | VV 2 | – | – | – | ||
| A3 | – | V 5 – | V 3 – | V 2 – | VV 2 | |
| А4 | – | V 8 | – | – | ||
| Потребности bj |
Найдем стоимость полученного опорного плана.
F= 100 1+200 2 +50 10+200 2+200 8+50 12+50 13 = 4250 (ед.).
Таким образом, наименьшую стоимость имеет опорный план, полученный методом двойного предпочтения, следовательно, он наиболее близок к оптимальному плану. Однако отсюда не следует вывод, что с помощью метода двойного предпочтения всегда получают лучший первоначальный план по сравнению с методом минимальной стоимости.
Можно показать, что задача линейного программирования двойственная классической транспортной задаче (4.1, 4.2) состоит в максимизации целевой функции:
(4.4)
при ограничениях
, (4.5)
где числа 
и 
называются соответственно потенциалами поставщиков и потребителей. Для того чтобы решение классической транспортной задачи было оптимальным необходимо выполнение следующей теоремы:
Теорема.Если план 
транспортной задачи является оптимальным, то ему соответствует система из m+n чисел и , удовлетворяющих условиям:
, для x*ij>0, (4.6)
, для x*ij=0. (4.7)
Из теоремы следует: для того, чтобы первоначальный опорный план был оптимальным, необходимо выполнение следующих условий:
- для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке ;
- для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке .
Если хотя бы одна незанятая клетка не удовлетворяет этому условию, то опорный план не является оптимальным и его можно улучшить, перемещая в эту клетку некоторое количество груза.
Используя первое условие теоремы 4.6, построим систему потенциалов (таблица 4.6), используя таблицу 4.5, предварительно проверив, сколько занятых клеток имеет таблица. Если занятых клеток меньше, чем m+n-1 заполняем недостающие клетки нулевыми перевозками.
Систему потенциалов можно построить только для невырожденного плана, который, как известно, содержит m+n-1 занятых клеток, поэтому для него можно составит систему из m+n-1 независимых уравнений 
с m+n неизвестными.
Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному (обычно 
) присваивают нулевое значение, после этого остальные потенциалы определяются однозначно.
Пусть известен потенциал , тогда 
, если известен потенциал 
, то 
.
Таким образом, для определения неизвестного потенциала от величины 
надо вычесть известный потенциал.
Так как в нашем примере m = 4, n = 5, то для того, чтобы найденный в таблице 4.5 план был невырожденным, он должен содержать 4 + 5 – 1 = 8 занятых клеток.
В таблице 4.5 всего шесть занятых клеток, следовательно, в две не занятые клетки необходимо поместить нулевые перевозки.
Заполним нулевыми перевозками клетки A2В2 и A2В4, так как во второй строке среди незанятых клеток они имеют минимальную стоимость перевозок, а именно: 6 и 7.
Запишем целевую функцию двойственной задачи, которую необходимо максимизировать. 
при ограничениях:
Получили систему из восьми неравенств и девяти неизвестных. Выберем в качестве свободной переменной 
, тогда потенциалы 
определятся однозначно. Запишем найденные значения потенциалов в таблицу 4.6.
Проверим выполнение условия 
(4.7) теоремы для незанятых клеток, если условие не выполняется, найдем разность 
и запишем в соответствующую клетку (таблица 4.7).
Таблица 4.6 – Построение системы потенциалов
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=7 | В3,b3=11 | В4,b4=6 | В5,b5=11 | ai | |
| A1,a1=-5 | ||||||
| A2,a2=0 | ||||||
| A3,a3=-9 | ||||||
| А4,a4=1 | ||||||
| Потребности bi |
Таблица 4.7 – Проверка является ли найденный план оптимальным
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=7 | В3,b3=11 | В4,b4=6 | В5,b5=11 | ai | |
| A1,a1=-5 | ||||||
| A2,a2=0 | ||||||
| A3,a3=-9 | ||||||
| А4,a4=1 | ||||||
| Потребности bi |
Условие оптимальности не выполняется для трех клеток А1В3, А1В5 и А2В3. Разности для этих клеток соответственно равны 2, 2, 1. Выберем клетку, в которую необходимо перераспределить перевозку. Для этого определим 
, значит любую из клеток А1В3, А1В5 можно сделать занятой. Возьмем клетку А1В5, так как в этом случае легче построить цикл, отметим ее знаком «+». Клетка А1В5 присоединяется к занятым клеткам, которых становиться m+n. Таким образом, появляется цикл, все вершины которого, за исключением одной, которая находится на клетке, отмеченной знаком «+», лежат на занятых клетках, причем этот цикл единственный.
Находим цикл и, двигаясь от клетки отмеченной знаком «+», поочередно проставляем знаки «–», «+» в клетках с вершинами цикла (таблица 4.8). Находим 
– минимальное значение среди перевозок, стоящих в вершинах цикла, отмеченных знаком «–».
Таблица 4.8 – Построение цикла
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=7 | В3,b3=11 | В4,b4=6 | В5,b5=11 | ai | |
| A1,a1=-5 | 1 – | 4 + |
Продолжение таблицы 4.8
| A2,a2=0 | 6 + | 11 – | ||||
| A3,a3=-9 | ||||||
| А4,a4=1 | ||||||
| Потребности bi |
К перевозкам, стоящим в занятых клетках, прибавляем 50, а из перевозок, стоящих в незанятых клетках, вычитаем 50, получаем новый план (таблица 4.9).
Таблица 4.9 – Новый опорный план
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=7 | В3,b3=11 | В4,b4=6 | В5,b5=9 | ai | |
| A1,a1=-5 | ||||||
| A2,a2=0 | ||||||
| A3,a3=-7 | ||||||
| А4,a4=1 | ||||||
| Потребности bi |
Пересчитываем потенциалы, так клетка А2В5 стала не занятой, а клетка А1В5 прибавилась к занятым клеткам. Проверяем является ли найденный план оптимальным. Условие оптимальности не выполняется для двух клеток А1В3 и А2В3. Разности для этих клеток соответственно равны
2, 1. Выберем клетку, в которую необходимо перераспределить перевозку. Для этого определим 
, значит клетку А1В3 надо сделать занятой. Отметим ее знаком «+». Клетка А1В3 присоединяется к занятым клеткам, которых становиться m+n. Таким образом, появляется цикл все вершины которого, за исключением одной, которая находится на клетке, отмеченной знаком «+», лежат на занятых клетках, причем этот цикл единственный (таблица 4.10). Находим цикл и, двигаясь от клетки отмеченной знаком «+», поочередно проставляем знаки «–», «+» в клетках с вершинами цикла.
Таблица 4.10– Построение цикла
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=7 | В3,b3=11 | В4,b4=6 | В5,b5=9 | ai | |
| A1,a1=-5 | + | 1 – | ||||
| A2,a2=0 | 7– | 6 + | ||||
| A3,a3=-7 | ||||||
| А4,a4=1 | 8+ | 12– | ||||
| Потребности bi |
Определяем 
– минимальное значение среди перевозок, стоящих в вершинах цикла, отмеченных знаком
«–». Значит, нулевую перевозку необходимо переместить в клетку А1В3, сделав ее занятой, и опять пересчитать потенциалы (таблица 4.11).
Проверяем найденный план на оптимальность. Для всех незанятых клеток условие оптимальности выполняется. Значит, найденный план является оптимальным.
Находим значение целевой функции.
Таблица 4.11 – Построение новой системы потенциалов
| Поставщики, Ai | Потребители, Вj | Запасы | ||||
| В1,b1=2 | В2,b2=5 | В3,b3=9 | В4,b4=6 | В5,b5=9 | ai | |
| A1,a1=-5 | ||||||
| A2,a2=0 |
Продолжение таблицы 4.11
| A3,a3=-7 | ||||||
| А4,a4=3 | ||||||
| Потребности bi |
Fmin = 1·50+4·50+6·50+2·200+2·200+8·200+12·100=4150.
max=-5·100+0·250-7·200+3·300+2·200+5·200+9·100+6·100+9·250 =4150.
Так как Fmin=max = 4150, т.е. целевая функция и прямой, и двойственной задачи имеет одно и тоже значение и выполняется условие оптимальности для незанятых клеток таблицы 4.11, значит, найденный план является оптимальным.
Ответ: Fmin= 4150 при: x14 = 50, x15 =50, x12 =200, x14 =50, x35 =200,
x42 =200, x43 =100.
Проверим полученный результат, решив задачу с помощью инструмента «Поиск решения» табличного процессора Excel.
Для того чтобы загрузить инструмент «Поиск решения» необходимо выполнить команду: Файл/ Параметры (рисунок 4.2).
В появившемся окне диалога «Параметры Excel» выбрать команду Надстройки, затем в поле «Надстройки» перейти в раздел «Неактивные надстройки приложений» выбрать Поиск решения и нажать кнопку Перейти.
В появившемся окне диалога «Надстройки» поставить флажок напротив инструмента «Поиск решений» и нажать кнопку ОК(рисунок 4.3). Затем перейти в меню на вкладку «Данные» (рисунок 4.4) заполнить окно диалога «Поиск решения» и нажать кнопку Найти решение. Появиться окно диалога «Результаты поиска решения» (рисунок 4.5), в котором необходимо нажать кнопкуОК.
Рисунок 4.2 – Выбор команды Параметры из меню Файл
 |
Рисунок 4.3 – Окно диалога «Параметры Excel»
Рисунок 4.4 – Окно диалога «Надстройки»
Рисунок 4.5 – Рабочий лист с введенными данными и окно диалога «Поиск решений»
Рабочий лист с решением задачи, представленной матрицей планирования (таблица 4.1), в системе компьютерной математики Mathcad представлен на рисунке 4.6.
Рисунок 4.6 – Алгоритм решения задачи в Mathcad
4.2 Пример выполнения второго задания
Пример.Найти решение игры, заданной матрицей
Решение. Исследование в матричных играх начинается с нахождения седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой точки заканчивается решение игры и записывается ответ: цена игры, соответствующая найденной седловой точке и стратегии первого и второго игроков соответствующие этой цене игры. Если же игра не имеет седловой точки в чистых стратегиях, то найденные нижняя и верхняя чистые цены этой игры указывают, что первый игрок не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры.
Решение начинаем с исследования платежной матрицы игры. Прежде всего, проверим наличие седловой точки в данной матрице А. Для этого найдем минимальные элементы в каждой из строк (1, 2 и 3) и максимальные элементы в каждом из столбцов (8, 5 и 6).
(4.8)
Затем определим нижнюю цену игры 
и верхнюю цену игры 
(рисунок 4.7).
Рисунок 4.7 – Алгоритм поиска нижней и верхней цены игры в Mathcad
Так как нижняя цена игры 
, а верхняя цена игры 
, т.е. игра не имеет седловой точки, а значит, нет решения в чистых стратегиях. Решением игры являются смешанные оптимальные стратегии, а цена игры n заключена в пределах 3£ n£ 5.Предположим, первый игрок А применяет свои чистые стратегии А1, А2 и А3 с вероятностями р1, р2 и р3 соответственно. Сумма вероятностей равна единице. Тогда, если второй игрок применит свои чистые стратегии В1 или В2 или В3, то игрок А получит средний выигрыш, больше или равный цене игры, т. е. получим следующую систему неравенств:
. (4.9)
Так как сумма вероятностей равна единице, получим следующее уравнение:
(4.10)
Разделим все члены неравенств системы (1.9) и уравнение (1.10) на n и заменим полученные выражения соответственно на: 
. Система (4.9) и уравнение (4.10) примет следующий вид:
Так как первый игрок стремиться сделать свой выигрыш как можно больше, т. е. сделать значение цены игры максимальным, следовательно, сумма 
. Таким образом, получим следующую задачу линейного программирования:
Найти значения 
при которых целевая функция 
примет минимальное значение:
при условии:
(4.11)
Найдя решения полученной задачи линейного программирования, вычислим цену игры и соответствующие вероятности по формулам:
; 
.
Проведя аналогичные рассуждения для второго игрока, получим задачу линейного программирования двойственную к задаче (4.11):
Найти значения 
при которых целевая функция 
примет максимальное значение:
при условии:
(4.12)
. или 
Пример решения задачи в Excel для второго игрока приведен на рисунке 4.8. Аналогично находиться решение для первого игрока (рисунок 4.9).
Ответ: Оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, т. е. первому игроку, чтобы выиграть не менее 4, надо чередовать применение первой и третьей стратегии, выбирая каждую с вероятностью 0,5, а вторую стратегию не применять. Второму игроку, чтобы не дать выиграть первому игроку больше, чем 4, необходимо в 4 раза реже применять свою первую чистую стратегию по сравнению со второй и в 5 раз реже по сравнению с третьей.
Рисунок 4.8 – Рабочий лист с результатами решения задачи поиска смешанных стратегий для второго игрока и заполненными полями окна диалога «Параметры поиска решения»
При решении задачи теории игр рекомендуется использовать следующий алгоритм:
1. Исключить из платежной матрицы игры заведомо невыгодные стратегии. Такими стратегиями для первого игрока (второго игрока) являются те, которым соответствуют строки (столбцы) с элементами, меньшими (большими) по сравнению с элементами других строк (столбцов).
Рисунок 4.9 – Рабочий лист с результатами решения задачи для первого игрока и заполненными полями окна диалога «Параметры поиска решения»
2. Определить имеет ли игра седловую точку. Для этого необходимо найти верхнюю и нижнюю цену игры:
2.1. Если они равны, то игра имеет седловую точку, а значит решение в чистых стратегиях и сразу можно записать ответ, так как соответствующие ей стратегии игроков будут оптимальными.
2.2. Если верхняя и нижняя цены игры не равны, то необходимо искать решение игры в смешанных стратегиях путем сведения ее к задаче линейного программирования.
3. Процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы:
3.1. Составляют пару двойственных задач линейного программирования, эквивалентных данной матричной игре.
3.2. Определяют оптимальные планы пары двойственных задач.
3.3. Используя соотношение между планами пары двойственных задач, оптимальными стратегиями и ценой игры, находят решение игры.
5. СТРУКТУРА КОНТРОЛЬНОЙ РАБОТЫ, ОБЩИЕ ТРЕБОВАНИЯ К ЕЕ НАПИСАНИЮ
При выполнении контрольной работы необходимо:
- провести подбор материала в соответствии с предложенной темой;
- оформить теоретический материал в соответствии с требованиями ГОСТ 2.105-95 ЕСКД. Общие требования к текстовым документам и ГОСТ 2.105-96 ЕСКД. Текстовые документы;
- решить задачи по соответствующим темам.
Контрольная работа сдается преподавателю в электронном виде в формате *.doc. на диске и печатном (формат А4).
Параметры текста контрольной работы:
- поля: левое – 30 мм; правое – 10 мм; верхнее – 20 мм; нижнее
20 мм.
- межстрочное расстояние – полуторное;
- переплет 0 см;
- штифт Times New Roman Cyr;
- размер шрифта 14 пунктов;
- абзац – 1,25 см.
Листы отчета по контрольной работе должны быть пронумерованы и скреплены.
6. РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ, ПРИМЕРНЫЙ КАЛЕНДАРНЫЙ ПЛАН ЕЕ ВЫПОЛНЕНИЯ
Материал к теоретической части необходимо подобрать в течение следующей недели после получения задания, оформить его и сдать на проверку, а затем приступать к выполнению практической части.
Выполнять практическую часть необходимо с помощью прикладного программного обеспечения.
Примерный календарный план выполнения контрольной работы по дисциплине «Теория информационных процессов и систем» представлен в таблице.6.1.
Таблица 6.1 – Календарный план
| Наименование этапа работы | Срок выполнения |
| Выдача задания | 2 неделя триместра |
| Выполнение контрольной работы: - подбор информации по теоретической части; - оформление теоретической части работы; - выполнение практической части; - оформление отчета по контрольной работе. | 3 –7 недели триместра |
| Сдача работы на проверку: 1. Теоретической части; 2. Практической части. | 4 неделя триместра 8 неделя триместра |
| Проверка контрольной работы | 4,8 недели триместра |
| Доработка (исправление) работы | 5,9недели триместра |
| Защита контрольной работы | 9 неделя триместра |
7 ПОРЯДОК ЗАЩИТЫ И ОТВЕТСТВЕННОСТЬ СТУДЕНТА ЗА ВЫПОЛНЕНИЕ ЗАДАНИЙ КОНТРОЛЬНОЙ РАБОТЫ
Контрольная работа сдается на проверку в срок не менее чем за 10 дней до защиты. После проверки студент либо допускается к защите, либо дорабатывает и вносит исправления в соответствии с замечаниями преподавателя. Программная реализация обязательно прилагается на диске и демонстрируется преподавателю. Во время защиты контрольной работы студент делает доклад (около 5 минут), в котором кратко излагает теоретический материал, в соответствии с предложенной темой, результаты и технологию решения задач в выбранном программном средстве. Доклад должен быть представлен в виде презентации.
Если студент на защите получает оценку «незачтено», то тема контрольной работы изменяется. Изменение темы происходит и в том случае, когда несколько теоретических частей абсолютно одинаковы.
8 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
8.1 Основная литература
1. Гончаров, В. А. Методы оптимизации : учеб. пособие [Текст] / В. А. Гончаров. – М. : Высшее образование, 2009. – 191 с. – (Основы наук). – Библиогр.: с. 191. – ISBN 978-5-9692-0337-2
2. Исследование операций в экономике : учеб. пособие [Текст]/
[Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман] / под ред. Н. Ш. Кремера. – М. : ЮНИТИ, 2006. – 408 с. : ил. – Библиогр.: с. 393 – 394. –Предм. указ.: с. 395 – 402. – ISBN 5-238-00636-5
3. Исследование операций в экономике : учеб. пособие [Текст]/
[Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман] / под ред. Н. Ш. Кремера. - М. : Юрайт, 2010. – 430 с. : ил. – (Основы наук). – Гриф: Рек. МО. – Библиогр.: с. 413 – 414.
8.2 Дополнительная литература
1.Волков, И. К. Исследование операций: учебник для вузов [Текст] / И. К. Волков, Е. А. Загорулько, под ред. В. С. Зарубина, А. П. Крищенко. – М. : Изд-во МГТУ им. Н. Э. Баумана, 2000– 368 с.
2.ГОСТ 2.105-95 ЕСКД. Общие требования к текстовым документам. . – М.: Издательство стандартов, 1999. – 23 с.
3. ГОСТ 2.105-96 Общие требования к текстовым документам. – М.: издательство стандартов, 1996. – 22 с.
4.Пантелеев, А. В. Методы оптимизации в примерах и задачах : учеб. пособие [Текст] / А. В. Пантелеев, Т. А. Летова. – М. : Высшая школа, 2002. –544 с. : ил. – (Прикладная математика для ВТУЗов). – Библиогр.: с. 543 – 544. –ISBN 5-06-004137-9
5. Аттетков, А. В. Методы оптимизации : учебник для втузов [Текст] / А. В. Аттетков, С. В. Галкин, В. С. Зарубин ; под ред. В. С. Зарубина, А. П. Крищенко. – Изд. 2-е, стереотип. – М. : Издательствово МГТУ им.
Н. Э. Баумана, 2003. – 440 с.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению контрольной работы по дисциплине
«Теория информационных процессов и систем»
для студентов специальностей 230201.65 «Информационные системы и технологии» и 230200.62 «Информационные системы»
Составитель Г. В. Шагрова
Редактор
Подписано в печать
Формат 60x84 1/16. Усл. п.л. – Уч.-изд. л..
Бумага газетная. Печать офсетная. Заказ Тираж 50 экз.
ФГБОУ УВПО «Северо-Кавказский государственный технический университет»
355029, г. Ставрополь, пр. Кулакова, 2
Типография СевКавГТУ