Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методические материалы_практическим занаятиям.docx
Скачиваний:
7
Добавлен:
01.07.2025
Размер:
388 Кб
Скачать
☆

Метод минимального элемента

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

Поставщики

Мощность

поставщиков

Потребители и их спрос

B 1

B 2

B 3

B 4

20

100

60

50

1

3

4

2

A1

50

20

30

2

5

1

4

A2

70

60

10

7

6

3

4

A3

80

70

10

0

0

0

0

A4

30

30

Число заполненных клеток m+n-1=7, затраты на перевозку

S= 20*1+30*2+60*1+10*4+70*6+10*4+30*0=640.

Общая стоимость перевозки меньше, чем в предыдущем способе, но это не означает, что так бывает всегда, что способ лучше. Далее этот первоначальный план нужно улучшать. Для этого предназначен метод потенциалов. Потенциалы клетки - это целые числа, Ui и Vi, такие, что их сумма равна Ci., их истинной стоимости

Находим сумму потенциалов для занятых клеток из системы уравнений Ui+Vi= Ci.

Поставщики

Мощность

поставщиков

Потребители и их спрос

B 1

B 2

B 3

B 4

20

100

60

50

U

1

3

4

2

A1

50

20

4

-1

30

U1=0

-1

5

2

5

1

4

A2

70

3

6

60

10

U2=2

-1

-1

7

6

3

4

A3

80

3

70

1

10

U3=2

-4

2

0

0

0

0

A4

30

-3

30

-5

-2

U4=-4

3

5

2

V

V1 =4

V2=4

V3=-1

V4=2

V1 +U1 = 1 V2 + U3 = 6 V2 + U4 = 0 V3 + U2 = 1 V4 + U1 = 2 V4 + U2 = 4

V4 + U3 = 4

Решаем систему в целых числах. Поскольку число уравнений на единицу меньше числа неизвестных, то зададимся любым значением одного из Ui и Vi Пусть U1 =0. Решением системы будет следующее:

V1 = 1 U1 = 0

V2= 4 U2 = 2

V3 = -1 U3 = 2

V4 = 2 U4 = -4

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

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

Занимаем эту клетку, ставим в нее (.) и начинаем строить цикл так, чтобы он прошел по занятым клеткам и имел вид прямоугольников. Расставляем знаки (+) и (-) по углам цикла, начиная с выбранной клетки - для нее (+). Затем из 2 клеток с (-) (-30 и -70) выбираем меньшее число по абсолютной величине (30) и от него в новом плане, соблюдая знаки, движемся по циклу, причем в клетках со знаком (+) это число прибавляем, а в клетках со знаком (-) -вычитаем.

Поставщики

Мощность

поставщиков

Потребители и их спрос

B 1

B 2

B 3

B 4

20

100

60

50

U

1

3

4

2

A1

50

20

30

-2

1

U1=0

6

1

2

5

1

4

A2

70

4

6

60

10

U2=3

-2

-1

7

6

3

4

A3

80

4

40

1

40

U3=3

3

2

0

0

0

0

A4

30

-2

30

-5

-3

U4=-3

2

5

3

V

V1 =1

V2=3

V3=-2

V4=1

Опять получены 2 клетки с отрицательными разностями, следовательно, план можно еще улучшить.

Из 2 отрицательных наименьшее число - 1.

Поставщики

Мощность

поставщиков

Потребители и их спрос

B 1

B 2

B 3

B 4

20

100

60

50

U

1

3

4

2

A1

50

10

40

0

1

U1=0

4

1

2

5

1

4

A2

70

10

4

60

2

U2=11

1

2

7

6

3

4

A3

80

4

30

3

50

U3=3

3

0

0

0

0

0

A4

30

-2

30

-3

-2

U4=-3

2

3

2

V

V1 =1

V2=3

V3=0

V4=1

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

S=10*1+10*2+40*3+30*60+30*0+60*1+50*4=590.

Задание.

1. Для производства четырех видов изделий А1, А2 ,А3, А4 завод должен использовать три вида сырья I,II,III, запасы которого на планируемый период составляют соответственно 1000, 600 и 150 условных единиц. (Предполагается, что ресурсы других видов имеются в количествах, достаточных для выполнения оптимального плана).

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

Вид сырья

Запас сырья

Технологические коэффициенты

A1

A2

A3

A4

I

1000

5

1

0

2

II

600

4

2

2

1

III

150

1

0

2

1

Прибыль от реализации

6

2

2,5

4

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

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

Станки

Время работы

Время обработки одной детали

станков

А1

А2

I

16

1

2

II

28

2

3

III

30

3

3

Прибыль...

4

3

Составить план производства, обеспечивающий наибольшую прибыль, при условии, что количество деталей вида А2 не должно быть меньше количества деталей вида А1. Решить задачу графически.

3. Решить транспортную задачу. Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: 120,100 и 80 условных единиц соответственно. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Затраты на перевозку приведены в таблице.

Поставщики

Мощность поставщиков

Потребители и их спрос

B 1

B 2

B 3

90

90

120

A1

120

7

6

4

A2

100

3

8

5

A3

80

2

3

7

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

Ресурсы

Расход материалов на производство

одной запасной части, кг

Запас ресурсов,

кг

1

2

3

I

5

5

2

1200

II

4

--

3

300

III

--

2

4

800

Прибыль от реализации одной запасной части (д. е.)

5

8

6

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

5. Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозку одного двигателя из районов к мастерским следующие:

Районы

Мастерские

1

2

3

1

4,5

3,7

8,3

2

2,1

4,3

2,4

3

7,5

7,1

4,2

4

5,3

1,2

6,2

5

4,1

6,7

3,1

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

6. Из трех продуктов — I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества «А», 8 ед. вещества «В» и не менее 12 ед. вещества «С». Структура химических веществ, приведена в следующей таблице:

Продукт

Содержание химического вещества

в 1 ед. продукции

Стоимость 1 ед. продукции

А

В

С

1

2

1

3

2

II

1

2

4

3

III

3

1,5

2

2,5

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

7. Цех выпускает три вида деталей - А, В, С. Каждая деталь обрабатывается тремя станками. Организация производства в цехе характеризуется следующей таблицей:

Станок

Длительность обработки детали, мин.

Фонд времени,

час

А

В

С

1

12

10

9

220

II

15

18

20

400

III

6

4

4

100

Отпускная цена

за одну деталь

30

32

30

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

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

Станок

Трудоемкость на 1 ед. продукции

Фонд времени, час.

А

В

1

3

3

15

2

2

6

18

3

4

0

16

4

1

2

8

Прибыль на 1 ед.

2

3

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

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

Питательные вещества

Количество единиц питательных веществ на 1 кг.

корма 1

корма 2

Белки

Углеводы

Протеин

3

1

1

1

2

6

Стоимость 1 кг корма первого вида — 4 д.е., второго — 6 д.е.

Составьте дневной рацион питательности, имеющий минимальную стоимость.

10 Хозяйство располагает следующими ресурсами: площадь -100 ед., труд - 120 ед., тяга - 80 ед. Хозяйство производит четыре вида продукции: А, В, С, Д. Организация производства характеризуется следующей таблицей:

Продукция

Затраты на 1 ед. продукции

Доход от ед.

продукции

площадь

труд

тяга

А

2

2

2

1

В

3

1

3

4

С

4

2

1

3

Д

5

4

1

5

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

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