Математическое программирование (183500)

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

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


,




Решение


1) Многоугольник решений.

Найдем точки, через которые пройдут предельные прямые [1, c. 20].








Строим многоугольник решений.



2) Оптимальные точки.

Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что Zmin находится в точке A, Zmax – в точке C.


3) Вычисление координат экстремумов.

Точка A – пересечение прямых L1 и L3:





Точка C – пересечение прямых L2 и L3:





4) Подсчет оптимальных значений.







Ответ: 88/3, 46.


2.4. Для изготовления 2-х видов продукции P1 и P2 используется 3 вида ресурсов R1, R2, R3. Запасы ресурсов, нормы их использования и прибыль от реализации единицы продукции приведены в таблице. Найти план производства продукции, которой бы при заданных условиях обеспечивал наибольшую прибыль.

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


Pi

Ri

Р1

Р2

Запасы

ресурсов

R1

2

5

80

R2

4

3

91

R3

1

4

68

Прибыль

15

12



Решение

Составим математическую модель задачи. Искомый выпуск продукции P1 обозначим через x1, продукции P2 – через x2. Поскольку есть ограничение на выделенные ресурсы каждого вида, переменные x1, x2 должны удовлетворять такой системе неравенств:





Общая стоимость продукции при этом составляет: z = 15x1 + 12x2 .

По своему экономическому содержанию переменные x1, x2 больше 0.

Следовательно, приходим к математической задаче: среди всех неотрицательных решений системы неравенств нужно найти такое, при котором функция z примет максимальное значение.

Решим задачу графическим способом.

1) Многоугольник решений

Найдем точки, через которые пройдут предельные прямые [1, c. 20].









Строим многоугольник решений.



2) Оптимальные точки.

Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что Fmin находится в точке O, Fmax - в точке C.

3) Вычисление координат экстремумов.

Точка C - пересечение прямых L1 и L2:




4) Подсчет оптимальных значений.





Ответ: 4881/14.


Решим задачу ЛП симплекс-методом [1, c. 30].

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем к ограничениям-уравнениям. Введем дополнительные 3 переменные – x3, x4, x5, в результате чего ограничения запишутся в виде уравнений:





Построим начальную симплекс-таблицу, где Q – неотрицательное отношение столбца плана к ключевому столбцу.


Базис

Cб

План

15

12

0

0

0

Q

x1

x2

x3

x4

x5

1

x3

0

80

2

5

1

0

0

40

2

x4

0

91

4

3

0

1

0

91/4

3

x5

0

68

1

4

0

0

1

68

4



0

-15

-12

0

0

0


Cтолбик 1 есть ключевым, поскольку он содержит минимальный отрицательный элемент 

Строка 2 есть ключевой, поскольку в ней минимальное Q2=91/4.

Ключевой элемент находится на их пересечении и равный числу 4.

Вместо вектора x4 , который выводим из базиса, вводим вектор x1.

Делим ключевую строку на ключевой элемент 4.

Умножаем его на 15 и добавляем к 4 строке.

Умножаем его на -2 и добавляем к 1 строке.

Умножаем его на -1 и добавляем к 3 строке.

Получим следующую симплекс-таблицу.


Базис

Cб

План

15

12

0

0

0

Q

x1

x2

x3

x4

x5

1

x3

0

69/2

0

7/2

1

-1/2

0

69/7

2

x1

15

91/4

1

3/4

0

1/4

0

91/3

3

x5

0

181/4

0

13/4

0

-1/4

1

181/13

4



1365/4

0

-3/4

0

15/4

0


Cтолбик 2 есть ключевым, поскольку он содержит минимальный отрицательный элемент 

Строка 1 есть ключевой, поскольку в ней минимальное Q1=69/7.

Ключевой элемент находится на их пересечении и равный числу 7/2.

Вместо вектора x3 , который выводим из базиса, вводим вектор x2.

Делим ключевую строку на ключевой элемент 7/2.

Умножаем его на 3/4 и добавляем к 4 строке.

Умножаем его на -3/4 и добавляем к 2 строке.

Умножаем его на -13/4 и добавляем к 3 строке.

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

Базис

Cб

План

15

12

0

0

0

x1

x2

x3

x4

x5

1

x2

12

69/7

0

1

2/7

-1/7

0

2

x1

15

215/14

1

0

-3/14

5/14

0

3

x5

0

185/14

0

0

-13/14

3/14

1

4



4881/14

0

0

3/14

51/14

0





Составим двойственную задачу к данной [1, c. 88]. Ее коэффициенты складываются с исходной путем транспонирования. Систему ограничений составят коэффициенты оптимизирующей функции. Коэффициентами оптимизирующей функции z будут свободные члены исходной системы. Знаки неравенств изменятся на противоположные. Оптимизирующая функция – минимум функции. Двойственная задача будет заключаться в том, чтобы составить такой план производства, при котором затраты ресурсов будут минимальными.

Следовательно, через y1 обозначим стоимость единицы ресурса 1 вида или А1, y2 – стоимость единицы А2, y3 – стоимость единицы А3. Тогда – стоимость продукции Р1, которая не может быть дешевле чем 15 у.д.е. (условных денежных единиц), то есть первое неравенство: . Аналогично .


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

Файл
2340-1.rtf
101691.rtf
1946-1947.doc
69241.rtf
15058.rtf




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