Методические указания к выполнению домашней работы Омск 2014



Скачать 334.38 Kb.
Дата06.06.2019
Размер334.38 Kb.
#97780
ТипМетодические указания


Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»



Основы выбора и принятия

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

Омск – 2014

Составитель: В.Б. Масягин, к.т.н., доцент, профессор кафедры

«Технология машиностроения» ОмГТУ

Методические указания содержат данные, необходимые для выполнения домашней работы для студентов направления 15.03.05 «Конструкторско-технологическое обеспечение машиностроительных производств» дневного, очно-заочного и заочного обучения.

Печатается по решению редакционно-издательского совета

Омского государственного технического университета


1 Цель и содержание домашней работы


Цель домашней работы: освоение методики применения математических моделей для решения такой проблемы принятия технологического решения, как оптимальное планирование производства с использованием ЭВМ.

В процессе выполнения работы студенты решают задачу планирования производства с помощью ЭВМ.

Для планирования производства используется аппарат линейного программирования с реализацией на ЭВМ симплекс-алгоритма и симплекс-метода [1, 4, 5, 7, 9]. Математическая модель, полученная на основе исходных данных задачи планирования и управления, включает линейные уравнения или неравенства, а также линейную целевую функцию.

2. Решение задачи планирования производства


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

Пример. Задача распределения станков для выполнения операций обработки изделий. Условия задачи.

Пусть Мi – располагаемое время полезной работы станка i, где i = 1, 2, ..., п;

j – производимые изделия, где j = 1,2,...,m;

aij время производства изделия j на станке i;

xij количество изделий j, произведенных на станке i;

Рij прибыль от производства изделия j на станке i.

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

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

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

Пример. Дано 8 изделий и 4 станка. Издержки и другие данные приведены в таблицах 1, 2, 3.

Таблица 1

Затраты времени, мин

Станки


Изделия

1

2

3

4

5

6

7

8

1

15

0

18

18

12

0

0

6

2

18

12

20

21

15

0

0

0

3

0

16

10

20

18

6

9

0

4

0

18

0

0

17

13

17

15

Таблица 2

Издержки производства, тыс. руб./мин



Станок

1

2

3

4

Издержки, тыс. руб.

0,05

0,06

0,08

0,04

Таблица 3

Продажная цена изделий, тыс. руб.



Изделие

Продажная цена

Изделие

Продажная цена

1

12,00

5

12,30

2

12,50

6

11,00

3

12,60

7

11,30

4

12,10

8

11,20

Известно, что располагаемое время равно соответственно 30, 35, 28, 29 часам на станках первом, втором, третьем и четвертом.

На основе исходных данных студент составляет уравнения с указанием всех переменных, коэффициентов, констант, и целевую функцию, подготавливает исходные данные для ввода в ЭВМ, получает результаты и выполняет анализ результатов (как это показано ниже) для двух вариантов постановки задачи.

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

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

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

.

Целевая функция: . Следует иметь в виду, что математическая задача линейного программирования решается только как задача минимизации целевой функции, поэтому требование максимизации прибыли преобразовано в требование минимизации с обратным знаком «–».

Для рассматриваемого примера математическая модель примет вид:

(ограничения), (целевая функция).

Представим уравнения в развернутом виде:

15 x11+0 x12+18 x13+18 x14+12 x15+0 x16+7 x17+6 x18  1800,

18 x21+12 x22+20 x23+21 x24+15 x25+0 x26+0 x27+0 x28  2100,

0 x31+16 x32+10 x33+20 x34+18 x35+6 x36+9 x37+0 x38  1680,

0 x41+18 x42+0 x43+0 x44+17 x45+13 x46+17 x47+15 x48  1740.

В этом случае имеются 32 переменные.

Целевая функция определяется путем расчета издержек производства, как это показано в таблице 4, и последующего их вычитания из продажной цены, что дает прибыль, показанную в таблице 5. Наличие нуля в некоторых клетках таблицы 5 говорит о том, что станки, не изготовляющие это изделие, прибыли не дают.


Таблица 4
Издержки производства, тыс. руб.

Станок


Изделие

1

2

3

4

5

6

7

8

1

0,75

0

0,90

0,90

0,60

0

0

0,30

2

1,08

0,72

0,120

1,26

0,90

0

0

0

3

0

1.28

0,80

1,60

1,44

0,48

0,72

0

4

0

0,72

0

0

0,68

0,52

0,68

0,60

Таблица 5

Прибыль, тыс. руб.


Станок


Изделие

1

2

3

4

5

6

7

8

1

11,25

0

11,70

11,20

11,70

0

0

10,90

2

10,92

11,78

11,40

10,84

11,40

0

0

0

3

0

11,22

11,80

10,50

10,86

10,52

10,58

0

4

0

11,78

0

0

11,62

10,48

10,62

10,60

Теперь можно записать целевую функцию:

– 11,25 x11 – 0 x12 – 11,70 x13 – 11,20 x14 – 11,70 x15 – 0 x16 – 0 x17 – 10,90 x18

– 10,92 x21 – 11,78 x22 – 11,40 x23 – 10,84 x24 – 11,40 x25 – 0 x26 – 0 x27 – 0 x28

– 0 x31 – 11,22 x32 – 11,80 x33 – 10,50 x34 – 10,86 x35 – 10,52 x36 – 10,58 x37 – 0 x38

– 0 x41 – 11,78 x42 – 0 x43 – 0 x44 – 11,62 x45 – 10,48 x46 – 10,62 x47 – 10,60 x48 = min.

Решение осуществляется с применением программы симплекс-алгоритма и симплекс-метода S12R. Подготовка исходных данных для программы S12R осуществляется по правилам, приведенным в методических указаниях к лабораторным работам по курсу «Основы выбора и принятия технологических решений».

Исходные данные для варианта 1.

Количество уравнений и количество переменных: 4 36.



Массив коэффициентов уравнений A (табл. 6).
Таблица 6
Массив коэффициентов уравнений A

11

12

13

14

15

16

17

18

21

22

23

24

25

26

27

28

31

32

33

34

35

36

37

38

41

42

43

44

45

46

47

48













1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

15

0

18

18

12

0

0

6

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

18

12

20

21

15

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

16

10

20

18

6

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

18

0

0

17

13

17

15

0

0

0

1

Над таблицей 6, представляющей массив коэффициентов, в первой строке приведены индексы переменных, входящих в ограничения и в целевую функцию; во второй строке приведены индексы переменных, используемые в программе. Индексы над таблицей не вводятся в ЭВМ и указываются только в том случае, когда переменные, входящие в ограничения и целевую функцию имеют два индекса xij. В случае, когда переменные, входящие в ограничения и целевую функцию, имеют один индекс xj, тогда эти индексы совпадают с индексами переменных, используемые в программе (см. табл. 7).

Массив свободных членов уравнений B: 1800 2100 1680 1740.

Строка коэффициентов целевой функции C: –11.25 0 –11.70 –11.20 –11.70 0 0 –10.90 –10.92 –11.78 –11.40 –10.84 –11.40 0 0 0 0 –11.22 –11.80 –10.50 –10.86 –10.52 –10.58 0 0 –11.78 0 0 –11.62 –10.48 –10.62 –10.60 0 0 0 0.

Номера базовых переменных: 33 34 35 36.

Исходные данные представляются в виде текстового файла, например файл f1.txt (рис. 1), причем коэффициенты целевой функции C вводятся одной строкой (на рисунке 1 они расположены на трех строках для компактности рисунка).

Рис. 1. Файл исходных данных для варианта 1

Результаты работы программы выводятся в текстовый файл в том же каталоге, где расположена программа. Вид результатов работы программы S12R для варианта 1 показан на рисунке 2.

Необходимо истолковать оптимальное решение, полученное с помощью ЭВМ. Для рассмотренной выше задачи распределения станков оптимальное решение, полученное с помощью ЭВМ по результатам работы программы S12R, приведено в конце распечатки непосредственно над словами «Оптимальное решение».

В данном случае оптимальное решение (рис. 2) следующее: x[8]= 300,000, x[10]= 175,000, x[22]= 280,000, x[30]= 133,846, z0= 9679,808.

Из рассмотрения двух строк над клетками таблицы 6 определяем, что индексы «8», «10», «22» и «30» во второй строке (используемые в программе) эквивалентны индексам «18», «22», «36» и «46» в первой строке (используемым в уравнениях), следовательно:



х18 =300 – количество обрабатываемых изделий восьмого вида на первом станке,

х22 =175 – количество обрабатываемых изделий второго вида на втором станке,

х36 =280 – количество обрабатываемых изделий шестого вида на третьем станке,

х46 =133 – количество обрабатываемых изделий шестого вида на четвертом станке.

Рис. 2. Результаты работы программа симплекс-алгоритма для варианта 1

Таким образом, целесообразно выпускать только изделия шестого и восьмого вида. При этом целевая функция примет экстремальное значение Z0 = 9679,808, то есть прибыль (максимально возможная) за неделю составит 9679,808 тыс. руб.

Вариант 2. Пусть каждое изделие проходит последовательную обработку на станках, как показано в таблице 1, то есть, работа начинается на первом станке, затем продолжается на втором, потом на третьем и т. д. Уравнения следует записать следующим образом:



(ограничения), (целевая функция).

Заметим, что в уравнениях для варианта 2 вводится различие для значений x только по изделиям (индекс j), но не вводится различие по станкам (индекс i), так как по условиям варианта 2 станки последовательно обрабатывают равное количество изделий данного вида (размеры допускаемого брака могут быть включены в нормативы времени aij). Следовательно, прибыль Рj также является функцией только количества изготовленных изделий каждого вида (индекс j). В тех случаях, когда показано нулевое время aij, имеется в виду, что станок не используется для изготовления изделий на данной операции.

Представим математическую модель в развернутом виде.

Ограничения:

15 x1+0 x2+18 x3+18 x4+12 x5+0 x6+0 x7+6 x8  1800,

18 x1+12 x2+20 x3+21 x4+15 x5+0 x6+0 x7+0 x8  2100,

0 x1+16 x2+10 x3+20 x4+18 x5+6 x6+9 x7+0 x8  1680,

0 x1+18 x2+0 x3+0 x4+17 x5+13 x6+17 x7+15 x8  1740.

Заметим, что в этом случае необходимо только 8 переменных.

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

– 10,17 x1 – 9,78 x2 – 9,70 x3 – 8,34 x4 – 8,68 x5 – 10,00 x6 – 9,90 x7 – 10,30 x8 = min.

Исходные данные для варианта 2.

Количество уравнений и количество переменных: 4 12.

Массив коэффициентов уравнений A (табл. 7).


Таблица 7
Массив коэффициентов уравнений A

1

2

3

4

5

6

7

8













1

2

3

4

5

6

7

8

9

10

11

12

15

0

18

18

12

0

0

6

1

0

0

0

18

12

20

21

15

0

0

0

0

1

0

0

0

16

10

20

18

6

9

0

0

0

1

0

0

18

0

0

17

13

17

15

0

0

0

1

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

Массив свободных членов уравнений B: 1800 2100 1680 1740.

Строка членов целевой функции C: –10.17 –9.78 –9.70 –8.34 –8.68 –10.00 –9.90 –10.30 0 0 0 0.

Номера базовых переменных: 9 10 11 12.

Исходные данные представляются в виде текстового файла, например файл f2.txt (рис. 3).

Рис. 3. Файл исходных данных для варианта 2

Результаты работы программы S12R для варианта 2 показаны на рис. 4.

Рис. 4. Результаты работы программа симплекс-алгоритма для варианта 2

Здесь оптимальное решение (рис. 4): x[1]= 116,667, x[6]= 133,846, x[11]= 876,923, x[9]= 50,000, z0= 2524,962.

Из рассмотрения двух строк над клетками табл. 7 определяем, что индексы «1» и «6» во второй строке (используемые в программе) эквивалентны индексам «1» и «6» в первой строке (используемым в уравнениях), а индексам «9» и «11» из второй строки нет соответствующего индекса в первой строке, следовательно:



х1 =116 – количество обрабатываемых изделий первого вида,

х6 =133 – количество обрабатываемых изделий шестого вида,

х9 =50 – количество неиспользованного ресурса (время) для первого станка,

х11 =876,9 – количество неиспользованного ресурса (время) для третьего станка.

Таким образом, целесообразно выпускать только изделия первого и шестого вида. При этом целевая функция примет экстремальное значение Z0 = 2524,96, то есть прибыль (максимально возможная) за неделю составит 2524,96 тыс. руб.С целью самопроверки следует проанализировать задачу при помощи поиска ответов на вопросы пункта 3 методических указаний.

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

3. Вопросы для самопроверки


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

1. Какие необходимы показатели (транспортные, производственные и торговые издержки, прибыль)?

2. Имеются ли нормативы времени?

3. Какого вида эти нормативы (опытные, расчетные, статистические)?

4. Какова степень точности нормативов?

5. Согласованы ли они друг с другом?

6. Каков коэффициент использования оборудования?

7. Какие изделия следует включить в исследование?

8. Какие станки оборудование должны быть включены в исследование?

9. Имеются ли таблицы времени переналадок и затрат на переналадку?

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

11. Составлены ли планы по сбыту?

12. Можно ли сгруппировать станки по одному нормативному показателю?

13. Производится ли такая группировка в настоящее время?

14. Можно ли сгруппировать изделия?

15. Имеются ли показатели затрат и прибылей по каждому складу?

16. Можно ли провести группировку складов?

17. Имеются ли транспортные тарифы на доставку грузов заказчику и расчеты издержек и прибыли по каждому заказчику?

18. Можно ли произвести группировку заказчиков?

19. Какие изделия можно закупить на стороне и по какой цене?

20. Какова емкость каждого склада?

21. Каковы возможности для закупок?

22. Какова мощность завода?

23. Какова цель (прибыль, издержки, коэффициент использования оборудования и т. д.)?

24. Каковы затраты при замене оборудования?

25. Каковы затраты на приобретение инструмента?

26. Каковы затраты на расширение существующих и строительство новых складов?

27. Каковы затраты на создание и хранение запасов товароматериальных ценностей?

28. Каков сменный суточный график?

29. Каково отношение к сверхурочным работам?

30. Каков плановый период?

31. Предусмотрено ли в плане изменение издержек и прибылей?

32. Каковы слабые места плана?

33. Каковы издержки и прибыль при производстве побочной продукции?

34. Практикуется ли перегрузка грузов в пути следования?

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

1. Каковы коэффициенты переменных, определяющих ограничения? (нормативы времени, или время, необходимое для выполнения заказа; нормативы веса материалов и т.д.).

2. Каковы дополнительные варианты?

3. Имеются ли неравенства в условиях (ограничениях) и требованиях задачи?

4. Каковы требования задачи?

5. Каковы ограничения в задаче?

6. В каких единицах указывается использование одного элемента как части другого элемента?

7. Можно ли упростить ряд ограничений и математическую формулировку задачи?

8. Включены ли в задачу все ограничения и требования?

9. Не включены ли в задачу излишние ограничения и требования?

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

11. Правильно ли сформулирована задача?

Библиографический список

1. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 186 с.

2. Горстко А.Б. В поисках правильного решения. – М.: Знание, 1970. – 77 с.

3. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. – М.: Наука, 1980. – 208 с.

4. Исследование операций: Учеб. для втузов / И.К. Волков, Е.А. Загоруйко, В.С. Зарубин, А. П. Крищенко; Под ред. В. С. Зарубина, А. П. Крищенко. – М.: Изд-во МГТУ им. Н. Э. Баумана, 2000. – 435 с.

5. Курицкий Б.Я. Оптимизация вокруг нас. – Л.: Машиностроение, 1989. – 144 с.

6. Конюховский П.В. Математические методы исследования операций в экономике: Учеб. пособие. – СПб.: Питер, 2002. – 207 с.

7. Карманов В.Г. Математическое программирование: Учеб. пособие для вузов по специальности "Прикладная математика". – 2-е изд., перераб. и доп. – М.: Наука, 1980. – 256 с.

8. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: BHV – Санкт-Петербург, 1997. – 384 с.

9. Рейнфельд Н., Фогель У. Математическое программирование: методы решения производственных и транспортных задач. Пер. с англ. – М.: Издательство иностранной литературы, 1960. – 303 с.

10. Численные методы и математическое обеспечение: Пер. с англ. / Д. Каханер, К. Моулер, С. Нэш; Под ред. Х. Д. Икрамова. – М.: Мир, 1998. – 575 с.

Приложение 1. Задачи к домашнему заданию

1. Основная транспортная задача. Требуется доставить однородный продукт из m пунктов отправления в количествах а1, а2, ..., аm соответственно в n пунктов назначения в количествах b1, b2, ..., bn соответственно. Стоимость cij доставки одной единицы продукта из пункта i в пункт j известна для всех комбинаций (i,j).

Задача состоит в том, чтобы определить количество продукта xij, которое нужно отправить по каждому пути (i,j), для того, чтобы минимизировать общую стоимость доставки. ai представляет собой наличные, а bi – требуемые количества продукта.

2. Транзитная задача. Это транспортная задача, в ней пункты отправления и назначения могут выступать в качестве промежуточного пункта, через который переправляются товары в конечный пункт назначения. Данную задачу можно свести к основной транспортной.

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

3. Задача о танкерных перевозках. Дано некоторое число портов i = 1, 2, ..., m, в которых производится загрузка танкеров, отправляющихся затем в порты назначения j = 1, 2, ..., n. Мы знаем время, необходимое для загрузки в порту i танкера, отправляющегося в порт j, а также время, затрачиваемое на путь из одного порта в другой и время выгрузки. Предполагается, что все танкеры одинаковы, а перевозки выражаются в единицах вместимости танкера. Доставив груз, танкер может идти в любой погрузочный порт.

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

4. Транспортная задача с ограниченными возможностями. Это основная транспортная задача, в которой возможные перевозки ограничены сверху, то есть хijuij.

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

5. Задача планирования производства. Предприниматель знает, что ему надо изготовить Ri (i = 1, 2, 3, ..., n) единиц некоторого товара в течении ближайших N месяцев. Это количество можно производить или регулярным образом, не более Ai единиц в месяц, или форсированным образом, не более Bi единиц в месяц. Стоимость производства одной единицы товара в i-м месяце равна Ci при регулярном и Di – при фиксированном способе производства. Ввиду колебания стоимости с течением времени, а также ввиду ограниченных возможностей может оказаться, что экономней производить товар впрок, до того, как он потребуется в действительности.

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

6. Задача поставщика. Поставщик инструментов знает, что ему требуется в течение ближайших n дней заточенных инструментов по rj штук в день, j = 1, 2, ..., n. Восстановление инструментов обычно занимает p дней, то есть, если затупившийся инструмент посылается на заточку не медленно после того, как был использован в j-й день, то он возвращается назад и вновь может быть использован в (j+p)-й день.

Кроме того, при восстановлении есть сложное обслуживание, при котором инструменты возвращаются через q дней (p и q – целые числа; q > p). Не имея под рукой или на восстановлении нужного количества инструментов, поставщик удовлетворяет первоначально свои потребности, покупая инструменты по а руб. за штуку. Восстановление одного инструмента стоит при обычном обслуживании b руб., а при срочном c руб. Как следует поступать поставщику, чтобы удовлетворить свои нужды и минимизировать расходы в данные n дней ?

7. Задача о назначениях. В заданиях этого типа нам дано определенное количество индивидуумов, машин и т.д., которое требуется распределить для выполнения некоего множества работ. Для каждого индивидуума i задана оценка Cij, изменяющая его эффективность при выполнении работы j. Индивидуум может быть назначен только на одну работу.

Пусть Ai – наличное количество индивидуумов типа i, а Bj – наличное количество работ типа j. Мы полагаем, что сумма Ai равна сумме Bj. Во многих случаях все Ai и Bj равны 1 и m = n; xij выражает собой назначение i-го индивидуума на j-ю работу.

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

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

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

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

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

В этой задаче мы хотим так спланировать производство, чтобы минимизировать сумму издержек, вызванных колебаниями выпуска и хранением. Обозначения: Xt – продукция в месяце t; Rt – потребности в месяце t; St – количество продукта на складе в месяце t; Yt – увеличение продукции; Zt – уменьшение продукции; а – стоимость увеличения производства продукции на единицу; b – стоимость хранения единицы продукции на складе в течение месяца.

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

12. Задача о распределении станков. В данном случае постановка задачи такова: минимизировать при условии, что , (*)

, Xij  0.

С особенностью Bij = 0, уравнения (*) превращаются в неравенства(); Aij представляют собой время, затрачиваемое на производство одной единицы продукта j на станке i; Xij – число единиц продукта j, изготавливаемое на станке i; Bi – число единиц j, которое необходимо получить; Cij – стоимость производства одной единицы продукта j на станке i.



Приложение 2. Основные сведения о применяемых математических обозначениях

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

Константа – это символ, применяемый для обозначения известной величины. Обычно в качестве констант используются начальные строчные буквы латинского алфавита. Например, а, b, с, d, е являются константами. Аналогично, 17, 21, 18 и т. д. тоже являются константами. Символ а используется обычно для обозначения того, что величина известна, но конкретные цифры не применяются, так как они могут ввести в заблуждение.

Коэффициент – специальный вид константы. Коэффициент – это число, умноженное на переменную.

Переменная – это символ, обозначающий неизвестное количество. Обычно переменные обозначаются конечными буквами латинского алфавита: х, у, z или X, Y, Z.

Выражение ах говорит о том, что а взято х раз, где а известно, а х неизвестно. Если а = 10, мы получим 10х. Если х – неизвестное количество изделий, которое должно быть произведено, и если стоимость каждого изделия, которое должно быть изготовлено, равна 10 руб., то при х = 100 мы получим 1000 руб.

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

Константы и переменные выражаются теми же буквами алфавита, как и раньше, с добавлением верхних и нижних индексов (например, x(1) или x1; называют «x-один»). Верхний индекс всегда заключается в скобки, чтобы не спутать его с показателем степени, который обозначает переменные высшей степени. x1. По этому методу условных обозначений x1 и x2 являются различными переменными с присущей им индивидуальностью. Далее, ясно, что число различных x-переменных, которое мы можем записать, используя верхние и нижние индексы, безгранично. Таким образом, если x, y и z принято использовать для обозначения переменных в небольших задачах, то x1, x2 и x3 могут быть использованы для этой же цели в больших задачах.

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

Нижние индексы i, j и k применяются для обозначения общей переменной или константы; x, записанное как xi будет означать x из числа возможных переменных. Например, могут встретиться следующие обозначения x: x1, x2, x3, x4, x5, x6; в этом случае xi можно отнести к любому x. Мы добьемся большей определенности, введя новые обозначения: xi, где i = 1, 2, ..., 6. Последний член в группе членов обозначается нижним индексом п или т. Так поступают в тех случаях, когда точно не известно количество членов, но необходимо разъяснить читателю, много ли, какие именно члены должны быть рассмотрены. Этот метод точнее выбора числа наугад в целях иллюстрации, который, возможно, ведет к неправильному пониманию. В вышеуказанном случае п = 6. Мы можем записать значения x в более общей форме: x1, x2, …, xn или xi, i =1, 2, .... n.

Теперь мы ссылаемся на любое x, число которых п. Точки в обоих случаях означают числовую последовательность. Выражение x1 + x2 + x3 + x4 + x5 + x6 понятно, но громоздко. Если п = 1000, то для того чтобы это записать, потребуется несколько часов. С применением символа Σ (сигма) выражение может быть обобщено для любого числа членов: . Это обобщенное выражение показывает, что все значения x взяты вместе (каждое из них рассматривается только один раз) и что мы должны сложить первые п из них. Теперь выражение, в котором п = 6, можно записать так:

или

Обычно в матрицах предпочитают применять 2 или больше нижних индексов. Принято, что индекс i относится к строке, а j – к столбцу. Величина записывается следующим образом: xij. Таким образом, читая нижние индексы, можно определить, какая строка и столбец имеются в виду. Например, x23 – это переменная из второй строки и из третьего столбца.

Знак суммы Σ применяется для объединения нижних и верхних индексов. Выражение может быть записано следующим образом:

x11 + x21 + x31 +…+ xn1

x12 + x22 + x32 +…+ xn2

………………………



x1m + x2m + x3m +…+ xnm

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

1) нужно сложить все значения x, которые имеют различные нижние индексы на месте i, но одинаковый нижний индекс на месте j;

2) каждому изменению нижнего индекса j соответствует новое уравнение.

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

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

Выражениеозначает:

x11 + x12 + x13 +…+ x1m

x21 + x22 + x23 +…+ x2m

………………………



xn1+ xn2 + xn3 +…+ xnm

Другими словами, сложите все j с i, имеющим постоянную величину.

Наконец, выражение означает сумму значений всех x, имеющих нижние индексы i и j: .

Выражение иногда записывают следующим образом: или



С верхними индексами или дополнительными нижними индексами поступают таким же образом. Константы и коэффициенты тоже могут иметь нижние и верхние индексы и обрабатываться таким же образом.



Скачать 334.38 Kb.

Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©www.vossta.ru 2022
обратиться к администрации

    Главная страница