Методы оптимальных решений

При этом надо перераспределять грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых – свободной.Для свободной клетки, имеющей максимальную положительную величину оценки,, строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках, углы прямые, число вершин четное. Форма цикла может быть разной, например:Но для клетки с положительной оценкой он является единственным.Около свободной клетки цикла ставится знак (+), затем, используя правило чередования знаков, поочередно проставляют знаки (–) и (+). У вершин со знаком (–) выбирают минимальный груз = min[xij()], его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (–). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.Замечание. В некоторых случаях поставка, перераспределяемая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка со знаком «–» содержала нулевую поставку . В этом случае по циклу передается нулевая поставка. В результате свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой – свободной. Если при перераспределении поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной следует считать только одну (любую) из них. Остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой .Переход к следующему опорномурешению. Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу , в данном случае она одна (4, 3). Для этой клетки можно построить следующий цикл: 0*290* (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–).У вершин со знаком (–) выбираем минимальный груз = min[2, 9] =2. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:Получили новое решение задачи (план перевозок):Справа и внизу матрицы проведена проверка: исходные данные запасов и потребностей в результате перераспределения поставок не изменились.Значение целевой функции:Значение целевой функции уменьшилось на 4 ед.Проверка решения Х2 на оптимальность. Расчет потенциалов для занятых клеток: u1 = 0;клетка (1, 1): v1 = c11 – u1 = 10 – 0 = 10;клетка (3, 1): u3 =c31 –v1 =22 – 10 = 12;клетка (3, 4): v4 = c34 – u3 = 27 – 12 = 15;клетка (1, 3): v3 =c13 –u1 =9 – 0 = 9;клетка (4, 3): u4 = c43 – v3 = 11 – 9 =2;клетка (4, 2): v2 =c42 –u4 =12 – 2 = 10;клетка (2, 2): u2 = c22 – v2 = 4 – 10 = -6;Расчет оценок свободных клеток:12 = u1 + v2c12 = 0 + 10 – 17 = –7 < 0,21= u2 + v1c21 = –6 + 10 – 13 = –9 <0,23 = u2 + v3c23 = – 6 + 9 – 24 = –21 < 0,24 = u2 + v4c24 = – 6 + 15 – 26 = –17 < 0,32 = u3 + v2c32 = 12 + 10 – 24 = –2 < 0,33 = u3 + v3c33 = 12 + 9 – 30 = –21 < 0,41 = u4 + v1c44 = 2 + 10 – 25 = –13< 0,44 = u4 + v4c44 = 2 + 15 – 24 = –7 < 0.Результаты расчета представлены в распределительной таблице:bjai1234ui92491811510617(-7)9 7202021513(–9)41524(–21)26(–17)-631922324(-2)30(-9)27161241125(-13)12911224(-7)2vj103915Все оценки свободных клеток отрицательные, следовательно, решение Х2 оптимально.5. Решение транспортной задачи в среде MicrosoftExсelВвод исходных данных (в области C3:F6 – тарифы на перевозку продукции; в столбце G3:G6 – запасы; в ячейках С7, D7, E7, F7 – потребности).В области решения в ячейке G10 введите формулу стоимости перевозок:=СУММПРОИЗВ(C12:F15;C3:F6). Для этого необходимо нажать на значок f(x) на панели инструментов, выбрать математическую функцию СУММПРОИЗВ и ввести два массива C12:F15 и C3:F6. Далее в области C12:F15 проставьте любое первоначальное решение (например, единицы)/В ячейке С16 записывается формула: =СУММ(C12:C14), т.е. сумма значений по столбцу (можно выделить значения столбца и нажать на знак автосуммыΣ на панели инструментов). Аналогично в D16, E16, F16. Автоматически суммируются значения по столбцам.В ячейке G12 записывается формула: =СУММ(C12:F12), т.е. сумма значений по строке (можно выделить значения строки и нажать на знак автосуммы Σ на панели инструментов). Аналогично в G13, G14, G15. Автоматически суммируются значения по строкам:Далее выполняют команду Поиск решения (вкладка Сервисили Данные).Установить целевую ячейку G10, равной минимальному значению.В поле ввода Изменяя ячейки установить C12:F15В поле ввода Ограничения установить C12:F15>=0C16:F16 =C7:F7G12:G15=G3:G6Далее нажимают на кнопку Параметры.Вычисления производятся при нажатии кнопки Выполнитьдва раза. Получим решение задачи:3.2.3. Обоснование ценовой стратегииРешениеОпределим нижнюю цену игры – α. Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.Стратегии "A"Стратегии "B"Минимумы строкB1B2B3B4A12-24-1-2A250510A32-122-1А422711В нашем случае нижняя цена игры равна: α = 0, и для того чтобы гарантировать себе выигрыш не хуже чем 0мы должны придерживаться стратегии A4Определим верхнюю цену игры - βВерхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизуЗатем найдем минимальный элемент дополнительной строки (отмечен *), это и будет верхняя цена игры.Стратегии "A"Стратегии "B"Минимумы строкB1B2B3B4A12-24-1-2A250510A32-122-1А422711*Максимумы столбцов52*72Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называют выбором стратегии игрока.Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.ИгрокиB1B2B3B4a = min(Ai)A12-24-1-2A250510A32-122-1A422711b = max(Bi)5272Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A4.Верхняя цена игры b = min(bj) = 2.Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 1 ≤ y ≤ 2. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij >akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.Стратегия A2 доминирует над стратегией A1 (все элементы строки 2 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p1 = 0.50512-1222271С позиции проигрышей игрока В стратегия B2 доминирует над стратегией B1 (все элементы столбца 2 меньше элементов столбца 1), следовательно, исключаем 1-й столбец матрицы. Вероятность q1 = 0.С позиции проигрышей игрока В стратегия B1 доминирует над стратегией B3 (все элементы столбца 1 меньше элементов столбца 3), следовательно, исключаем 3-й столбец матрицы. Вероятность q3 = 0.01-1221Стратегия A4 доминирует над стратегией A2 (все элементы строки 4 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы. Вероятность p2 = 0.-1221Мы свели игру 4 x 4 к игре 2 x 2.Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.3. Находим решение игры в смешанных стратегиях.Запишем систему уравнений.Для игрока IДля игрока IIРешая эти системы методом Гаусса (решение см. ниже), находим:y = 11/4p1 = 1/4 (вероятность применения 1-ой стратегии).p2 = 3/4 (вероятность применения 2-ой стратегии).Оптимальная смешанная стратегия игрока I: P = (1/4; 3/4)q1 = 1/4 (вероятность применения 1-ой стратегии).q2 = 3/4 (вероятность применения 2-ой стратегии).Оптимальная смешанная стратегия игрока II: Q = (1/4; 3/4)Цена игры:y = 11/4Также решение можно найти по следующим формулам:Ответ: y=11/4P(0, 0, 1/4, 3/4)Q(0, 1/4, 0, 3/4)Решение игры в Excel.Составим математическую модель игры:тематическая модель ПЗЛП:L(X*)=x1+x2+x3→minРешим через Поиск решения.Результат решения совпадает с найденным выше.3.2.4. Обоснование распределения финансовых ресурсов между проектами.На развитие трех предприятий выделено В млн. руб. Известна эффективность капитальных вложений xi в каждое j-епредприятие, заданная таблично значением нелинейной функции fj(xi), где , , n – количество предприятий, m – количество возможных сумм капитальных вложений.Необходимо распределить выделенные средства между предприятиямитаким образом, чтобы получить максимальный суммарный доход.Исходные данные варианта 6:Объем капиталовложений xi (тыс. руб.)Прирост выпуска продукции fj(xi)в зависимости от объема капиталовложений (тыс. руб.)предприятие 1предприятие 2предприятие 30000100305040200507050300709080400100120110500150160150600190190180700210220230Математическая модель задачи.Определить х* = (,, …, , …, ), обеспечивающий максимум целевой функциии удовлетворяющий условиям,Математическая модель задачи варианта 0:при ограничениях:,.Условная оптимизация.Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), определяется с помощью функции Беллмана:,где Сk – количество средств, инвестируемых вk-е предприятие, 0≤ Сk≤ В.На первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств Сn, 0≤ Сn≤ В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т.е. Fn(Сn) = fn(Сn) и хn = Сn.Для упрощения расчетов предполагаем, что распределение средствосуществляется в целых числах xi = {0,100,200,300,400,500, 600, 700} тыс. руб.Решение.I этап. Условная оптимизация.1-й шаг: k = 3. Таблица 1x3C30100200300400500600700F3(C3) 0 0 0 0 10040 4010020050502003008080300400110110400500150150500600180180600700230230700В шапке таблицы отражены варианты значений капиталовложений х3, которые могут быть предоставлены третьему предприятию. В столбце C3 отражены варианты значений капиталовложений, которые могут быть выделены всем трем предприятиям в совокупности.Предположим, что все средства в количестве x3 = 700тыс. руб. отданы третьему предприятию. В этом случае максимальный доходсоставит f3(x3) = 700 тыс. руб., следовательно: F3(C3) = f3(x3) и x3= C3.2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:.Представим в таблице расчет функции Беллмана. Таблица 2x2C20100200300400500600700F2(C2) 0 0+00 0 1000+4050+0501002000+5050+4070+0901003000+8050+5070+4090+01102004000+11050+8070+5090+40120+0130100/3005000+15050+11070+8090+50120+40160+0160100/400/5006000+18050+15070+11090+80120+50160+40190+0200100/5007000+23050+18070+15090+110120+80160+50190+40220+02300/600В шапке таблицы отражены варианты значений капиталовложений х2, которые могут быть предоставлены второму предприятию при условии, что часть средств выделяется третьему предприятию. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции второго предприятия f2(х2) в результате освоения капиталовложений х2; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F3(C2 – х2), т.е. возможный прирост выпуска продукции третьего предприятия, если ему будет выделена оставшаяся часть капиталовложений, определяемая как C2 – х2.Например, рассуждая формально, если при общей величине капиталовложений C2 = 0 второму предприятию выделяется х2 = 0, то прирост продукции составляет f2(0) = 0, а значение функции Беллмана из табл.1 составит: F3(0 – 0) = 0. Поэтому в клетке табл. 2 (0, 0) отражается сумма 0+0.При общей величине капиталовложений C2 = 100 тыс. руб. возможны уже два варианта распределения средств между вторым и третьим предприятием:1) второму предприятию ничего не выделяется, т.е. х2 = 0 и прирост продукции составляет f2(0) = 0. В этом случае значение функции Беллмана из табл. 1 составит F3(100 – 0) = F3(100) = 40 тыс. руб., т.е. вся сумма C2 = 100 тыс. руб. выделена третьему предприятию, поэтому суммарный прирост продукции составит 0+40, отражаемый в клетке (100, 0).2) второму предприятию может быть выделено х2 = 100 тыс. руб., прирост продукции второго предприятия составляет f2(100) = 50 тыс. руб. В этом случае значение функции Беллмана из табл. 1 составит F3(100 – 100) = F3(0) = 0, т.е. вся сумма C2 = 100 тыс. руб. выделена второму предприятию, поэтому суммарный прирост продукции составит 50+0, отражаемый в клетке (100, 100).Рассуждая аналогично, заполняются все строки табл. 2.Максимальная сумма по каждой строке вносится в колонку F2(C2), одновременно в колонку вносят соответствующие максимальным суммам значения х2 из шапки табл. 2.Например, в строке C2 = 100 максимальная сумма 160 неединственная, следовательно, F2(100) = 50, ему соответствует значение х2 = 100, следовательно, =100. В строке C2 = 500 максимальная сумма единственная 50, следовательно, F2(500) = 160, ему соответствуют значения х2 = 100, х2 = 400, х2 = 500, следовательно, =100/400/500.3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:, на ее основе составлена табл. 3.В шапке таблицы отражены варианты значений капиталовложений х1, которые могут быть предоставлены первому предприятию при условии, что часть средств выделяется второму и третьему предприятию. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции первого предприятия f1(х1) в результате освоения капиталовложений х1; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F2(C1–х1), т.е. возможный прирост выпуска продукции второго и третьего предприятий, если им будет выделена оставшаяся часть капиталовложений, определяемая как C1 – х1.Таблица 3x1C10100200300400500600700F1(C1)0 0+00 0 1000+5030+05002000+9030+5050+09003000+11030+9050+5070+01201004000+13030+11050+9070+50100+0140100/2005000+16030+13050+11070+90100+50150+01600/100/200/3006000+20030+16050+13070+110100+90150+50190+0200100/5007000+23030+20050+16070+130100+110150+90190+50210+0240500/600Значение функции Беллмана F1(С1) представляет собой максимально возможный доход со всех предприятий, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие.Значение целевой функции равно максимальному значению функции Беллмана F1(С1) из табл. 3.Следовательно, значение целевой функции равно Fmax(x*) = 240 тыс. руб.II этап. Безусловная оптимизация.Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина Сk = (Сk-1 – хk-1) оптимальным управлением на k-м шаге является то значение хk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk.Определяем компоненты оптимальной стратегии. Для этого значения функций Беллмана и соответствующие им оптимальные значения х вносим в итоговую табл. 4.Таблица 4.C1F3(C3) F2(C2) F1(C1)0 0 0 0 0 0 0 1004010050100500200502009010090030080300110200120100400110400130100/300140100/200500150500160100/400/5001600/100/200/300600180600200100/500200100/5007002307002300/600240500/6001-й шаг. По данным из табл. 4 максимальный доход при распределении 700 тыс. руб. между тремя предприятиями составляет: C1 = 700, F1(700) = 240 тыс. руб.При этом возможны следующие варианты. Первому предприятию нужно выделить:1)= 500тыс. руб.;2) = 600тыс. руб.2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий: 1) С2 = C1 – = 700 – 500 = 200тыс. руб.;2) С2 = C1 – = 700 – 600 = 100тыс. руб.По данным табл.4 находим, что оптимальный вариант распределения между вторым и третьим предприятиями денежных средств размером:1)200 тыс. руб. составляет: F2(200) = 90 тыс. руб. при выделении второму предприятию = 100тыс. руб.;2) 100 тыс. руб. составляет: F2(100) = 50 тыс. руб. при выделении второму предприятию = 100тыс. руб.3-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятия: 1) С3 = C2 – = 200 – 100 = 100тыс. руб.;2) С3 = C2 – = 200 – 200 = 0.По данным табл. 4 находим: 1) F3(100) = 40 и = 100 тыс. руб.;2) F3(0) = 0 и = 0.Таким образом, возможны два альтернативных варианта оптимального плана инвестирования предприятий: 1) х* = (500, 100, 100), который обеспечит максимальный доход, равный F(700) = f1(500) + f2(100) + f3(100) = 150 + 50 + 40 = 240 тыс. руб.;2) х** = (600, 100, 0), который обеспечит максимальный доход, равный F(700) = f1(600) + f2(100) + f3(0) = 190 + 50 + 0 = 240 тыс. руб.ЗаключениеПри выполнение курсовой работы по методам оптимальных решений на тему «Обоснование принятия оптимальных решений для предприятия оптовой торговли продовольственными товарами» была достигнута цель: овладение математическими методами решения экономических задач. Были решены следующие задачи: Построены экономико-математические модели оптимального решения задачи для предприятия оптовой торговли продовольственными товарами. Освоен симплекс-метод и двойственный симплекс метод.Освоено решение задачи ЛП при помощи надстройки Поиск решения.2. Освоен метод потенциалов решения транспортной задачи. 3. Освоена методика решения антагонистических игр. Получено оптимальное решение задачи.4. При решении задачи динамического программирования найдено оптимальное распределение капиталовложений.В ходе выполнения курсовой работы по дисциплине «Методы оптимальных решений» овладели математическими методами решения экономических задач, научились строить экономико-математические модели, освоили простой симплекс-метод табличного решения задачи линейного программирования, освоили одновременный двойственный симплекс-метод решения задачи линейного программирования, метод потенциалов решения транспортной задачи, методику решения антагонистических игр, методику решения задачи динамического программирования.Список использованных источников1. Васин А. А. Исследование операций : учеб. пособие для вузов / А.А. Васин, П.С. Краснощеков, В. В. Морозов.— М. : Академия, 2008.— 464 с.2. Вентцель Е.С. Исследование операций : задачи, принципы, методология : учеб. пособие / Е.С. Вентцель.— 5-е изд., стер. — М. :Высш. шк., 2010 .— 191 с. 3. Горбунова Р.И. Экономико-математические методы и модели : учеб. пособие / Р.И. Горбунова [и др.]; под ред. С.И. Макарова.— М. : КНОРУС, 2007.— 232с.4. Исследование операций в экономике : учеб. пособие для вузов / Н.Ш. Кремер [и др.] ; под ред. Н. Ш. Кремера.— 2-е изд., перераб. и доп.— М. : Юрайт, 2010.— 431 с.5. Солодовников А.С. Математика в экономике : учебник для вузов. Ч.1 / А.С. Солодовников [и др.] .— 2-е изд., перераб. и доп. — М. : Финансы и статистика, 2007 .— 384с.