Обоснование принятия оптимальных решений для хлебозавода

Обоснование принятия оптимальных решений для хлебозавода

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

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

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

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

Задачи выполнения типового расчета:

— научиться строить экономико-математические модели;

— освоить симплекс-метод табличного решения задачи линейного программирования;

— освоить двойственный симплекс-метод решения задачи линейного программирования;

— освоить метод потенциалов решения транспортной задачи;

— освоить методику решения антагонистических игр;

— освоить методику решения задачи динамического программирования.

1. Особенности обоснования принятия оптимальных решений для хлебозавода

Хлебозавод — одно из старейших предприятий хлебопекарной отрасли России. Он ведет свою историю с октября 1934 года, когда с конвейера сошла первая партия продукции.

Уже тогда, почти век назад, в эпоху индустриализации страны хлебозавод был задуман как передовое предприятие пищевой промышленности по производству хлеба и сухарных изделий. На нем впервые были установлены конвейерные печи, в 6 раз, превосходящие по мощности жаровые печи на других хлебозаводах. Вплоть до Великой отечественной войны Хлебозавод непрерывно повышал свои производственные мощности и объемы выпускаемой продукции, обеспечивая растущее население города хлебом отличного качества.

Затем завод стал круглосуточно работать на нужды фронта. В 1942 г. каждые 24 часа с его конвейеров сходила одна тонна сухарей для воинских частей. 24 августа 1942 года во время массированной бомбардировки немецкой авиации завод был частично разрушен. Но уже 1 апреля 1943 г. хлебопекарная база была восстановлена и заработала с еще большей мощностью, выпуская 6 тонн хлеба в сутки.

Хлеб всегда был важным продовольственным запасом страны, а в военные годы его бесперебойные поставки имели еще и стратегическое значение. Обеспечивая армейские части хлебным пайком.

Дальнейшее развитие и совершенствование производственной базы завода шло рука об руку с техническим прогрессом. На хлебозавод внедрялись новые технологии производства, и оставалось неизменным качество хлеба — эталонное, ГОСТовское.

Хлебозавод — предприятие, где все технологические процессы изготовления хлеба полностью автоматизированы. Производство хлеба на этих заводах ведётся на автоматических линиях, рассчитанных на выпуск определённых сортов хлебных изделий.

Мука доставляется в цистернах муковозов, а дрожжи, соль, сахар, жир и т. д. — специализированными автомашинами. На заводе мука хранится в бункерах; её транспортирование осуществляется пневматическим способом. Остальное сырьё хранится в жидком виде в ёмкостях и транспортируется по трубопроводам. Дозирование муки производится дозаторами непрерывного действия, а жидких компонентов — автоматическими дозировочными станциями. Тесто приготовляется с помощью агрегатов, включающих месильные машины непрерывного действия и аппараты для брожения. Затем тесто разделяется на куски и формуется на поточных линиях, состоящих из тестоделительных, тестокруглительных, тестозакаточных машин, а также конвейерных установок для расстойки (выдержки) теста в кусках. Хлеб выпекается в автоматизированных конвейерных печах. Режим работы тестоприготовительных агрегатов, тесторазделочных линий и печей автоматически контролируется и регулируется в соответствии с качественными показателями поступающего сырья, изменением условий работы предприятия и т. д. Выпеченный хлеб подаётся на автоматизированный склад (включает хлебохранилище и экспедицию), где хранится в контейнерах до отправки в торговую сеть.

В состав хлебозавода входят 2 производства: хлебобулочное и кондитерское. ОАО «Пышка» — хлебозавод. Он находится в Туле и распространяет свою продукцию по территории, данной области.

Основная задача хлебозавода: обеспечение населения хлебобулочной и кондитерской продукцией.

Принципы и цели:

— постоянное обновление и совершенствование ассортимента продукции;

— использование только натурального и высококачественного сырья.

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

Хлебозавод выпускает следующие изделия:

П1 — Хлеб Это пищевой продукт, получаемый путём выпечки, паровой обработки или жарки теста, состоящего, как минимум, из муки и воды. В большинстве случаев добавляется соль, а также используется разрыхлитель — дрожжи.

П2 — Печенье Это небольшое кондитерское изделие, выпеченное из теста. К тесту для печенья добавляют различные зёрна; печенье формуют в виде кружков, квадратов, звёздочек, трубочек; иногда печенье делают с начинкой (шоколадом, изюмом, сгущённым молоком, кремом) или помещают начинку между двумя печеньями.

П3 — Слойка Это слоёный пирожок, изделие из слоёного теста.

Ресурсы, использованные для производства изделий:

Р1 — Соль Р2 -Мука Она изготавливается из зёрен, размельчённых до порошкообразного состояния. Именно от муки зависит основная структура выпеченного хлеба. Наиболее распространена мука ржаная, ячменная, кукурузная и другие, но для приготовления хлеба чаще всего используется пшеничная мука, размолотая по специальной технологии Р3 — Вода или какая-либо другая жидкость используется для формирования из муки теста.

2. Задача оптимального распределения ресурсов

Организация имеет возможность выпускать три вида изделий П₁, П₂, П₃, При их изготовлении используется три вида ресурсов Р₁, Р₂, Р₃. Размеры допустимых затрат ресурсов ограничены соответственно величинами b₁, b₂, b₃. Расход ресурса i-го вида (i=1,2,…, m) на единицу изделия j-го вида (j=1,2,…, n) составляет a_ijден. ед. Цена единицы продукции j-го вида равна с_j. Требуется найти оптимальный план выпуска изделий, который обеспечивал бы организации максимальный доход.

Построим экономико-математическую модель задачи. С целью ее построения следует ввести переменные и представить исходные данные в табличном виде (Таблица 1).

Таблица 1- Переменные для решения задачи оптимального распределения ресурсов

Введем переменные: х₁ — объем производства продукции первого вида; х₂ — объем производства продукции второго вида; х₃ — объем производства продукции третьего вида.

Представим исходные данные варианта 44 в виде таблицы 2.

Таблица 2 — Исходные данные для решения задачи оптимального распределения ресурсов

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

где n — количество видов продукции.

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

где m — количество ресурсов.

Также должно выполняться условие неотрицательности переменных:

.

Таким образом, экономико-математическая модель прямой задачи линейного программирования (ПЗЛП) варианта 44 имеет вид:

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

Данная ПЗЛП имеет стандартную форму записи, поскольку в задаче на максимум все функциональные (ресурсные) ограничения имеют знаки «меньше или равно».

Для построения двойственной задачи линейного программирования (ДЗЛП) следует ввести двойственные переменные: у₁ — скрытая цена первого ресурса; у₂ — скрытая цена второго ресурса; у₃ — скрытая цена третьего ресурса.

Целевая функция ДЗЛП представляет собой совокупные затраты второго предприятия на приобретение всех ресурсов первого предприятия, при этом второе предприятие стремиться, чтобы его затраты на приобретение ресурсов у первого предприятия были минимальными:

.

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

.

Должно выполняться условие неотрицательности переменных:

.

Также для построения ДЗЛП можно руководствоваться следующими правилами.

1. В первой задаче определяется максимум линейной целевой функции, во второй — минимум.

2. Коэффициенты при переменных в целевой функции первой задачи являются правыми частями в системе ограничений во второй задаче.

3. Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «меньше или равно», а в задаче минимизации все неравенства вида «больше или равно».

4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу. Для варианта 0 матрица коэффициентов при переменных в системе ограничений ПЗЛП имеет вид:

Тогда транспонированная матрица, отражающая коэффициенты при переменных в системе ограничений ДЗЛП, имеет вид:

.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условие неотрицательности переменных имеются в обеих задачах.

Таким образом, экономико-математическая модель ДЗЛП варианта 0 имеет вид:

при ограничениях Данная ДЗЛП имеет стандартную форму записи, поскольку в задаче на минимум все функциональные (затратные) ограничения имеют знаки «больше или равно». Для решения задачи линейного программирования необходимо перейти к ее канонической форме записи, то есть перейти в системе ограничений от функциональных неравенств к равенствам посредством включения дополнительных переменных. Для ПЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме записи ПЗЛП варианта 0 следует добавить дополнительные переменные х₄, х₅, х₆, в соответствующие неравенства со знаком «+», поскольку они отражают возможный остаток неиспользованных ресурсов:

Для ДЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме записи ДЗЛП варианта 0 следует добавить дополнительные переменные y₄, y₅, y₆, в соответствующие неравенства со знаком ««, поскольку они отражают возможное превышение затрат на приобретение ресурсов над ценой реализации продукции (возможный убыток от производства продукции):

Во взаимодвойственных задачах линейного программирования первоначальным переменным ПЗЛП соответствуют дополнительные переменные ДЗЛП и аналогично первоначальным переменным ДЗЛП соответствуют дополнительные переменные ПЗЛП.

Установим соответствие переменных прямой и двойственной задачи для варианта 0:

Таблица Решение задачи оптимального распределения ресурсов возможно двумя способами:

А. Одновременное решение ПЗЛП и ДЗЛП с помощью симплекс-таблиц.

Б. Двойственный симплекс-метод.

Рассмотрим оба метода.

Решаем ПЗЛП.

Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки _j (индексная строка), заполняем по данным системы ограничений и целевой функции канонической формы записи ПЗЛП.

В первую строку с_jвносятся значения коэффициентов при переменных из целевой функции. В столбец базисных переменных вносим дополнительные переменные х_j.

В столбец с_i вносят значения коэффициентов при переменных из целевой функции, которые вошли в базис.

Рабочее поле таблицы (столбцы под переменными х_jзаполняют коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП. Отсутствие той или иной переменной в равенстве означает, что ей соответствует коэффициент, равный нулю.

В столбец b_i вносят свободные члены системы равенств.

Индексная строка (_j) для переменных находится по формуле:

где h_ij — соответствующий элемент, стоящий на пересечении i-й строки и j-го столбца рабочего поля симплекс таблицы.

Индексная строка (_j) для свободного члена находится по формуле

где l_i — соответствующий элемент, из столбца b_i.

В рассматриваемом варианте в первую строку с_jвносим значения коэффициентов при переменных из целевой функции 3, 4 и 1, остальные значения равны нулю. В столбец базисных переменных вносим дополнительные переменные х₄, х₅, х₆. В рассматриваемом случае базисные переменные не входят в целевую функцию, поэтому им соответствуют нулевые значения в столбце с_i.

Рабочее поле таблицы (столбцы под переменными х₁, х₂, х₃, х₄, х₅, х₆) заполняем коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП.

Поскольку, в первом равенстве отсутствуют переменные х₅ и х₆, поэтому в первой рабочей строке симплекс-таблицы этим переменным соответствует коэффициент «0».

Таблица 3 — Шаг симплекс-метода

Заполняем индексную строку:

₁ = 03 + 02 + 03 — 3 = -3;

₂ = 01 + 04 + 03 — 4 = -4;

₃ = 02 + 01 + 02 — 1 = -1;

₄ = 0; ₅ = 0; ₆ = 0;

₇= 04 + 010 + 03 = 0.

Первое опорное решение имеет вид: = (0, 0, 0, 3, 10, 4), = 0. (компоненты опорного решения выписывают для базисных переменных из столбца свободных членов b_i; переменные, не входящие в базис, имеют значение 0). В рассматриваемом случае переменные х₁, х₂, х₃. не входят в базис, поэтому их компоненты в опорном решении равны нулю, базисные переменные имеют значения х₄= 3, х₅ = 10, х₆ = 4. Значение целевой функции берут из последней строки столбца. На данном шаге симплекс-метода = 0.

Следует проверить первое опорное решение на оптимальность.

Возможны следующие случаи решения задачи на максимум:

— если все оценки _j 0, то найденное решение оптимальное;

— если хотя бы одна оценка _j 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f (X), т. е. целевая функция не ограничена в области допустимых решений;

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

— если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

В рассматриваемом случае первое опорное решение не оптимальное, поскольку имеются три отрицательные оценки ₁ = - 3, ₂ = - 4, ₃ = - 1.

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

Пусть одна оценка _k 0 или наибольшая по абсолютной величине _k 0, тогда k-й столбец принимают за ключевой (разрешающий).

Такой переменной является переменная из столбца с наибольшей по абсолютной величине оценкой ₂ = 4, т. е. переменная х₂.

Таблица 4 — Шаг симплекс-метода

Теперь следует определить, какую переменную нужно вывести из базиса.

За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам ключевогоk-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.

В столбце оценочных отношений min{b_i/h_ij} отражены отношения свободных членов к элементам из разрешающего столбца, минимальным является отношение 1, соответствующее строке переменной х₄, следовательно, эта строка — разрешающая, а переменная х₄ выводится из базисных переменных:

Таблица 5 — Шаг симплекс-метода

На пересечении ключевой строки и ключевого столбца находится ключевой элемент «3».

Переход ко второму шагу симплекс-метода.

В столбец базисных переменных на место выведенной из базисных вносится новая базисная переменная. При этом в столбец с_i вносится соответствующее значение коэффициента при переменной из целевой функции.

Ключевая строка переписывается, при этом все ее элементы делят на ключевой элемент. Заполняют столбцы для базисных переменных: на пересечении строки и столбца, в которых находится одна и та же переменная, ставят «1», в остальных клетках столбца нули.

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

.

Оценки _j можно считать по приведенным ранее формулам или по правилу «прямоугольника».

Заполним симплекс-таблицу второго шага для варианта 44. Вместо переменной х₄ вводим в базис переменную х₂, в целевой функции ей соответствует коэффициент 4, который вносится в соответствующую клетку столбца с_i. В строке, соответствующей переменной х₂ переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «3»:

Таблица 6 — Шаг симплекс-метода

Таблица 7 — Шаг симплекс-метода

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

= ;

= ;

= ;

= ;

= ;

= ;

= ;

= .

Таблица 8 — Шаг симплекс-метода

Находим оценки переменных:

₁ = 0(2) + 0(-2) + 4(1) — 3 = 1;

₃ = 0(4/3) + 0(-5/3) + 4(2/3) — 1 = 5/3;

₄ = 0(-1/3) + 0(-4/3) + 4(1/3) — 0 =4/3;

₇= 0(3) + 0(6) + 4(1) = 4.

Таблица 9 — Шаг симплекс-метода

Поскольку все оценки положительные _j, то полученное опорное решение является оптимальным: = (0, 1, 0, 0, 6, 3), а максимальное значение целевой функции равно = 4.

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

Таблица 10 — Шаг симплекс-метода

Таким образом, = (4/3, 0, 0, 1, 0, 5/3), поскольку y₁x₄, y₂x₅, y₃x₆, y₄x₁, y₅x₂, y₆x₃. Значение целевой функции = 4.

Экономический смысл переменных, участвующих в решении отражен в таблице 11.

Таблица 11 — Экономический смысл переменных

Экономический смысл переменных:

x₁^*, x₂^*, x₃^*-основные переменные — оптимальный план производства;

x₄^*, x₅, x₆^*— дополнительные переменные — остатки ресурсов;

y₁, y₂, y₃-основные переменные — скрытые цены;

y₄, y₅, y₆-дополнительные переменны — превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции).

Анализ решения ПЗЛП Подставим оптимальные значения переменных x^*в исходную систему ограничений ПЗЛП:

1) 3х₁ + 3х₂ + 2х₃ 3

30+ 31 + 20 = 3

3=3, следовательно, х₄ = 0, ресурс Р₁ используется полностью;

2) 2х₁ + 4х₂ + х₃ 10

20+ 41 + 10 = 4

4 < 10, следовательно, х₅ = 6, ресурс Р₂ используется не полностью;

3) 3х₁ + х₂ + 2х₃ 4

30 + 11 + 20 = 1

1 < 4, следовательно, х₄ = 3, ресурс Р₃ используется не полностью.

Анализ решения ДЗЛП Подставим оптимальные значения переменных у^*в исходную систему ограничений ПЗЛП:

1) 3у₁ + 2у₂ + 3у₃ 3

3(4/3) + 20 + 30 = 4

4 3, на 1, следовательно, у₄ = 1, убытки от производства первого вида продукции П₁, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 1 ден. ед. с каждого изделия первого вида;

2) 3у₁ + 4у₂ + у₃ 4

3(4/3) + 40 + 10 = 4

4 = 4, следовательно, у₅ = 0, убытки от производства второго вида продукции П₂, которая вошла в оптимальный план производства отсутствуют;

3) 2у₁ + у₂ + 2у₃ 1

2(4/3) + 10 + 20 = 8/3

8/3 1 на 5/3, следовательно, у₆ = 5/3, убытки от производства третьего вида продукции П₃, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 5/3 ден. ед. с каждого изделия третьего вида.

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

В рассматриваемом случае дефицитным является ресурс Р₁.

Для исследования границ изменения первого вида ресурса Р₁ из последней симплекс-таблицы составляют систему неравенств для базисных переменных ПЗЛП, используя элементы из столбца свободных членов b_i и столбца, соответствующего переменной у₁. Коэффициенты из столбца «у₁» умножают на искомое изменение b₁запаса ресурса Р₁:

.

Учитывая, что b₁ = 3, допустимый интервал изменения границ первого вида ресурса составит или .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₁ = 7,48:

Рисунок 1 — Прямая задача линейного программирования Структура ПЗЛП не изменилась Рисунок 2 — Двойственная задача линейного программирования Структура ДЗЛП не изменилась.

Зададим b₁ = 0,02:

Рисунок 3 — Прямая задача линейного программирования Структура решения ПЗЛП не изменилась Рисунок 4 — Двойственная задача линейного программирования Структура ДЗЛП не изменилась.

Зададим b₁ = 7,51:

Рисунок 5 — Прямая задача линейного программирования Получили новую структуру оптимального плана прямой задачи: (х₁=0,01; х₂=2,5; x₃=0)

Рисунок 6 — Двойственная задача линейного программирования Получили новую структуру оптимального плана ДЗЛП.

Можно сделать вывод о правильности установленных границ изменения ресурса Р₁: 0? b₂? 15/2.

Значение остатка недефицитных ресурсов определяется значением соответствующей дополнительной переменной.

В рассматриваемом случае не дефицитными являются ресурсы Р₂ и Р₃. Оптимальный план производства не изменится при .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₂ = 3,98:

Рисунок 7 — Двойственная задача линейного программирования Получили новый оптимальный план решения ДЗЛП.

Зададим b₂ = 4,02:

Рисунок 8 — Прямая задача линейного программирования Оптимальный план решения ПЗЛП не изменился Рисунок 9 — Двойственная задача линейного программирования Оптимальный план решения ДЗЛП не изменился.

Можно сделать вывод о правильности установления границы изменения ресурса Р₂: b₂? 4.

Оптимальный план производства для не дефицитного ресурса Р₃ не изменится при .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₃ = 0,98:

Рисунок 10 — Двойственная задача линейного программирования Получили новый оптимальный план решения ДЗЛП.

Зададим b₂ = 1,02:

Рисунок 11 — Прямая задача линейного программирования Оптимальный план решения ПЗЛП не изменился.

Рисунок 12 — Двойственная задача линейного программирования Оптимальный план решения ДЗЛП не изменился.

Можно сделать вывод о правильности установления границы изменения ресурса Р₃: b₃? 1.

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

В план производства вошел второй вид продукции П₂.

Для второго вида продукции П₂, которая попала в план производства, из последней симплекс-таблицы составляют систему неравенств для базисных переменных ДЗЛП (они соответствуют свободным переменным ПЗЛП), используя элементы из строки _j и строки, соответствующей переменной х₂. Коэффициенты из строки «х₂» умножают на искомое изменение с₁цены продукции П₂

.

Учитывая цену второго вида продукции с₂ = 4, интервал устойчивости изменения цен составит или .

Проверим границы с помощью вычислительного эксперимента:

Зададим c₂ = 2,98:

Рисунок 13 — Прямая задача линейного программирования Получили новый оптимальный план решения ПЗЛП.

Зададим c₂ = 3,02:

Рисунок 14 — Прямая задача линейного программирования Структура оптимального плана решения ПЗЛП не изменилась.

Рисунок 15 — Двойственная задача линейного программирования Структура решения ДЗЛП не изменилась.

Можно сделать вывод о правильности определения границы изменения цены с₂: с₂ 3.

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

Определим величины? b_s ресурса Р_s, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства? b_r единиц ресурса Р_r.

В рассматриваемом случае: r = 1; ?b_r = 0,2; s = 2.

Для взаимозаменяемых ресурсов (коэффициент взаимозаменяемости >0, но отличен от бесконечности) количество ресурса? b_iвида i, необходимое для замены выбывающего количества? b_kресурса k, определяется по формуле:

.

Таким образом,. Следовательно, замена первого ресурса невозможна.

Оценим целесообразность приобретения? b_k единиц ресурса Р_k по цене с_k за единицу. Для оценки целесообразности приобретения дополнительного количества ресурса? b_iвида i по цене с_k необходимо сравнить предлагаемую цену с рассчитанной ранее теневой ценой этого ресурса. Приобретение дополнительного количества ресурса целесообразно, если выполняется условие непревышения новой цены над теневой ценой с_k.

В противном случае приобретение дополнительного количества ресурса нецелесообразно.

В рассматриваемом случае: ?b_k = 0,2; k = 3, c_k = 15.

Поскольку < 15, то приобретение дополнительного количества ресурса не целесообразно.

Оценим целесообразность выпуска нового изделия П₄, на единицу которого ресурсы Р₁, Р₂, Р₃ расходуются в количествах a₁₄, a₂₄, a₃₄ единиц, а цена единицы изделия составляет с₄ денежных единиц. Включение дополнительного вида продукции n+1 в план производства целесообразно, если соотношение дополнительных затрат и цены реализации дополнительного вида продукции удовлетворяет следующему условию

.

Расчет затрат осуществим по формуле ден. ед.

Учитывая, что затраты на ресурсы для производства продукции третьего вида меньше цены реализации с₄ = 35 ден. ед., то включение ее в план производства целесообразно.

Решим прямую и двойственную задачу линейного программирования в среде MicrosoftExсel. Решение задач линейного программирования с помощью программы MicrosoftExcel осуществляется через меню Сервис и вкладку Поиск решения. Если данная вкладка не установлена, то ее установка осуществляется следующими действиями:

1. Войти в меню Сервис.

2. Выбрать команду Надстройки.

3. В появившемся диалоговом окне Надстройки установить флажок напротив строки Поиск решения и нажать кнопку ОК.

После произведенных действий в меню Сервис появится команда Поиск решения.

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

Выбираем ячейку для введения целевой функции (например, ячейку А1). При записи целевой функции в ячейку А1 вместо значений переменной х_i подставляют названия пустых ячеек, в которых хотим получить искомые значения х₁, х₂, х₃, например, С1, С2, С3. Тогда запись целевой функции в ячейке А1 будет иметь вид = 3*С1+4*С2+С3. После введения целевой функции в ячейку А1 нажимаем клавишу «Enter», в ячейке А1 отобразится 0.

Условия ограничений вписываем в ячейки столбца В. В выбранные ячейки записываются только левые части неравенств в следующем виде:

Ячейка В1: =3*С1+3*С2+2*С3 «Enter»

Ячейка В2: =2*С1+4*С2+С3 «Enter»

Ячейка В3: =3*С1+С2+2*С3 «Enter»

Ячейка В4: =С1 «Enter»

Ячейка В5: =С2 «Enter»

Ячейка В6: =С3 «Enter»

Через меню Сервис/Поиск решения открыть окно поиска решения:

Рисунок 16 — Решение задачи в среде MicrosoftExсel

В поле ввода Установить целевую ячейку вводим ссылку на ячейку А1.

В поле ввода Изменяя ячейки укажем ссылки на ячейки С1: С3.

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

1.Щелкнуть левой кнопкой мыши в поле ввода Изменяя ячейки.

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

В поле ввода Ограничения введем ограничения, соответствующие ячейкам В1, В2, В3. Ввод значений осуществляется в следующем порядке:

1.Нажать кнопку Добавить. Появится диалоговое окно Добавление ограничения.

2. Для каждого логического выражения, находящихся в ячейках В1, В2, В3 вводим свое условие и свое ограничение, последовательно нажимая кнопку Добавить. По окончании нажать кнопку ОК.

Рисунок 17 — Решение задачи в среде MicrosoftExсel

3. Должен появиться следующий результат:

Рисунок 18 — Результат решения задачи в среде MicrosoftExсel

Для поиска максимального значения устанавливаем флажок.

Для осуществления вычислений нажмем кнопку Выполнить. Откроется окно диалога Результаты поиска решения. В окне Тип отчета выберем строку Результаты и нажмем кнопку ОК. Получим следующие результаты:

В ячейке А1отражено максимально возможное значение функции при заданных условиях 4.

В столбце В отражены значения логических выражений, удовлетворяющих исходным ограничениям.

3х₁ + 3х₂ +2х₃ = 3

2х₁ + 4х₂ + х₃ = 4

3х₁ + х₂ + 2х₃ = 1

В столбце С отражены значения переменных, при которых значение функции принимает максимальную величину:

х₁ = 0; х₂ = 1; х₃ = 0.

На листе «Отчет по результатам» появится следующая информация, отражающая результаты расчета:

Рисунок 19 — Результат решения задачи в среде MicrosoftExсel

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

Рисунок 20 — Результат решения задачи в среде MicrosoftExсel

симплекс-метод

1. Выражение базисных переменных ПЗЛП и ДЗЛП через свободные.

Выразим базисные переменные ПЗЛП и ДЗЛП через свободные:

2.Определение исходного решения прямой и двойственной задач и проверка его на оптимальность.

Для этого заполняют симплекс-таблицу двойственного симплекс-метода. Таблица имеет два входа: по переменным прямой задачи x_jи по переменным двойственной задачи y_i. Базисные переменные ПЗЛП записывают в столбце x_баз, а свободные переменные в строке x_св со знаком ««. Базисные переменные ДЗЛП записывают в строке у_баз, а свободные переменные в столбце у_св.

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

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

Симплексная таблица двойственного симплекс-метода для варианта 40 имеет следующий вид:

Таблица 12 — Шаг двойственного симплекс-метода Решение ПЗЛП выписывается по строкам, значения базисных переменных берутся из столбца b_i, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, 3, 10, 4), = 0.

Решение ДЗЛП выписывается по столбцам, значения базисных переменных берутся из строки c_j, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, -3, -4, -1), = 0.

Данное решение не является оптимальным, поскольку решение не допустимое (не выполнено условие неотрицательности переменных), ему соответствуют отрицательные элементы в строке. Поэтому следует провести замену переменных в базисе.

Для выбора разрешающей строки находят отрицательный элемент в строке .В столбце над этим найденным элементом выбирают любой положительный элемент, эта строка — разрешающая.

Если в столбце над найденным элементом нет положительных элементов, то ПЗЛП не имеет смысла (целевая функция не ограничена в области допустимых решений), а ДЗЛП не имеет решения.

В рассматриваемом примере в строке три отрицательных элемента.

Таблица 13 — Шаг двойственного симплекс-метода Можно выбрать любой из них, поэтому выбираем «1», а над ним выбираем элемент из второй строки «2». Следовательно, первая строка — разрешающая (выделена жирным шрифтом).

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

Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

В рассматриваемом примере максимальным среди отношений элементов из строкии элементов разрешающей строки является отношение в третьем столбце. В качестве разрешающего выберем третий столбец (выделен жирным шрифтом).

Таблица 14 — Шаг двойственного симплекс-метода Разрешающим элементом является элемент «2», который стоит на пересечении первой строки и третьего столбца.

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

Заполнение нижних частей клеток для разрешающей строки и разрешающего столбца варианта 44:

Таблица 15 — Шаг двойственного симплекс-метода Остальные элементы таблицы в нижних частях клеток находят по правилу прямоугольника: для искомого элемента из нижней части клетки элемент из верхней части этой же клетки умножают на разрешающий элемент и из этого произведения вычитают произведение элементов, расположенных на противоположной диагонали прямоугольника, образуемого искомым и разрешающим элементами (все элементы из верхних клеток).

Заполнение нижних частей для остальных клеток варианта 44:

на пересечении второй строки и первого столбца:

Рис. 22 31 = 1;

клетка на пересечении третьей строки и первого столбца:

Рис. 23 23 = 0;

клетка на пересечении четвертой строки и первого столбца:

Рис. 32 3(1) = 3;

клетка на пересечении второй строки и второго столбца:

Рис. 42 31 = 5;

клетка на пересечении третьей строки и второго столбца:

Рис. 21 32 = -4;

клетка на пересечении четвертой строки и второго столбца:

42 (1)3 = -5;

клетка на пересечении второй строки и четвертого столбца:

Рис. 10 13 = 17;

клетка на пересечении третьей строки и четвертого столбца:

Рис. 4 23 = 2;

клетка на пересечении четвертой строки и четвертого столбца:

Рис. 02 (1)3= 3.

Таким образом, получаем следующую таблицу:

Таблица 16 — Шаг двойственного симплекс-метода Изменяют базисные переменные: меняют местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и записывают на соответствующие места в верхние клетки новой симплекс-таблицы.

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

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

Если в строке есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода: Столбец с нулевым элементом в строке выбирается за разрешающий. Находят неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца. Из полученных отношений выбирают минимальное неотрицательное отношение — это разрешающая строка, разрешающий элемент найден. Затем выполняют еще один шаг симплекс-метода.

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

Переходим к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₃, у₆, соответствующих разрешающему столбцу, а в третий столбец вводится пара переменных х₄, у₁, соответствующая разрешающей строке. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «2»:

Таблица 17 — Шаг двойственного симплекс-метода Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: = (0, 0, 3/2, 0, 17/2, 1), = 3/2, решение ДЗЛП выписывается по столбцам: = (½, 0, 0, 3/2, -5/2, 0), = 3/2. Данное решение также не оптимальное, поскольку в строке еще остались отрицательные элементы. Необходимо продолжить поиск оптимального решения.

В строке выбираем отрицательный элемент «3/2». Над ним выбираем положительный, предпочтительнее «3/2», следовательно, первая строка — разрешающая (выделена жирным шрифтом):

Таблица 18 — Шаг двойственного симплекс-метода Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки

. Разрешающий столбец — первый, поскольку максимальное отношение соответствует ему.

Разрешающий элемент «3/2» находится на пересечении разрешающей строки и разрешающего столбца.

Заполнение нижних частей клеток осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:

Таблица 19 — Шаг двойственного симплекс-метода Переходим к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₁, у₄, соответствующих разрешающему столбцу, а в первый столбец вводится пара переменных х₃, у₆, соответствующая разрешающей строке. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «3/2»:

Таблица 20 — Шаг двойственного симплекс-метода Решение ПЗЛП на третьем шаге двойственного симплекс-метода также выписывается по строкам: = (1, 0, 0, 0, 8, 1), = 3, решение ДЗЛП выписывается по столбцам: = (1, 0, 0, 0, -1, 1), = 3. Данное решение также не оптимальное, поскольку в строке еще остался отрицательный элемент. Необходимо продолжить поиск оптимального решения.

В строке выбираем отрицательный элемент «1». Над ним выбираем положительный, предпочтительнее «1», следовательно, первая строка — разрешающая (выделена жирным шрифтом):

Таблица 21 — Шаг двойственного симплекс-метода Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки. Разрешающий столбец — второй, поскольку максимальное отношение соответствует ему.

Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.

Заполнение нижних частей клеток осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:

Таблица 22 — Шаг двойственного симплекс-метода Перейдем к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₂, у₅, соответствующих разрешающему столбцу, а во второй столбец вводится пара переменных х₁, у₄, соответствующая разрешающей строке. Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице.

Таблица 23 — Шаг двойственного симплекс-метода Оптимальное решение ПЗЛП: = (0, 1, 0, 0, 6, 3), = 4, оптимальное решение ДЗЛП: = (4/3, 0, 0, 1, 0,5/3), = 4.

Данное решение аналогично решению, полученному в соответствии с методом одновременного решения пары взаимодвойственных задач для ПЗЛП и совпадает с решением ДЗЛП в отношении значения целевой функции.

3. Метод потенциалов решения транспортной задачи

Начальное решение транспортной задачи

Имеется 4 оптовых склада и 4 магазина.

A₁, A₂, A₃, A₄ — склады.

a₁ = 19, a₂ = 19, a₃ = 19, a₄ = 19 — соответственно, запасы на складах.

B₁, B₂, B₃, B₄ — магазины.

b₁ = 15, b₂ = 15, b₃ = 23, b₄ = 23 — соответственно, потребности магазинов.

Найдем исходное опорное решение по методу минимальной стоимости. Для этого заполним распределительную таблицу:

Таблица 24 — Транспортная задача Таблица 25 — Транспортная задача Таким образом, все поставки распределены, получено начальное решение транспортной задачи:

Рис.

f_o(x^o) = 12· 19 + 16· 15 + 15· 4 + 16· 19 + 10· 15 + 10· 4 = 1022

Количество ненулевых элементов 6 < 7, решение вырожденное. Введем значимый ноль (O).

Решение транспортной задачи методом потенциалов Таблица 26 — Транспортная задача Вычисляем оценки свободных клеток:

₁₁ = c₁₁ — u₁ -v₁ = 21- 0 — 13= 8 > 0,

₁₂ = c₁₂— u₁ — v₂ = 17 — 0 -11 = 6 >0,

₁₄ = c₁₄ — u₁ — v₄ = 24 — 0 — 11= 13 >0,

₂₂ = c₂₂ — u₂ — v₂ = 19 — 3 — 11 = 5 > 0,

₂₄ = c₂₄ — u₂ — v₄ = 19 — 3 -11 = 5 > 0,

₃₁ = c₃₁ — u₃ — v₁ = 17 — 5 — 13= - 1< 0,

₃₂ = c₃₂ — u₃ — v₂ = 15 — 5 — 11= -1< 0,

₃₃ = c₃₃ — u₃ — v₃ = 24 — 5- 12 = 7 >0,

₄₁ = c₄₁ — u₄ — v₁ = 13+1−13 = 1 >0.

В распределительной таблице оценки клеток проставлены в нижнем левом углу в скобках:

Таблица 27 — Транспортная задача Переход к следующему опорному решению.

Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу. У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (-).У вершин со знаком (-) выбираем минимальный груз = min[15,19] = 15.

Рис.

Проверка решения Х₁ на оптимальность выполняется аналогично предыдущему шагу.

Таблица 28 — Транспортная задача У вершин со знаком (-) выбираем минимальный груз = min[15,4,0] = 0.

Рис.

Проверка решения Х₂ на оптимальность.

Результаты расчета представлены в распределительной таблице:

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

F^*(x₂) = 12· 19 + 16· 15 + 15· 4 + 15· 15 + 16· 4 + 10· 19 = 1007

Таким образом, решение транспортной задачи:

Рис.

Решение транспортной задачи в среде Microsoft Exс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. Автоматически суммируются значения по строкам:

Рисунок 21 — Поиск оптимального решения Далее выполняют команду Поиск решения (вкладка Сервис или Данные).

Установить целевую ячейку G10, равной минимальному значению.

В поле ввода Изменяя ячейки установить C12: F15

В поле ввода Ограничения установить C12: F15 >= 0

C16:E16 = C7: E7

G12:G15 = G3: G6

Рисунок 22 — Поиск оптимального решения Вычисления производятся при нажатии кнопки Найти решение. Получим решение задачи:

Рисунок 23 — Поиск оптимального решения

4. Решение игры

Рассмотрим игру, представленную платежной матрицей:

.

Так как игра не имеет седловой точки, то она не решается в чистых стратегиях.

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

Решим упрощенную игру с помощью графического доминирования.

Рисунок 24 — Геометрическая интерпретация исходной игры хлебопекарный игра отрасль С помощью геометрического доминирования исходная игра сведена к игре размерности [2×2]

Решим полученную игру аналитическим методом:

Проверка:

V (H)=x*HY*^T=

ЗЛП для игрока 1:

min [ f₀ (х)=х1+х2]

ЗЛП для игрока 2:

max [ g₀(y)=y1+y2+y3+y4+y5]

Найдем решение задачи линейного программирования для первого игрока с помощью программы Microsoft Excel.

Введем целевую функцию в ячейку А1, ограничения в ячейки В1 — В5, а искомые значения x в ячейки С1 — С2. Далее с помощью поиска решений найдем оптимальное решения. Получим следующее:

Рисунок 25 — Поиск оптимального решения Найдем решение задачи линейного программирования для второго игрока с помощью программы Microsoft Excel.

Введем целевую функцию в ячейку А1, ограничения в ячейки В1 — В2, а искомые значения y в ячейки С1 — С5. Далее с помощью поиска решений найдем оптимальное решения. Получим следующее:

Рисунок 26 — Поиск оптимального решения

X=(1/7; 1/7); Y=(0; 1/7; 0; 1/7; 0); ,

g₀(y*)=f₀(x*)=2/7.

Тогда

V (H)=1/(2/7)=7/2;

X*₁=(1/7)/(2/7)=½;

X*₂=(1/7)/(2/7)=½;

Y*₁=0/(2/7)=0;

Y*₂=(1/7)/(2/7)=½;

Y*₃=0/(2/7)=0;

Y*₄=(1/7)/(2/7)=½;

Y*₅=0/(2/7)=0;

Следовательно:

Х= (½; ½),

Y= (0; ½; 0; ½; 0).

V (H) = 7/2

5. Задача динамического программирования

На развитие трех предприятий выделено В млн. руб. Известна эффективность капитальных вложений x_i в каждое j-е предприятие, заданная таблично значением нелинейной функции f_j(x_i), где, n — количество предприятий, m — количество возможных сумм капитальных вложений.

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

Таблица 30- Данные для решения задачи динамического программирования

Математическая модель задачи.

Определить х^* = (, …,, …,), обеспечивающий максимум целевой функции и удовлетворяющий условиям

Математическая модель задачи :

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

.

Условная оптимизация.

Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), определяется с помощью функции Беллмана:

где С_k — количество средств, инвестируемых вk-е предприятие, 0? С_k? В.

На первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств С_n, 0? С_n? В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е.

F_n(С_n) = f_n(С_n) и х_n = С_n.

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах x_i = {0,100,200,300,400,500, 600, 700} тыс. руб.

На первом шаге все капиталовложения идут на 1-е предприятие (Таблица 31).

Таблица 31 — Первый шаг задачи динамического программирования В шапке таблицы отражены варианты значений капиталовложений х₁, которые могут быть предоставлены первому предприятию. В столбце C₁ отражены варианты значений капиталовложений, которые могут быть выделены всем трем предприятиям в совокупности.

Предположим, что все средства в количестве x₁ = 700 тыс. руб. отданы первому предприятию. В этом случае максимальный доход составит f₁(x₁) = 700 тыс. руб., следовательно: F₁(C₁) = f₁(x₁) и x₁= C₁.

На втором шаге определяем оптимальную стратегию при распределении денежных средств между вторым и первым предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:

.

Таблица 32 — Второй шаг задачи динамического программирования В шапке таблицы отражены варианты значений капиталовложений х₂, которые могут быть предоставлены второму предприятию при условии, что часть средств выделяется первому предприятию. В клетках таблицы первое слагаемое — это возможный прирост выпуска продукции второго предприятия f₂(х₂) в результате освоения капиталовложений х₂; второе слагаемое — значение функции Беллмана, полученной на предыдущем шаге F₁(C₂ — х₂), т. е. возможный прирост выпуска продукции первого предприятия, если ему будет выделена оставшаяся часть капиталовложений, определяемая как C₂ — х₂.

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

В шапке таблицы отражены варианты значений капиталовложений х₁, которые могут быть предоставлены третьему предприятию при условии, что часть средств выделяется второму и первому предприятию. В клетках таблицы первое слагаемое — это возможный прирост выпуска продукции первого предприятия f₁(х₁) в результате освоения капиталовложений х₁; второе слагаемое — значение функции Беллмана, полученной на предыдущем шаге F₂(C₁-х₁), т. е. возможный прирост выпуска продукции второго и первого предприятий, если им будет выделена оставшаяся часть капиталовложений, определяемая как C₁ — х₁.

Таблица 33 — Третий шаг задачи динамического программирования Значение функции Беллмана F₁(С₁) представляет собой максимально возможный доход со всех предприятий, а значение, на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в третье предприятие.

Значение целевой функции равно максимальному значению функции Беллмана F₁(С₁)

Следовательно, значение целевой функции равно F_max(x^*) = 270 тыс. руб. Безусловная оптимизация.

Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина С_k = (С_k-1 — х_k-1) оптимальным управлением на k-м шаге является то значение х_k, которое обеспечивает максимум дохода при соответствующем состоянии системы S_k. Определяем компоненты оптимальной стратегии. Для этого значения функций Беллмана и соответствующие им оптимальные значения х вносим в итоговую таблицу 34.

Таблица 34 — Обратный ход По данным из таблицы 34 максимальный доход при распределении 700 тыс. руб. между тремя предприятиями составляет: C₁ = 700, F₃(700) = 270 тыс. руб.

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

х^* = (0, 100, 600), который обеспечит максимальный доход, равный

F (700) = f₁ (0) + f₂(100) + f₃(600) = 0 + 50 + 220 = 270 тыс. руб.;

Заключение

В первом разделе курсовой работы требовалось найти оптимальный план выпуска изделий, который обеспечивал бы организации максимальный доход. Оптимальный план выпуска = 4 единицы. Были найдены решения В ДЗЛП И ПЗЛП: X^* = (0, 1, 0, 0, 6, 3) и Y^* = (4/3;0;0;1;0;5/3). Следовало произвести расчет границ изменения дефицитных ресурсов, в пределах которых не изменится структура оптимального плана. В рассмотренном случае лишь один ресурс используется полностью, следовательно, является дефицитным. Это ресурс Р₁: 0 b₁ b₁ 15/ 2. Также был произведен расчет границ изменения цены изделия, попавших в оптимальный план производства, в пределах которых оптимальный план не изменится.

В план производства вошел второй вид продукции П₂ и цена на него устанавливается в размере 4 ден. ед. В курсовой работе произведена оценка целесообразности приобретения дополнительного количества ресурса и была доказано, что данная процедура не целесообразна. Произведена оценка целесообразности выпуска нового изделия. Учитывая, что затраты на ресурсы для производства продукции третьего вида меньше цены реализации с₄ = 15 ден. ед., то включение ее в план производства целесообразно. В курсовой работе был найден оптимальный план для хлебозавода, оптимальный план перевозки, который равен 1007 денежным единицам, при котором общая стоимость перевозок минимальна, была обоснована ценовая стратегия, цена игры равна 7/2 денежных единиц, было произведено распределение ресурсов между проектами для того, чтобы получить максимальный суммарный доход, который равен 270 тыс. руб. Ко всем расчетам мною были приложены решения в среде Microsoft Excel. Таким образом, все поставленные задачи курсовой работы были выполнены, все методы и методики решения были проанализированы на конкретном виде предприятия.

1. «Математические методы в программировании: Учебник» / Агальцов В. П. — М.:ИД «ФОРУМ», 2013

2. «Динамическое программирование» / Окулов С. М., Пестов О. А. — М.: БИНОМ. Лаборатория знаний, 2012

3. «Компьютерное моделирование математических задач: учебное пособие» / Сулейманов Р. Р. — М.: БИНОМ. Лаборатория знаний, 2012

4. «Введение в математическое моделирование: учебное пособие» / Под ред. Трусова П. В. — М.: Университетская книга, Логос, 2007

5. «Математические методы и модели в управлении» / Шикин Е. В., Чхартишвили А. Г. — М: Дело, 2002

6. «Математические методы и модели исследования операций»: Учебное пособие / Кутузов А. Л. — издательство СПб ГПУ, 2005

7. «Математические методы: Учебник» / Партика Т. Л., Попов И. И. — М: ФОРУМ: ИНФРА, 2005

8. «Математическое программирование» / Костевич Л., издательство «Новое знание», 2003

9. «Экономико-математическое моделирование: практическое пособие по решению задач» / Мадера А. Г. — М: ИЭУП, 2004