Поделиться Поделиться

ример выполнения первого задания

Пример. Четыре предприятия могут производить некоторую однородную продукцию в количестве соответственно 100, 250, 200 и 300. На эту продукцию есть заказ от пяти потребителей соответственно в количестве 200, 200, 100, 100 и 250. Затраты с производством и доставкой единицы продукции задаются матрицей:

ример выполнения первого задания - Инвестирование -  1 .

1. Постройте математическую модель заданной экономической системы.

2. Найдите опорный план методами: северо-западного угла; минимальной стоимости; двойного предпочтения.

3. Постройте систему потенциалов и проверьте найденные планы на оптимальность.

4. Найдите оптимальный план методом потенциалов, взяв за первоначальный любой из опорных планов, не являющихся оптимальным.

Решение. Построение математической модели заданной экономической системы. Сформулируем математическую задачу: пусть некоторый однородный продукт, сосредоточен у т = 4 поставщиков Аi в количестве аi (i = 1, 2, ..., т) единиц соответственно, необходимо доставить этот продукт п потребителям Вj в количестве bj (j = 1, 2, ..., n) единиц. Известна стоимость cij перевозки единицы продукта от i-го поставщика к j-у потребителю заданная матрицей стоимостей. Необходимо составить такой план перевозки продукта, который имеет минимальную стоимость.

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

ример выполнения первого задания - Инвестирование -  2 .

Так как суммарные потребности равны суммарным запасам, имеем закрытую транспортную задачу. Обозначим через 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. Стоимость всего плана выразится двойной суммой:

ример выполнения первого задания - Инвестирование -  3

Систему ограничений получим из следующих условий задачи:

а) все продукты должны быть вывезены, то есть,

ример выполнения первого задания - Инвестирование -  4 , (i = 1, 2, 3, 4),

эти уравнения получаются из строк таблицы 4.1;

б) все потребности должны быть удовлетворены, то есть,

ример выполнения первого задания - Инвестирование -  5 , (j = 1,2, ..., 5),

уравнения получаются из столбцов таблицы 4.1.

Таким образом, математическая модель имеет следующий вид:

ример выполнения первого задания - Инвестирование -  6 (4.1)

при ограничениях:

ример выполнения первого задания - Инвестирование -  7 (4.2)

где ример выполнения первого задания - Инвестирование -  8 , ример выполнения первого задания - Инвестирование -  9 , ример выполнения первого задания - Инвестирование -  10 .

Иначе математическую модель можно записать в следующем виде:

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

при ограничениях:

ример выполнения первого задания - Инвестирование -  11

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

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 = 100·10+100·2+150·7+50·5+100·3+50·2+50·16+250·13=6950(ед. стоимости).

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального.

Построение опорного плана удобно выполнять в табличном процессоре Excel. Для этого необходимо ввести данные таблицы 4.2 на рабочий лист Excel, затем эту таблицу скопировать и удалить все числа, оставив название полей. Затем в соответствующие ячейки по строке «Потребности» и столбцу «Запасы» ввести формулы для подсчета сумм перевозок по строкам и столбцам. Затем заполнить ячейки таблицы значениями перевозок.


ример выполнения первого задания - Инвестирование -  12

ример выполнения первого задания - Инвестирование -  13

Рисунок 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) состоит в максимизации целевой функции:

ример выполнения первого задания - Инвестирование -  14 (4.4)

при ограничениях

ример выполнения первого задания - Инвестирование -  15 , (4.5)

где числа ример выполнения первого задания - Инвестирование -  16 и ример выполнения первого задания - Инвестирование -  17 называются соответственно потенциалами поставщиков и потребителей. Для того чтобы решение классической транспортной задачи было оптимальным необходимо выполнение следующей теоремы:

Теорема. Если план ример выполнения первого задания - Инвестирование -  18 транспортной задачи является оптимальным, то ему соответствует система из m+n чисел ример выполнения первого задания - Инвестирование -  16 и ример выполнения первого задания - Инвестирование -  17 , удовлетворяющих условиям:

ример выполнения первого задания - Инвестирование -  21 , для x*ij>0, (4.6)

ример выполнения первого задания - Инвестирование -  22 , для x*ij=0. (4.7)

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

- для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке ример выполнения первого задания - Инвестирование -  21 ;

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

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

Используя первое условие теоремы 4.6, построим систему потенциалов (таблица 4.6), используя таблицу 4.5, предварительно проверив, сколько занятых клеток имеет таблица. Если занятых клеток меньше, чем m+n-1 заполняем недостающие клетки нулевыми перевозками.

Систему потенциалов можно построить только для невырожденного плана, который, как известно, содержит m+n-1 занятых клеток, поэтому для него можно составит систему из m+n-1 независимых уравнений ример выполнения первого задания - Инвестирование -  25 с m+n неизвестными.

Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному (обычно ример выполнения первого задания - Инвестирование -  26 ) присваивают нулевое значение, после этого остальные потенциалы определяются однозначно.

Пусть известен потенциал ример выполнения первого задания - Инвестирование -  26 , тогда ример выполнения первого задания - Инвестирование -  28 , если известен потенциал ример выполнения первого задания - Инвестирование -  29 , то ример выполнения первого задания - Инвестирование -  30 .

Таким образом, для определения неизвестного потенциала от величины ример выполнения первого задания - Инвестирование -  31 надо вычесть известный потенциал.

Так как в нашем примере m = 4, n = 5, то для того, чтобы найденный в таблице 4.5 план был невырожденным, он должен содержать 4 + 5 – 1 = 8 занятых клеток.

В таблице 4.5 всего шесть занятых клеток, следовательно, в две не занятые клетки необходимо поместить нулевые перевозки.

Заполним нулевыми перевозками клетки A2В2 и A2В4, так как во второй строке среди незанятых клеток они имеют минимальную стоимость перевозок, а именно: 6 и 7.

Запишем целевую функцию двойственной задачи, которую необходимо максимизировать. ример выполнения первого задания - Инвестирование -  32

при ограничениях:

ример выполнения первого задания - Инвестирование -  33

Получили систему из восьми неравенств и девяти неизвестных. Выберем в качестве свободной переменной ример выполнения первого задания - Инвестирование -  34 , тогда потенциалы ример выполнения первого задания - Инвестирование -  35 определятся однозначно. Запишем найденные значения потенциалов в таблицу 4.6.

Проверим выполнение условия ример выполнения первого задания - Инвестирование -  36 (4.7) теоремы для незанятых клеток, если условие не выполняется, найдем разность ример выполнения первого задания - Инвестирование -  37 и запишем в соответствующую клетку (таблица 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. Выберем клетку, в которую необходимо перераспределить перевозку. Для этого определим ример выполнения первого задания - Инвестирование -  38 , значит любую из клеток А1В3, А1В5 можно сделать занятой. Возьмем клетку А1В5, так как в этом случае легче построить цикл, отметим ее знаком «+». Клетка А1В5 присоединяется к занятым клеткам, которых становиться m+n. Таким образом, появляется цикл, все вершины которого, за исключением одной, которая находится на клетке, отмеченной знаком «+», лежат на занятых клетках, причем этот цикл единственный.

Находим цикл и, двигаясь от клетки отмеченной знаком «+», поочередно проставляем знаки «–», «+» в клетках с вершинами цикла (таблица 4.8). Находим ример выполнения первого задания - Инвестирование -  39 – минимальное значение среди перевозок, стоящих в вершинах цикла, отмеченных знаком «–».

Таблица 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. Выберем клетку, в которую необходимо перераспределить перевозку. Для этого определим ример выполнения первого задания - Инвестирование -  40 , значит клетку А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  

Определяем ример выполнения первого задания - Инвестирование -  41 – минимальное значение среди перевозок, стоящих в вершинах цикла, отмеченных знаком
«–». Значит, нулевую перевозку необходимо переместить в клетку А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,
x
42 =200, x43 =100.

Проверим полученный результат, решив задачу с помощью инструмента «Поиск решения» табличного процессора Excel.

Для того чтобы загрузить инструмент «Поиск решения» необходимо выполнить команду: Файл/ Параметры (рисунок 4.2).

В появившемся окне диалога «Параметры Excel» выбрать команду Надстройки , затем в поле «Надстройки» перейти в раздел «Неактивные надстройки приложений» выбрать Поиск решенияи нажать кнопку Перейти .

В появившемся окне диалога «Надстройки» поставить флажок напротив инструмента «Поиск решений» и нажать кнопку ОК (рисунок 4.3). Затем перейти в меню на вкладку «Данные» (рисунок 4.4) заполнить окно диалога «Поиск решения» и нажать кнопку Найти решение . Появиться окно диалога «Результаты поиска решения» (рисунок 4.5), в котором необходимо нажать кнопкуОК .

ример выполнения первого задания - Инвестирование -  42

Рисунок 4.2 – Выбор команды Параметрыиз меню Файл

 
  ример выполнения первого задания - Инвестирование -  43

Рисунок 4.3 – Окно диалога «Параметры Excel»

ример выполнения первого задания - Инвестирование -  44

Рисунок 4.4 – Окно диалога «Надстройки»


ример выполнения первого задания - Инвестирование -  45

Рисунок 4.5 – Рабочий лист с введенными данными и окно диалога «Поиск решений»


Рабочий лист с решением задачи, представленной матрицей планирования (таблица 4.1), в системе компьютерной математики Mathcad представлен на рисунке 4.6.

ример выполнения первого задания - Инвестирование -  46

Рисунок 4.6 – Алгоритм решения задачи в Mathcad


4.2 Пример выполнения второго задания

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

ример выполнения первого задания - Инвестирование -  47

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

Решение начинаем с исследования платежной матрицы игры. Прежде всего, проверим наличие седловой точки в данной матрице А. Для этого найдем минимальные элементы в каждой из строк (1, 2 и 3) и максимальные элементы в каждом из столбцов (8, 5 и 6).

ример выполнения первого задания - Инвестирование -  48 (4.8)

Затем определим нижнюю цену игры ример выполнения первого задания - Инвестирование -  49 и верхнюю цену игры ример выполнения первого задания - Инвестирование -  50 (рисунок 4.7).

ример выполнения первого задания - Инвестирование -  51

Рисунок 4.7 – Алгоритм поиска нижней и верхней цены игры в Mathcad

Так как нижняя цена игры ример выполнения первого задания - Инвестирование -  52 , а верхняя цена игры ример выполнения первого задания - Инвестирование -  53 , т.е. игра не имеет седловой точки, а значит, нет решения в чистых стратегиях. Решением игры являются смешанные оптимальные стратегии, а цена игры n заключена в пределах 3£ n£ 5.Предположим, первый игрок А применяет свои чистые стратегии А1, А2 и А3 с вероятностями р1, р2 и р3 соответственно. Сумма вероятностей равна единице. Тогда, если второй игрок применит свои чистые стратегии В1 или В2 или В3, то игрок А получит средний выигрыш, больше или равный цене игры, т. е. получим следующую систему неравенств:

ример выполнения первого задания - Инвестирование -  54 . (4.9)

Так как сумма вероятностей равна единице, получим следующее уравнение:

ример выполнения первого задания - Инвестирование -  55 (4.10)

Разделим все члены неравенств системы (1.9) и уравнение (1.10) на n и заменим полученные выражения соответственно на: ример выполнения первого задания - Инвестирование -  56 . Система (4.9) и уравнение (4.10) примет следующий вид:

ример выполнения первого задания - Инвестирование -  57

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

Найти значения ример выполнения первого задания - Инвестирование -  59 при которых целевая функция ример выполнения первого задания - Инвестирование -  60 примет минимальное значение:

ример выполнения первого задания - Инвестирование -  61

при условии:

ример выполнения первого задания - Инвестирование -  62 (4.11)

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

ример выполнения первого задания - Инвестирование -  63 ; ример выполнения первого задания - Инвестирование -  64 ример выполнения первого задания - Инвестирование -  65 .

Проведя аналогичные рассуждения для второго игрока, получим задачу линейного программирования двойственную к задаче (4.11):

Найти значения ример выполнения первого задания - Инвестирование -  66 при которых целевая функция ример выполнения первого задания - Инвестирование -  67 примет максимальное значение:

ример выполнения первого задания - Инвестирование -  68

при условии:

ример выполнения первого задания - Инвестирование -  69 (4.12)

ример выполнения первого задания - Инвестирование -  70 ример выполнения первого задания - Инвестирование -  71 . или ример выполнения первого задания - Инвестирование -  72

Пример решения задачи в Excel для второго игрока приведен на рисунке 4.8. Аналогично находиться решение для первого игрока (рисунок 4.9).

Ответ: Оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, т. е. первому игроку, чтобы выиграть не менее 4, надо чередовать применение первой и третьей стратегии, выбирая каждую с вероятностью 0,5, а вторую стратегию не применять. Второму игроку, чтобы не дать выиграть первому игроку больше, чем 4, необходимо в 4 раза реже применять свою первую чистую стратегию по сравнению со второй и в 5 раз реже по сравнению с третьей.

ример выполнения первого задания - Инвестирование -  73

Рисунок 4.8 – Рабочий лист с результатами решения задачи поиска смешанных стратегий для второго игрока и заполненными полями окна диалога «Параметры поиска решения»

При решении задачи теории игр рекомендуется использовать следующий алгоритм:

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

ример выполнения первого задания - Инвестирование -  74

Рисунок 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 «Информационные системы»

Составитель Г. В. Шагрова

Редактор

ример выполнения первого задания - Инвестирование -  75


Подписано в печать

Формат 60x84 1/16. Усл. п.л. – Уч.-изд. л..

Бумага газетная. Печать офсетная. Заказ Тираж 50 экз.

ФГБОУ УВПО «Северо-Кавказский государственный технический университет»

ример выполнения первого задания - Инвестирование -  76 355029, г. Ставрополь, пр. Кулакова, 2

Типография СевКавГТУ

← Предыдущая страница | Следующая страница →