Курсовая работа - Сведение матричной игры к задаче линейного программирования

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

наибольшей.

4

5

2

1284810

76598

5143102













 

512,14,5,10,10min

54,5,2max







121451010

Так как

5



, то игра имеет седловую точку и задача разрешима в чистых

стратегиях. Выбирая второй тип технологической линии, будет достигнута

наибольшая прибыль не меньше пяти.

23

3. Линейное программирование.

Оптимизационная задача – это экономико-математическая задача, которая

состоит в нахождении оптимального (максимального или минимального)

значения целевой функции, причём значения переменных должны принадлежать

некоторой области допустимых значений.

В самом общем виде задача математически записывается так:

max)(  XfU

;

WX 

, (3.1)

где

 

n

xxxX ,...,

21



;

W

– область допустимых значений переменных

n

xxx ,...,,

21

;

)(Xf

– целевая функция.

Для того чтобы решить задачу оптимизации, достаточно найти её

оптимальное решение, т.е. указать

WX 

0

такое, что

   

XfXf 

0

при любом

WX 

, или для случая минимизации

   

XfXf 

0

при любом

WX 

.

Оптимизационная задача является неразрешенной, если она не имеет

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

если целевая функция

)(Xf

не ограничена сверху на допустимом множестве

W

.

Методы решения оптимизационных задач зависят как от вида целевой

функции

)(Xf

, так и от строения допустимого множества

W

. Если целевая

функция в задаче является функцией

n

переменных, то методы решения

называются методами математического программирования.

В математическом программировании принято следующие основные задачи

в зависимости от вида целевой функции

)(Xf

и от области

W

:

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

)(Xf

и

W

линейны.

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

целочисленности переменных

n

xxx ,...,,

21

.

3. Задачи не линейного программирования, если форма

)(Xf

носит не

линейный характер.

24

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

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

операций, математическая модель которой имеет вид:

   

minmax

1







n

j

jj

xcXf

(3.2)

i

n

j

jij

bxa 



1

,

Ii 

,

 

mMI ,...,2,1

; (3.3)

j

n

j

jij

bxa 



1

,

Mi 

; (3.4)

0

j

x

,

Jj 

,

 

nNJ ,...,2,1

. (3.5)

При этом система линейных уравнений (3.3) и неравенств (3.4), (3.5),

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

W

, называется системой

ограничений задачи линейного программирования, а линейная функция

 

Xf

называется целевой функцией, или критерием оптимальности.

В частном случае, если

I

Ø, то система (3.3) – (3.4) состоит только из

линейных неравенств, а если

MI 

, то – из линейных уравнений.

Если математическая модель задачи линейного программирования имеет

вид:

 







n

j

jj

xcXf

1

min

; (3.6)

i

n

j

jij

bxa 



1

,

mi ,1

;

0

i

b

; (3.7)

0

j

x

,

nj ,1

, (3.8)

то говорят, что задача представлена в канонической форме.

Любую задачу линейного программирования можно свести к задаче

линейного программирования в конической форме. Для этого в общем случае

нужно уметь сводить максимизации к задаче минимизации; переходить от

ограничений неравенств к ограничениям равенств и заменять переменные,

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

функции эквивалентна минимизации той же функции, взятой с противоположным

знаком, и наоборот.

25

Правило приведения задачи линейного программирования к каноническому

виду состоит в следующем:

1. Если в исходной задаче требуется определить максимум линейной

функции, то следует изменить знак и искать минимум этой функции.

2. Если в ограничениях правая часть отрицательна, то следует умножить это

ограничение на -1.

3. Если среди ограничений имеются неравенства, то путём введения

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

4. Если некоторая переменная

k

x

не имеет ограничений по знаку, то она

заменяется (в целевой функции и во всех ограничениях) разностью между двумя

новыми неотрицательными переменными:

lkk

xxx 





, где

l

– свободный индекс,

0



r

x

,

0

l

x

.

26

3.2. Построение экономико-математических моделей задач

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

Рассмотрю процесс построения математической модели задачи линейного

программирования на примерах.

Пример (п.3.1)

Определение оптимального ассортимента продукции.

Предприятие изготовляет два вида продукции – П

1

и П

2

, которая поступает в

оптовую продажу. Для производства продукции используют два вида сырья – А и

В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц

соответственно. Расход сырья на единицу продукции вида П

1

и П

2

дан в табл. 3.1.

Опыт работы показал, что суточный спрос на продукцию П

2

никогда не

превышает 2 ед. в сутки.

Таблица 3.1

Расход сырья на единицу продукции

Сырьё

Расход сырья на ед.

продукции

Запас

сырья,

ед.

П

1

П

2

А

В

2

3

2

9

13

Оптовые цены единицы продукции равны: 3 д. е. – для П

1

и 4 д. е. для П

2

.

Какое количество продукции каждого вида должно производить

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

Процесс построения математической модели для решения поставленной

задачи начинается с ответов на следующие вопросы.

1. Для определения каких величин должна быть построена модель, т.е. как

идентифицировать переменные данной задачи?

2. Какие ограничении должны быть наложены на переменные, чтобы

выполнились условия, характерные для модулируемой системы?

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

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

оптимальному (наилучшему) решению задачи?

27

Ответы на вышеперечисленные вопросы могут быть сформулированы для

данной задачи так: фирме требуется определить объёмы производства каждого

вида продукции в тоннах, максимизирующие доход в д. е. от реализации

продукции, с учётом ограничений на спрос и расход исходных продуктов.

Для построения математической модели остаётся только идентифицировать

переменные и представить цель и ограничения в виде математических функций

этих переменных. Предположим, что предприятие изготовило

1

x

единиц

продукции П

1

и

2

x

единиц продукции П

2

. Поскольку производство продукции П

1

и П

2

ограничено имеющимися в распоряжении предприятия с сырьём каждого

вида и спросом на данную продукцию, а также учитывается, что количество

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

следующие неравенства:

.0

;0

;2

;1

;1323

;932

2

1

2

21









x

xx

Доход от реализации

1

x

единиц продукции П

1

и

2

x

единиц продукции П

2

составит

21

43 xxF 

.

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

всех неотрицательных решений данной системы линейных неравенств требуется

найти такое, при котором функция

F

принимает максимальное значение

max

F

.

Рассмотренная задача относится к разряду типовых задач оптимизации

производственной программы предприятия. В качестве критериев оптимальности

в этих задачах могут быть также использованы: прибыль, себестоимость,

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

Пример (п.3.2)

Использование мощностей оборудования.

Предприятие имеет

m

моделей машин различных мощностей. Задан план по

времени и номенклатуре: T – время работы каждой машин; продукции j-го вида

должно быть выпущено не менее N

j

единиц.

28

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

минимальные затраты на производство, если известны производительность

каждой i-й машины по выпуску j-го вида продукции

ij

b

и стоимость единицы

времени, затрачиваемого j-й машиной на выпуск j-го вида продукции

ij

c

.

Другими словами, задача для предприятия состоит в следующем: требуется

определить время работы i-й машины по выпуску j-го вида продукции

ij

x

,

обеспечивающие минимальные затраты на производство при соблюдении

ограничений по общему времени работы машин T и заданному количеству

продукции N

j

.

По условию задачи машины работают заданное время Т, поэтому данное

ограничение можно представить в следующем виде:

Tx

n

j

ij





1

,

mi ,1

. (3.9)

Ограничение по заданному количеству продукции выглядит следующим

образом:

Nxb

m

i

ijij





1

,

nj ,1

. (3.10)

Задача решается на минимум затрат на производство:

ijij

n

j

m

i

xcZ







11

min

. (3.11)

Необходимо также учесть не отрицательность переменных

0

ij

x

.

Задача поставлена так, чтобы израсходовать все отведённое время работы

машины, т.е. обеспечить полную загрузку машины. При этом количество

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

j

.

Однако в некоторых случаях не допускается превышение плана по номенклатуре,

тогда ограничения математической модели изменяются следующим образом:

Tx

n

j

ij





1

,

mi ,1

; (3.12)

j

m

i

ijij

Nxb 



1

,

mi ,1

; (3.13)

0

ij

x

;

29

ijij

n

j

m

i

xcZ







11

min

(3.14)

Пример (п.3.3)

Минимизация дисбаланса на линии сборки.

Промышленная фирма производит изделие, представляющее сборку из

m

различных узлов. Эти узлы изготавливаются на

n

заводах.

Из-за различий в составе технологического оборудования

производительность заводов по выпуску j-го узла неодинакова и равна

ij

b

.

Каждый i-й завод располагает максимальным суммарным ресурсом времени в

течении недели для производства

m

узлов, равного величине

i

T

.

Задача состоит в максимизации выпуска изделий, что по существу

эквивалентно минимизации дисбаланса, возникающего вследствие

некомплектности поставки по одному или по нескольким видам узлов.

В данной задаче требуется определить еженедельные затраты времени (в

часах) на производство j-го узла на i-м заводе, не превышающие в сумме

временные ресурсы j-го завода и обеспечивающие максимальный выпуск

изделий.

Пусть

ij

x

– недельный фонд времени (в часах), выделяемый на заводе

i

для

производства узла

j

. Тогда объёмы производства узла

j

будут следующими:





n

i

ijij

xb

1

,

nj ,1

. (3.15)

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

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

комплектующих узлов, объём производства которых минимален:



















mjxb

n

i

ijij

,1,min

1

. (3.16)

Условие рассматриваемой задачи устанавливает ограничение на фонд

времени, которым располагает завод

i

.

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

следующем виде.

30

Максимизируем



















mjxbZ

n

i

ijij

,1,min

1

; (3.17)

i

m

j

ij

Tx 



1

,

ni ,1

; (3.18)

0

ij

x

для всех

i

и

j

.

Эта модель не является линейной, но её можно привести к линейной форме с

простого преобразования. Пусть

Y

– количество изделий:



















n

i

jijij

mjNxbY

1

,1,min

. (3.19)

Этому выражению с математической точки зрения эквивалентна следующая

формулировка: максимизировать

YZ 

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







n

i

ijij

Yxb

1

0

,

mj ,1

; (3.20)







m

j

iij

Tx

1

,

ni ,1

; (3.21)

0

ij

x

для всех

i

и

j

;

0Y

.

Пример (п.3.4)

Задача составления кормовой смеси, или задача о диете.

Пусть крупная фирма (Условно назову ее «Суперрацион») имеет

возможность покупать

m

различных видов сырья и приготавливать различные

виды смесей (продуктов). Каждый вид сырья содержит разное количество

питательных компонентов (ингредиентов).

Лабораторией фирмы установлено, что продукция должна удовлетворять по

крайней мере некоторым минимальным требованиям с очки зрения с точки зрения

питательности (полезности). Перед руководством фирмы стоит задача определить

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

соблюдении требований к общему расходу смеси и её питательности.

Решение

Введём условные обозначения:

i

x

– количество i-го сырья в смеси;

31

m

– количество видов сырья;

n

– количество ингредиентов в сырье;

ij

a

– количество ингредиента j, содержащегося в единице i-го вида сырья;

j

b

– минимальное количество ингредиента j, содержащегося в единице

смеси;

i

c

– стоимость единицы сырья I;

q

– минимальный общий вес смеси, используемый фирмой.

Задача может быть представлена в виде





m

i

ii

xcZ

1

min

, (3.22)

при следующих ограничениях:

на общий расход смеси:

qx

m

i





1

; (3.23)

на питательность смеси:

 

 



m

i

m

i

ijiij

xbxa

1 1

,

nj ,1

; (3.24)

на не отрицательность переменных:

0

i

x

,

mi ,1

. (3.25)

Пример (п.3.5)

Задача составления жидких смесей.

Еще один класс моделей, аналогично рассмотренных выше, возникает при

решении экономической проблемы, связанной с изготовлением смесей различных

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

Представим себе фирму, торгующую различного рода химическими

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

Предположим, что эта фирма планирует изготовление смесей m-видов.

Обозначим подлежащее определению количество литров i-го химического

компонента, используемого для получения j-го продукта через

ij

x

. Будем

предполагать, что

0

ij

x

,

ni ,1

,

mj ,1

.

32

Курсовая работа - Сведение матричной игры к задаче линейного программирования

Подождите немного. Документ загружается.