Вариант 18: задача 2, 3, 4

  • ID: 04204 
  • 11 страниц

Фрагмент работы:

Вариант 18: задача 2, 3, 4

Задача 2.6

Для производства двух видов изделий А и В используются три типа технологического оборудования. На производство единицы изделия А оборудования первого типа используется а1=3 часов, оборудование второго типа а2= 3 часов, оборудование третьего типа а3= 2 часов. На производство единицы изделия В оборудование первого типа используется b1=2 часов, оборудования второго типа - b2=3 часов, а оборудование третьего типа - b2=5 часов.

На изготовление всех изделий администрация предприятия может предоставить оборудование первого типа не более чем на t1=273 часов, оборудование второго типа на более чем на t2=300 часов, а оборудование третьего типа - не более чем на t3=380 часов.

Прибыль от реализации единицы готового изделия А составляет s =4 руб., а изделия В - r =5 руб.

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

Решить задачу графически и симплекс - методом.

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

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

x1 - количество изделий А, x2 - количество изделий В

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

Расход сырья первого вида - 3х1 + 2х2

Расход сырья второго вида - 3х1 + 3х2

Расход сырья третьего вида - 2х1 + 5х2

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

3х1 + 2х2? 273

3х1 + 3х2? 300

2х1 + 5х2? 380

Кроме того также должны выполняться условия неотрицательности переменных х1, х2, т.е. х1 ? 0, х2 ? 0.

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

Если обозначить функцию прибыли через Z, то: Z = 4х1 +5х2, а основная цель может быть выражена так: максимизировать целевую функцию: Z = 4х1 +5х2.

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

Найти неизвестные значения переменных х1, х2, удовлетворяющие ограничениям

3х1 + 2х2? 273

3х1 + 3х2? 300

2х1 + 5х2? 380

х1 ? 0, х2 ? 0.

и доставляющие максимальное значение целевой функции Z = 4х1 +5х2? max.

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

=...

=...

=...

Построим вектор С = (4, 5) и целевую функцию по уравнению: 4x1 + 5x2 = 200

На рис. 1 видно, что оптимальное решение соответствует точке В, лежащей на пересечении прямых (2) и (3). Поэтому ее координаты находятся как решение системы линейных уравнений, задающих эти прямые:

При этом значение целевой функции

Рис. 1. Графическое решение задачи.

Решим задачу симплекс - методом. Приведем исходную задачу к каноническому виду:

=...

=...

=...

х1 ? 0, х2 ? 0, х3 ? 0, х4 ? 0, х5 ? 0

=...

Построим симплекс-таблицу:

- х1 - х2

х3 273 3 2

х4 300 3 3

х5 380 2 5

Z 0 -4 -5

Этой симплекс-таблице соответствует опорное решение:

При этом целевая функция принимает значение:...

Так как в последней строке симплекс-таблице имеются отрицательные элементы, следовательно, план не оптимален.

Построим новую симплекс-таблицу.

Выбираем: ключевой столбец - "?5", (последний)

ключевая строка - "1" -.... (третья)

Ключевой элемент - "5".

- х1 - х2

х3 273 3 2

х4 300 3 3

х5 380 2 5

Z 0 -4 -5

Получаем новую симплекс-таблицу:

- х1 - х5

х3 121 2,2 -0,4

х4 72 1,8 -0,6

х2 76 0,4 0,2

Z 380 -2 1

Так как в последней строке есть отрицательный элемент, то полученное решение не оптимально.

Построим новую симплекс-таблицу.

Выбираем: ключевой столбец - "?2", (второй)

ключевая строка - "1,8" -... (вторая)

Ключевой элемент - "1,8".

- х4 - х5

х3 33 -1,22 0,33

х1 40 0,56 -0,33

х2 60 -0,22 0,33

Z 460 1,11 0,33

В последней строке нет отрицательных элементов. Полученный план оптимален

При этом целевая функция принимает значение:...

Ответ:...

Задача 3.6

Условия транспортной задача заданы в виде таблицы:

Вj Ai 90 120 110 130

105 12 9 7 11

165 4 3 12 2

180 5 17 9 4

Требуется:

1. Дать содержательную постановку ТЗ

2. Составить математическую модель

3. Найти первоначальный опорный план:

- методом северо-западного угла

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

4. сравнить эти опорные планы и определить является ли "лучший" план оптимальным

5. Найти оптимальное решение и соответствующее значение целевой функции

6. Решить задачу в предположении, что необходимо учитывать еще производственные затраты. Выяснить как повлияет учет производственных затрат на решение ТЗ.

Решение:

Исходные параметры модели ТЗ

1) n - количество пунктов отправления, m - количество пунктов назначения.

2)... - запас продукции в пункте отправления... (...) [ед. прод.].

3)... - спрос на продукцию в пункте назначения... (...) [ед. прод.].

4)... - тариф (стоимость) перевозки единицы продукции из пункта отправления... в пункт назначения... [руб./ед. прод.].

Искомые параметры модели ТЗ

1)... - количество продукции, перевозимой из пункта отправления... в пункт назначения... [ед. прод.].

2)... - транспортные расходы на перевозку всей продукции [руб.].

Составим транспортную матрицу задачи

Поставщики потребители запасы

12 9 7 11 105

4 3 12 2 165

5 17 9 4 180

потребление 90 120 110 130

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

Зададим ограничения:

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

и.........

Следовательно, данная транспортная задача закрытая.

Найдем исходное решение по методу северо-западного угла

Поставщики потребители запасы

90 12 15 9 7 11 105

4 105 3 60 12 2 165

5 17 50 9 130 4 180

потребление 90 120 110 130

Стоимость перевозки при исходном решении составляет:

Найдем исходное решение по методу минимального тарифа.

Поставщики потребители запасы

12 9 105 7 11 105

4 35 3 12 130 2 165

90 5 85 17 5 9 4 180

потребление 90 120 110 130

Стоимость перевозки при исходном решении составляет:

Сравнивая полученные планы приходим к выводу, что опорный план составленный по методу минимального элемента лучше, т.к. затраты на перевозку продукции составляют 3040 ден. ед., а по плану северо-западного угла 3220 ден. ед.

Проверим план, составленный по методу минимального элемента на оптимальность.

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

Пусть..., тогда находим остальные потенциалы, получаем:

?12...2

3...15...7...14

Проверим условия оптимальности для незаполненных клеток:

=...

0+15=15>9

=...

=...

=...

=...

Условия оптимальности не выполнены для клеток (1,2), (1,4) и (3,4). Следовательно, построенный план не оптимален.

Выполним перераспределение груза, получим новый опорный план.

Поставщики потребители запасы

12 9 105 7 11 105

4 120 3 12 45 2 165

+ ?

90 5 17 5 9 85 4 180

? +

потребление 90 120 110 130

Стоимость перевозки при исходном решении составляет:

Проверим план, на оптимальность. Вычислим потенциалы... и....

Пусть..., тогда находим остальные потенциалы, получаем:

0...2

3...3...7... 2

Проверим условия оптимальности для незаполненных клеток:

=...

=...

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

Ответ:......

6) Затраты на производство единицы продукции в каждом i-м пункте производства известны и равны..., i=1,2,3. Стоимости перевозки единицы груза от каждого i-го производителя каждому j-му потребителю известны и равны..., i=1,2,3, j=1,2,3,4. Требуется составить план сокращения (размещения) производства, обеспечивающий минимальные производственно-транспортные затраты.

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

Зададим производственные затраты:.... Тогда матрица стоимостей будет иметь вид:

Воспользуемся решением предыдущего пункта:

Поставщики потребители запасы

13 10 105 8 12 105

6 120 5 14 45 4 165

90 8 20 5 12 85 7 180

потребление 90 120 110 130

Стоимость затрат при исходном решении составляет:

Проверим план, на оптимальность. Вычислим потенциалы... и....

Пусть..., тогда находим остальные потенциалы, получаем:

1...4

4...4...8...3

Проверим условия оптимальности для незаполненных клеток:

=...

=...

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

Оптимальный план перевозок -...

целевая функция -...(ден.ед.).

Затраты на производство составляют:...(ден.ед.).

Транспортные расходы:...(ден.ед.).

Задача 4.6

Решить задачу о назначениях. Составить математическую модель задачи. Решить задачу в ручную и дать интерпретацию результатов.

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

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

Решение:

1) Сформулируем задачу о назначениях:

Имеется n работ и n предприятий для их выполнения. Затраты j-го предприятия на выполнение i-й работы равны.... Каждое предприятие может быть назначено только на одну работу, и каждая работа может быть выполнена только одним предприятием. Требуется найти назначение предприятий на работы, при котором суммарные затраты на выполнение работ минимальны.

Эта задача заключается в выборе перестановки из n чисел: (i1, i2...in), ij=..., -обеспечивающей экстремум функции... ? min.

Найдем решение данной задачи венгерским методом.

Составим матрицу С:

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

Получили следующие назначения:

1 предприятие - 1 вид изделий

2 предприятие - 2 вид изделий

3 предприятие - 4 вид изделий

4 предприятие - 3 вид изделий

Суммарные затраты при этом составляют:... ден. ед.

2) Имеется n работ и n предприятий для их выполнения. Производительность j-го предприятия на выполнение i-й работы равно.... Каждое предприятие может быть назначено только на одну работу, и каждая работа может быть выполнена только одним предприятием. Требуется найти назначение предприятий на работы, при котором суммарная производительность фирмы была максимальной.

Эта задача заключается в выборе перестановки из n чисел: (i1, i2...in), ij=..., -обеспечивающей экстремум функции... ? max.

Найдем решение данной задачи венгерским методом.

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

Получили следующие назначения:

1 предприятие - 3 вид изделий

2 предприятие - 4 вид изделий

3 предприятие - 1 вид изделий

4 предприятие - 2 вид изделий

Суммарная производительность при этом составляет:... ден. ед.