Линейное программирование (183737)

Посмотреть архив целиком

Задача 1.

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

Вариант 2.

Найти наибольшее значение функции f(X) = x1 – 4x4 при ограничениях


x1 – x2 + x3 + x4 = 3

x1 + x2 + 2x3 = 5,

xj  0, j = 1, 2, 3, 4.


Решение.

Задача записана в каноническом виде, но не имеет необходимого числа единичных столбцов, т. е. не обладает очевидным начальным опорным решением.

Для нахождения опорного плана переходим к М-задаче:


f(X) = x1 – 4x4Мy1  max

x1 – x2 + x3 + x4 = 3

x1 + x2 + 2x3 + y1 = 5,

xj  0, j = 1, 2, 3, 4; y1 0.


Очевидное начальное опорное решение (0; 0; 0; 3; 5).

Решение осуществляется симплекс-методом с искусственным базисом.

Расчеты оформим в симплекс-таблицах


Номер симплекс-таблицы

Базис


Cj


Ci

B

1

0

0

-4

-M

Q

A1

A2

A3

A4

P1

0

A4

-4

3

1

-1

1

1

0

3:1 = 3

P1

-M

5

1

1

2

0

1

5:2 = 2,5

j

-

-5M-12

-M-5

-M+4

-2M-4

0

0

 

1

A4

-4

1/2

1/2

-3/2

0

1


1/2:1/2=1

A3

0

5/2

1/2

1/2

1

0


5/2:1/2=1 

j

-

-2

-3

6

0

0


 

2

A1

1

1

1

-3

0

2


 

A3

0

2

0

2

1

-1


 2:2=1

j

-

1

0

-3

0

6


 

3

A1

1

4

1

0

3/2

1/2



A2

0

1

0

1

1/2

-1/2



j

-

4

0

0

3/2

9/2




Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в  - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P1, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P1 выводим из базиса, а А3 - вводим в базис.

При пересчете таблицы столбец Р1 далее можно не рассчитывать.

После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в  - строке есть отрицательные значения, в столбце А1.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А1 - вводим в базис.

После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в  - строке есть отрицательные значения, в столбце А2. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А3. В качестве направляющей строки возьмем А3. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А3 выводим из базиса, а А2 - вводим в базис.

После пересчета получаем симплекс-таблицу 3. Опорное решение, соответствующее симплекс-таблице 3 (4; 1; 0; 0; 0) – оптимально, так как в  - строке нет отрицательных значений.

Отбрасывая значения переменной y1, получаем оптимальное решение исходной задачи:

х1 = 4, х2 = 1; х3 = 0; х4 = 0; fmax = 14 + 01 + 00 – 40 = 4.

Задача 2.

Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.

Задание 2. Решить полученную задачу линейного программирования графическим методом.

Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

Вариант 2.

Предприятие производит полки для ванных комнат двух размеров А и Б. Служба маркетинга определили, что на рынке может быть реализовано до 550 полок в неделю, а объем поставляемого на предприятие материала, из которого делаются полки, равен 1200 м2 в неделю. Для каждой полки типов А и Б требуется 2 м2 и 3 м2 материала соответственно, а затраты станочного времени на обработку одной полки типа А и Б составляют соответственно 12 и 30 минут. Общий недельный объем станочного времени равен 160 часов, а прибыль от продажи каждой полки типа А и Б составляет 3 и 4 ден. единиц соответственно. Определить, сколько полок каждого типа следует выпускать в неделю для получения наибольшей прибыли.

Решение.

Задание 1.

Обозначим x1 и x2 количество полок типа А и Б, соответственно (план выпуска). Очевидно, x1, x2  0 и целые.

Так как объем реализации в неделю составляет до 550 полок, то x1 + x2  550.

Расход материала составит 2x1 + 3x2 м2, эта величина не должна превышать запаса материала 1200 м2. Следовательно, должно выполняться неравенство 2x1 + 3x2  1200.

Затраты станочного времени составят 0,2x1 + 0,5x2 час. и не могут быть больше недельного объема 160 час. Следовательно, должно выполняться неравенство 0,2x1 + 0,5x2  160. Чтобы не было дробей, умножим его на 10 и получим 2x1 + 5x2  1600.

Прибыль от реализации полок составит f(X) = 3x1 + 4x2 ден. единиц, и она должна быть наибольшей

Получаем экономико-математическую модель задачи:

Найти максимум функции f(X) при заданных ограничениях

f(X) = 3x1 + 4x2  max

x1 + x2  550

2x1 + 3x2  1200

2x1 + 5x2  1600

x1, x2  0, целые.

Задание 2.

Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.

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

Проведем прямую x1 + x2 = 550 через точки (0; 550) и (550; 0). Подставим в первое неравенство координаты точки (0; 0): 10 +10 = 0 < 550, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x1 + 3x2 = 1200 через точки (0; 400) и (600; 0). Подставим в первое неравенство координаты точки (0; 0): 20 + 30 = 0 < 1200, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x1 + 5x2 = 1600 через точки (0; 320) и (800; 0). Подставим в первое неравенство координаты точки (0; 0): 20 + 50 = 0 < 1600, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Множество допустимых решений – это многоугольник ABCDO.

Построим линию уровня целевой функции f(X) = 3x1 + 4x2

3x1 + 4x2 = 0 через точки (200; -150 ) и (-200; 150).

Вектор-градиент {3; 4} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение. На чертеже построен вектор, пропорциональный градиенту (60; 80), так как сам градиент имеет малый масштаб на чертеже.


Случайные файлы

Файл
55976.rtf
21641-1.rtf
186160.rtf
42305.rtf
27404-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.