Научная литература
booksshare.net -> Добавить материал -> Математика -> Красс М.С. -> "Математика для экономистов" -> 80

Математика для экономистов - Красс М.С.

Красс М.С. , Чупрынов Математика для экономистов: Учебное пособие — СПб.: Питер, 2005. — 464 c.
ISBN 5-94723-672-9
Скачать (прямая ссылка): krass2005.pdf
Предыдущая << 1 .. 74 75 76 77 78 79 < 80 > 81 82 83 84 85 86 .. 137 >> Следующая


2. Правило «прямоугольника* состоит в следующем. Пусть ключевым элементом предыдущего шага является элемент 1 -й строки (m + 1 )-го столбца A1 я tТогда элемент г-н строки (т + 2)то столбца последующего шага, который обозначим k\ mt3, по правилу «прямоугольника» определяется по формуле

где й, |М + г, А, „ . j — элементы предыдущего шага.

14.2.2. Применение симплексного метода в задачах ЛП Поясним применение симплексного метода.

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

Tl роиэ ВО ДСТНРН11 !.1 fr ресурс
Раскол ресурсов за 1 месяц
Общші ресурс
-1

I -м способ
2-Гг способ

Сырье
L
2

Оборудование
1
1
3

Электроэнергия
2
1
8

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором — 4 тыс. изделий.

270 Глава 14. Линейное программирование

Cv

3
А
0
0
0


J

-?

-*u
Vs
ь,

0
¦•'a i I
2
1
0
0
4

0

1
1
q
l
0
3

u

2
1
0
u
1
8



-3

а
0
0
0

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

Решение. Составим математическую модель задачи. Для этого введем обозначения:

• Xx — время работы предприятия первым способом,

• .Vj - время работы предприятия вторым способом.

Тогда задача ЛП формулируется следующим образом: найти максимум целевой функции

LCx) = За"і + Ax2 —> max

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

+2х.2 <4,

¦ .t1 + .y3 < 3,

2jt, +X2 <8, дг, >0. X1 >0.

Приведем задачу к каноническому виду, для чего добавим в правые части ограничений дополнительные неизвестные х3. xt и xs (балансовые переменные) при ограничениях

.V1 + Ix1 + хЛ =4,

< X1 + X2 -KV4 = 3,

2г, +X7 +X5 = 8,

X a 0 / = ЇХ Теперь составим симплексную таблицу 1-го шага:

14,2. Симплексный метод 271

X1 =(0. 0, 1 а 8), L(X)=Q.

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

переменной ХЬ а за КЛЮЧевуЮ СфОКу — Строку ПеремеННОЙ Jf3, где

min (\/2, 3/1. 8/1) = min (2, 3, 8) = 2.

Ключевым элементом является *2>. Вводим и столбец БП переменную хг, выводим jfj. Составляем симплексную таблицу 2-го шага:


БП
3
4
0
0
0


JfI
х2
ч
.T4
¦Ч
ь>

А

1/2
1
1/2
0
0
2

0
X4
V2
0
-1/2
1
0
I

0

3/2
0
-V2
0
1
е


-1
0
2
Q
0
~ В

X1 =(0, 2, О, І, 6), L(X2 )=&

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым злементом является «1/2». Составляем симплексную таблицу 3-го шага:



3
1
0
0
0

W)

*1
¦*2
х1

*5



4
х?
0
1
1
-1
0

І

3
х\
1
0
-1
2
0
2

0
Ч_
0
0
1
-3
I

3


<V
U
0
I
2
0
10

Uce оценки свободных неременных Д>0, следовательно, найденное опорное решение является оптимальным:

X^ =(2, 1, 0, 0, 3), і(т)„ =10.

Ответ. Первым способом предприятие должно работать два месяца, вторым — один месяц, при этом максимальный выпуск продукции составит 10 TbLC ед.

272 Глава 14. Линейное программирование

14.3. Двойственные задачи

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

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

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

14.3.1. Виды математических моделей двойственных задач Симметричные двойственные задачи

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

I(.r) = C1Xj + C3-Ti + ¦-¦ + с1:хц -> max ?14.9)

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

a,.xt + al2x2 + ... + а!л.т„ 5A1 \уг

a2irt +a.i2x, + ... + alrxK <b, \ у,, (\4\Q)

U1nX1 + amx-, + ... + лт„х„ < Ь„ ]

X1 > О, J = 1, п, І = !, т.

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

• каждому неравенству системы ограничений исходной задачи приводити в соответствие переменную у-,

• составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничении исходной задачи;

• составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы оіранпчений исходной задачи. При этом знаки неравенств меняются на противоположные. Свободными членами системы
Предыдущая << 1 .. 74 75 76 77 78 79 < 80 > 81 82 83 84 85 86 .. 137 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed