Решение задач по ТПР - файл n1.doc

приобрести
Решение задач по ТПР
скачать (937.5 kb.)
Доступные файлы (1):
n1.doc938kb.01.06.2012 12:23скачать

n1.doc

  1   2   3   4
Задача 1

Математическая модель
При производстве изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Исходные данные приведены в таблице:


Тип оборудования

Затраты времени (ч.) на обработку одного изделия

Общий фонд полезного рабочего времени оборудования, ч.

А

В

Фрезерное

10

8

168

Токарное

5

10

180

Шлифовальное

6

12

144

Цена изделия, д.е.

14

18





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


Пусть Х1 – количество изделия А, а Х2 – количество изделия В по плану реализации.

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

По условию задачи условия-ограничения примут вид.


Задача 1

Графический метод
При производстве изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Исходные данные приведены в таблице:


Тип оборудования

Затраты времени (ч.) на обработку одного изделия

Общий фонд полезного рабочего времени оборудования, ч.

А

В

Фрезерное

10

8

168

Токарное

5

10

180

Шлифовальное

6

12

144

Цена изделия, д.е.

14

18





Найти план выпуска изделий, обеспечивающий максимальную выручку от реализации продукции.
Необходимо найти максимальное значение целевой функции F = 14x1+18x2 ? max, при системе ограничений:


10x1+8x2?168

(1)

5x1+10x2?180

(2)

6x1+12x2?144

(3)

x1?0

(4)

x2?0

(5)

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




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


Рассмотрим целевую функцию задачи F = 14x1+18x2 ? max. 
Построим прямую, отвечающую значению функции F = 0: F = 14x1+18x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.




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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
10x1+8x2?168
6x1+12x2?144

Решив систему уравнений, получим: x1 = 12, x2 = 6
Откуда найдем максимальное значение целевой функции:
F(X) = 14*12 + 18*6 = 276

ОТВЕТ: Максимальная выручка от реализации продукции составит 276 д.е.
Задача 1

Симплекс метод
При производстве изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Исходные данные приведены в таблице:


Тип оборудования

Затраты времени (ч.) на обработку одного изделия

Общий фонд полезного рабочего времени оборудования, ч.

А

В

Фрезерное

10

8

168

Токарное

5

10

180

Шлифовальное

6

12

144

Цена изделия, д.е.

14

18





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

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

Определим максимальное значение целевой функции F(X) = 14x1+18x2 при следующих условиях-ограничений.

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

В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5.

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,168,180,144)
Базисное решение называется допустимым, если оно неотрицательно.




14

18

0

0

0

i

Ci

Б

Вi

x1

x2

x3

x4

x5

1

0

x3

168

10

8

1

0

0

2

0

x4

180

5

10

0

1

0

3

0

x5

144

6

12

0

0

1

4




F(X0)

0

-14

-18

0

0

0


Переходим к основному алгоритму симплекс-метода.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения i по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:


Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (12) и находится на пересечении ведущего столбца и ведущей строки.






14


18

0

0

0




i

Ci

Б

В

x1

x2

x3

x4

x5



1

0

x3

168

10

8

1

0

0

21

2

0

x4

180

5

10

0

1

0

18

3

0

x5

144

6

12

0

0

1

12

4




F(X1)

0

-14

-18

0

0

0

0


4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x5 в план 1 войдет переменная x2

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=12

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (12), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:


Bi

x1

x2

x3

x4

x5





































144 / 12 = 12

6 / 12 = 0.5

12 / 12 = 1

0 / 12 = 0

0 / 12 = 0

1 / 12 = 0.08





















После преобразований получаем новую таблицу:






14


18

0

0

0

i

Ci

Б

Вi

x1

x2

x3

x4

x5

1

0

x3

72

6

0

1

0

-0.67

2

0

x4

60

0

0

0

1

-0.83

3

18

x2

12

0.5

1

0

0

0.0833

4




F(X1)

216

-5

0

0

0

1.5


1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения i по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:



Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.





14


18


0


0


0





i

Ci

Б

Bi

x1

x2

x3

x4

x5



1

0

x3

72

6

0

1

0

-0.67

12

2

0

x4

60

0

0

0

1

-0.83

-

3

18

x2

12

0.5

1

0

0

0.0833

24

4




F(X2)

216

-5

0

0

0

1.5

0



4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 2 войдет переменная x1

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=6

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x1 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1 .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:


Bi

x1

x2

x3

x4

x5

72 / 6 = 12

6 / 6 = 1

0 / 6 = 0

1 / 6 = 0.17

0 / 6 = 0

-0.67 / 6 = -0.11
























































После преобразований получаем новую таблицу:




14

18

0

0

0

i

Ci

Б

Вi

x1

x2

x3

x4

x5

1

14

x1

12

1

0

0.17

0

-0.11

2

0

x4

60

0

0

0

1

-0.83

3

18

x2

6

0

1

-0.0833

0

0.14

4




F(X2)

276

0

0

0.83

0

0.94



1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:




14


18


0


0


0


Б

Вi

x1

x2

x3

x4

x5

x1

12

1

0

0.17

0

-0.11

x4

60

0

0

0

1

-0.83

x2

6

0

1

-0.0833

0

0.14

F(X3)

276

0

0

0.83

0

0.94


Оптимальный план можно записать так:

x1 = 12

x4 = 60

x2 = 6

F(X) = 14*12 + 18*6 = 276

Задача №2

Метод северо-западного угла.
На три базы поступил однородный груз в количествах соответственно равных 140, 180 и 160 единиц. Этот груз требуется в четырёх пунктах потребления в количествах равных 60, 70, 120 и 100 единиц соответственно. Тарифы на перевозку еденицы груза от каждого пункта отправления в пункты назначения (д.е) задаются матрицей С:



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


Математическая модель транспортной задачи:

F = ??cijxij, (1)

при условиях:

?xij = ai, i = 1,2,…, m, (2)

?xij = bj, j = 1,2,…, n, (3)

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





1

2

3

4

Запасы

1

2

3

4

2

140

2

8

4

1

4

180

3

9

7

3

7

160

Потребности

60

70

120

100





Проверим необходимое и достаточное условие разрешимости задачи.

?a = 140 + 180 + 160 = 480

?b = 60 + 70 + 120 + 100 = 350

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 130 (480—350). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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





1

2

3

4

5

Запасы

1

2

3

4

2

0

140

2

8

4

1

4

0

180

3

9

7

3

7

0

160

Потребности

60

70

120

100

130




  1   2   3   4


Задача 1 Математическая модель
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации