Типовые задачи исследования операций.

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

1. Задачи линейного программирования.

Задача о пищевом рационе (Задача хозяйки, задача о солдатской столовой).

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

- белков не менее b₁ единиц,

- углеводов не менее b₂ единиц, (*)

- жиров не менее b₃ единиц.

Единица продукта П₁ содержит a₁₁, единиц белков, a₁₂ единиц углеводов, a₁₃ единиц жиров и т.д.

Требуется составить пищевой рацион так, чтобы обеспечить условие (*) при минимальной стоимости продуктов. Построим модель задачи ИО. Обозначим x₁, x₂, x₃, x₄ количества продуктов, входящих в рацион. Общая стоимость будет:

L=c₁x₁+c₂x₂+c₃x₃+c₄x₄ или

L=.

Запишем условия для белков, жиров и углеводов

a₁₁x₁+a₂₁x₂+a₃₁x₃+a₄₁x₄b₁ ;

a₁₂x₁+a₂₂x₂+a₃₂x₃+a₄₂x₄b₂ ;

a₁₃x₁+a₂₃x₂+a₃₃x₃+a₄₃x₄b₃ .

Эти условия представляют собой ограничения, накладываемые на решение.

Таким образом, возникает следующая задача ИО: выбрать неотрицательные значения переменных x₁, x₂,x₃, x₄ (вектора (x₁, x₂, x₃, x₄)), удовлетворяющие системе линейных неравенств (**), при которых линейная функция этих переменных

L= c₁x₁+c₂x₂+c₃x₃+c₄x₄

обращалась бы в минимум.

С некоторыми модификациями эта задача называется задачей о пайке. Обычно в нее добавляются ограничения:

- вес пайка не должен превышать заданной величины р,

- паек должен быть минимального объема.

Иногда (для пайка) меняются местами целевая функция и ограничение:

- стоимость пайка не должна превышать С денежных единиц;

- паек должен иметь максимальную калорийность.

При этом считается, что для единицы каждого продукта П_k известны объем v_k, вес р_k и калорийность q_k.

Задача о распределении ресурсов.

Имеются какие-то ресурсы (сырье, рабочая сила, оборудование, информация):

R₁, R₂, …, R_m в соответствующих количествах: b₁, b₂, …, b_m единиц.

С помощью этих ресурсов может производиться конечная продукция (товары):

T₁, T₂, …, T_n.

Для производства одной единицы товара T_j необходимо a_ij единиц ресурса R_i (i=, j=). Каждая единица ресурса R_i стоит d_i гривен (i=). Каждая единица товара может быть реализована по цене c_j ( j=).

По каждому виду товара количество произведенных единиц ограничивается спросом: рынок не может поглотить более, чем k_j единиц товара T_j (j=1, 2, …, n).

Какое количество единиц какого товара надо произвести для того, чтобы получить максимальную прибыль?

Обозначим x₁, x₂, …, x_n количества товаров T₁, T₂, …, T_n , планируемые к производству. Условия спроса налагают следующие ограничения:

x₁ k₁; x₂ k₂; …; x_n k_n.

Ресурсов должно хватить, отсюда ограничения:

a_n1x₁+a₁₂x₂+…+a_1nx_nb₁ ;

a₂₁x₁+a₂₂x₂+…+a_2nx_nb₂ ;

. Об этом говорит сайт https://intellect.icu . . . . . . . . . .

a_m1x₁+a_m2x₂+…+a_mnx_nb_m.

Или в более коротком виде:

;

;

. . . . . .

Найдем выражения для прибыли: себестоимость единицы товара T_j равна:

S_j= a_1jd₁+ a_2jd₂+ …+ a_mjd_m,

или

S_j= , (j=).

Вычислим себестоимость товара каждого вида: S₁, S₂, …, S_n.

Чистая прибыль q_j для товара T_j равна разнице между продажной ценой C_j и себестоимостью S_i:

q_j =C_j - S_j , (j=).

Чистые прибыли: q₁, q₂, …, q_n .

Общая прибыль (целевая функция):

L = q₁x₁ + q₂x₂ + …+q_nx_n,

или короче:

L = .

Выбрать такие неотрицательные значения переменных x₁, x₂, …, x_n, которые удовлетворяют линейным неравенствам и обращают в максимум линейную функцию L.

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

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

Старинная русская задача.

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

Пусть x₁, x₂, x₃ - число кур, уток и гусей, соответственно взятых для продажи. Целевая функция:

c₁x₁+c₂x₂+c₃x₃ = max.

Условие-ограничение - масса товара, который может взять бабушка:

a₁x₁+a₂x₂+a₃x₃P,

x₁, x₂, x₃ Z.

При желании можно учесть конъюнктуру рынка.

Задача о рюкзаке.

Это одна из наиболее популярных задач целочисленного программирования.

Турист готовится к длительному переходу. В рюкзаке он может нести груз массой не более W кг. Этот груз может включать n видов предметов, каждый предмет типа j, массой w_j кг, j=. Для каждого вида предмета турист определяет его ценность E_j во время похода. Сколько предметов каждого типа он должен положить в рюкзак, чтобы общая ценность снаряжения была максимальной?

Обозначим через x_j – количество предметов j – го типа в рюкзаке. Тогда математическая модель задачи такова:

max

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

, x_j Z (целые).

x_j0, j=.

Это так называемые задачи о неделимостях (Загрузка транспортных средств, план пожарной эвакуации).

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

Задача.

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

1) продать машину и заменить ее новой;

2) отремонтировать и продолжать эксплуатацию;

3) продолжать эксплуатацию без ремонта.

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

Показатель аддитивности:

W = ,

где w_i – расходы в i-м году. W надо обратить в минимум. Управление может быть таким:

x = (3, 3, 2, 2, 2, 1, 3, …).

А в общем случае это вектор:

x = ( j₁, j₂, …, j_m ),

где j₁, j₂, …, j_m могут принимать значения 1, 2 или 3.

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

W =

( аддитивный критерий).

Полушутя – полусерьезно Л.Н. Толстой предложил критерий оценки качества человека. Он имел вид дроби, в числителе которой стоят достоинства человека, а в знаменателе – его мнение о себе. Этот критерий логичен только с первого взгляда

( ).

4. Задачи на сетях.

Особый класс задач Ио составляют задачи на сетях.

В качестве примера сетевой или потоковой задачи рассматривают транспортную задачу, решенную в 1948г. Ф.Л.Хичкоком.

Транспортная задача.

Пусть есть два завода и три склада. Заводы производят соответственно S₁ и S₂ единиц продукции, возможности складов – d₁,d₂,d₃ единиц

S₁+S₂=d₁+d₂+d₃

Задача состоит в том, чтобы минимизировать затраты на перевозку продукции с заводов на склады. Пусть x_ij – объем продукции, который необходимо перевезти с i-го завода на j-й склад и c_ij – стоимость перевозки единицы продукции с i-го завода на j-й склад.

Тогда целевая функция - стоимость перевозки – имеет вид:

c₁₁x₁₁+c₁₂x₁₂+c₁₃x₁₃+c₂₁x₂₁+c₂₂x₂₂+c₂₃x₂₃=

Условие того, что вся продукция будет увезена с каждого завода:

x₁₁+x₁₂+x₁₃==S₁

x₂₁+x₂₂+x₂₃==S₂

Или кратко: =S_i ; i=1,2.

Условие заполнения складов имеет вид:

=d_j ;

Основы линейного программирования.

Постановка общей задачи линейного программирования (ЛП) и ее анализ.

Если множество допустимых решений - выпуклый многогранник, а критерий оптимальности – скалярная линейная целевая функция, то задача называется задачей ЛП. Говоря о задачах ЛП, мы фактически имеем в виду не саму задачу ИО, а ее математическую модель, обладающую определенными свойствами.

Задача ЛП имеет следующий вид:

(2.1)

Где a_ik, c_k, b_i – известные числовые параметры, а множества I₁,I₂,I₃ попарно не пересекаются и . Неизвестные x_k, , представляющие собой координаты вектора X (x₁,x₂,…,x_n)^Tназывают управляемыми переменными или переменными модели.

Рассмотрим пример.

Предприятие производит два вида лака для внутренних и наружных работ. Для производства лаков используются два исходных продукта – А и В. Максимально возможные суточные затраты этих продуктов определяются емкостями, которые имеются, и составляют 6 и 8т соответственно. На производство 1т лака для внутренних работ расходуется 1т продукта А и 2т продукта В, а при производстве 1т лака для внешних работ расходуется 2т продукта А и 1т продукта В.

Изучение рынка показало, что суточный спрос на лак для наружных работ не превышает 2т. Доход от реализации (в тыс. у.е.) 1т лака для внутренних работ равен 3, а доход от реализации 1т лака для внешних работ-2.

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

Суть этой задачи ИО можно определить следующим образом. Необходимо определить объемы производства каждого вида продукции с учетом ограничений на спрос и с учетом расхода исходных продуктов А и В.

Управляемыми переменными являются x₁ – суточный объем выпуска лака для внутренних работ, x₂ – суточный объем выпуска лака для наружных работ. Таким образом, n=2.

Суточный расход исходных продуктов А и В не может превосходить максимального суточного запаса, т.е. и .

Ограничение на величину суточного спроса на лак для наружных работ имеет вид . Так как объемы не могут быть отрицательными, то . Таким образом в задаче (2.1) m=3, I₁={1,2,3},I₂=I₃=0.

Общий доход f(x₁,x₂)=3x₁+2x₂. Математическая модель рассматриваемой задачи ИО может быть представлена в виде:

3x₁+2x₂max

,; (2.2)

Вау!! 😲 Ты еще не читал? Это зря!

• Выпуклость в экономике
• Жадный алгоритм
• Невыпуклость ( экономика )
• Стохастическое программирование
• Стохастическое динамическое программирование
• Обучение с подкреплением
• динамическое программирование ,
• нелинейное программирование ,

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