Экономико-математические методы решения задач

Размещено на http://www.allbest.ru/

Математика. Экономико-математические методы

Задание 1. Решить задачу графическим методом

0.

L (x) = 4x1 + 6x2min при ограничениях

3x1 +x2?9,

x1+2x2 ?8,

x1? 0, x2? 0.

Решение

Т. к. x1, x2?0, то решение задачи располагается в Iчетверти.

Рассмотрим уравнение 3x1+x2?9

x1=0=>x2=9

x2=0 =>x1=3

Рассмотрим уравнение x1+2x2?8

x1=0=>x2=4

x2=0=>x1=8

Рассмотрим уравнение x1+6x2?12

x1=0=>x2=2

x2=0=>x1=12

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

Опускаем перпендикуляр.

Для нахождения значения нулевой функции необходимо подставить найденное значение целевой функции:

Подставим х1=2, х2=3 в целевую функцию:

minL (x) = 4*2+6*3

minL (x) =20

Задача решена.

Задание 2. Решить задачу симплексным методом

5.

Решение

Систему ограничений приводим к каноническому виду, т. е. к системе линейных уравнений, где число переменных больше числа уравнений (m > k). В этой системе обязательно найдутся переменные, которые можно выразить через другие переменные, а если это не так, то их можно ввести искусственно. В этом случае первые называются базисом или искусственным базисом, а вторые - свободными. Вводим искусственные базисные переменные x3, x4 и x5 следующим образом:

3x1+5x2+x3=18,

2x1- x2 +x4 =0,

5x1 - 3x2 +x5 = 15;

Неравенства преобразовались в равенства, благодаря добавленным переменные x3, x4, x5, которые являются неотрицательными величинами. Таким образом, привели систему к каноническому виду. Переменная x3 входит в первое уравнение с коэффициентом 1, а в два других - с коэффициентом 0, то же справедливо для переменных x4, x5 и соответствующих уравнений, что соответствует определению базиса, т. е. добавлено 3 дополнительные переменные и добавлен 1 искусственный базис

Выбран ключевой элемент (2, 1)

Выбран ключевой элемент (3, 4)

Решение задачи: бесконечное множество оптимальных планов

x* = k (0, 0) + (1-k) (3, 0)

L (x*) = 0

Задание 3. Решить транспортную задачу

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

Решение.

Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей Xi, j - перевозка между поставщиком Ai и потребителем Bj. Di, j - ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj. M - некоторое число, близкое к бесконечности e - некоторое число, близкое к нулю. Красным цветом будем отображать ограничения пропускных способностей коммуникаций между поставщиками и потребителями. Серым цветом будем отображать стоимости перевозок (тарифы). Исходная таблица:

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план для задачи с ограничениями. Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai Bj* - недостача в поставке груза потребителю Bj Di, j - ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj

Находим незанятую клетку с минимальным тарифом: (2, 1). Помещаем туда меньшее из чисел A2*=20, B1*=70 и D2, 1=M Находим незанятую клетку с минимальным тарифом: (1, 2). Помещаем туда меньшее из чисел A1*=70, B2*=60 и D1, 2=M Находим незанятую клетку с минимальным тарифом: (1, 1). Помещаем туда меньшее из чисел A1*=10, B1*=50 и D1, 1=M Находим незанятую клетку с минимальным тарифом: (3, 3). Помещаем туда меньшее из чисел A3*=100, B3*=60 и D3, 3=M Находим незанятую клетку с минимальным тарифом: (3, 1). Помещаем туда меньшее из чисел A3*=40, B1*=40 и D3, 1=M

Целевая функция L (x) =810

Решаем задачу c ограничениями методом потенциалов:

Этап 1

Так как суммарная величина нераспределенного груза/потребностей epsilon = 0, то текущий план является опорным планом транспортной задачи с ограничениями.

Этап 2

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci, j (i=1.. m, j=1.. n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V1=C1, 1-U1= 3 V2=C1, 2-U1= 2 U2=C1, 2-V1= -2 U3=C1, 3-V1= 7 V3=C3, 3-U3= -3 Определяем значения оценок Si, j=Ci, j- (Vj-Ui) для всех свободных клеток: Для случая Xi, j = 0 условие оптимальности оценки Si, j определяется следующим образом: Si, j>=0. Для случая Xi, j = Di, j условие оптимальности оценки Si, j определяется следующим образом: Si, j<=0.

Оценки Si, j для всех клеток, удовлетворяющих условию: Xi, j = 0 (неоптимальные выделены синим цветом) S1, 3 = c1, 3 - (v3 + u1) = 6. S2, 2 = c2, 2 - (v2 + u2) = 4. S2, 3 = c2, 3 - (v3 + u2) = 8. S3, 2 = c3, 2 - (v2 + u3) = -4. оценки Si, j для всех клеток, удовлетворяющих условию: Xi, j = Di, j (неоптимальные выделены красным цветом) Если имеются неоптимальные оценки и для случая Xi, j = 0, и для случая Xi, j = Di, j, то наиболее потенциальной (неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3, 2). Для нее оценка равна -4. Строим для этой клетки цикл, помечая клетки цикла знаками «плюс» и «минус».

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

Целевая функция L (x) = 650

Значение целевой функции изменилось на 160 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci, j (i=1.. m, j=1.. n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V1=C1, 1-U1= 3 V2=C1, 2-U1= 2 U2=C1, 2-V1= -2 U3=C2, 3-V2= 3 V3=C3, 3-U3= 1 Определяем значения оценок Si, j=Ci, j- (Vj-Ui) для всех свободных клеток: Для случая Xi, j = 0 условие оптимальности оценки Si, j определяется следующим образом: Si, j>=0. Для случая Xi, j = Di, j условие оптимальности оценки Si, j определяется следующим образом: Si, j<=0.

Оценки Si, j для всех клеток, удовлетворяющих условию: Xi, j = 0 (неоптимальные выделены синим цветом) S1, 3 = c1, 3 - (v3 + u1) = 2. S2, 2 = c2, 2 - (v2 + u2) = 4. S2, 3 = c2, 3 - (v3 + u2) = 4. S3, 1 = c3, 1 - (v1 + u3) = 4. оценки Si, j для всех клеток, удовлетворяющих условию: Xi, j = Di, j (неоптимальные выделены красным цветом) Так как все условия оптимальности выполнены, то полученный план является оптимальным. Транспортная задача решена.

Целевая функция L (x) = 650

целевая функция вектор

Размещено на Allbest.ru