Математическое програмирование (стр. 1 из 3)
Математическое программирование
Задача 1
Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.
Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.
Решение.
Данная задача является задачей линейного программирования. Под планом производства понимается: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Прибыль рассчитывается по формуле:
Запишем математическую модель задачи:
Решим данную задачу графически.
Для этого построим на плоскости
области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.Три записанных выше неравенства ограничивают на плоскости многоугольник, ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).
График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10 ; 14). В этой точке целевая функция будет достигать максимума.
Решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные
. 
Составляем симплекс-таблицу:
| Базис | Cб | В | 2 | 3 | 0 | 0 | 0 |
| А1 | А2 | А3 | А4 | А5 | |||
| А3 | 0 | 48 | 2 | 2 | 1 | 0 | 0 |
| А4 | 0 | 38 | 1 | 2 | 0 | 1 | 0 |
| А5 | 0 | 54 | 3 | 1 | 0 | 0 | 1 |
| Fi - Ci | 0 | -2 | -3 | 0 | 0 | 0 |
В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – А3, А4, А5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
В следующий столбец
записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при i –й переменной.Под столбцом свободных членов записывается начальная оценка
Остальные оценки записываются под столбцами соответствующих векторов
. 
Преобразуем симплекс-таблицу следующим образом:
Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.
Шаг 2: Для отрицательных оценок вычисляются величины:
Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае -57 минимально, поэтому в качестве разрешающего элемента выбирается второй элемент второго столбца – 2 (выделен в таблице).
Шаг 3: Вторая строка таблицы делится на 2
От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.
От элементов строки 3 отнимает соответствующие элементы строки 2.
От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.
| Базис | Cб | В | 2 | 3 | 0 | 0 | 0 |
| А1 | А2 | А3 | А4 | А5 | |||
| А3 | 0 | 10 | 1 | 0 | 1 | - | 0 |
| А5 | 0 | 19 | 0,5 | 1 | 0 | 0,5 | 0 |
| А2 | 3 | 35 | 2,5 | 0 | 0 | -0,5 | 1 |
| Fi - Ci | 57 | -0,5 | 0 | 0 | 1,5 | 0 |
Таким образом, новыми базисными переменными становятся А3, А5, А2.
Возвращаемся к шагу 1 и повторяем весь процесс.
Проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А1.
Вычисляем:
Разрешающим элементом будет первый элемент первого столбца – 1.
Новыми базисными переменными становятся A5, A2, A1
От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 0,5.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 2,5.
От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -0,5.
| Базис | Cб | В | 2 | 3 | 0 | 0 | 0 |
| А1 | А2 | А3 | А4 | А5 | |||
| А5 | 0 | 10 | 1 | 0 | 1 | -1 | 0 |
| А2 | 3 | 14 | 0 | 1 | -0,5 | 1 | 0 |
| А1 | 2 | 10 | 0 | 0 | -2,5 | 2 | 1 |
| Fi - Ci | 62 | 0 | 0 | 1,5 | 1 | 0,5 |
Отрицательных оценок нет, то есть критерий оптимальности выполнен.
Таким образом, получается искомое значение целевой функции
F(10; 14; 0; 0; 10) = 62, т.е. возвращаясь к системе неравенств, получаем:
Ответы, полученные различными методами, совпадают.
Ответ: хопт = ( 10 , 14) Значение функции : F = 62
Задача 2
Имеются три пункта отправления А1,А2,А3 однородного груза и пять пунктов В1, В2, В3, В4, В5 его назначения. На пунктах А1,А2,А3 находится груз в количествах 50, 30, 70 тонн. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:
| Пункты отправления | Пункты назначения | ||||
| В1 | В2 | В3 | В4 | В5 | |
| А1 | 9 | 5 | 1 | 1 | 9 |
| А2 | 7 | 1 | 4 | 9 | 4 |
| А3 | 5 | 3 | 4 | 9 | 9 |
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;
2) для решения задачи использовать методы северо-западного угла и потенциалов.
Решение.
Составим математическую модель задачи:
Обозначим
- количество груза, перевезенного из пункта отправления i в пункт назначения j.Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):
При этом должна быть минимизирована целевая функция