Линейное программирование: формулировка задач и их графическое решение




страница1/3
Дата04.05.2016
Размер0.78 Mb.
  1   2   3

ЗАДАЧИ ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ

содержание:

Линейное программирование: формулировка задач

и их графическое решение............................................... 3


Линейное программирование: алгебраические методы

решения задач................................................................. 13


Линейное программирование: транспортная

модель.............................................................................. 22


Сети................................................................................. 30
Как определяются номера задач для самостоятельной

работы............................................................................. 36



Линейное Программирование: формулировка задач и их графическое решение
Пример 2.1.1. (Задача фирмы Reddy Mikks.) Небольшая фабрика фирмы Reddy Mikks изготовляет два вида красок: для внутренних (1) и наружных (Е) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используется два исходных продукта - А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн соответственно. Расходы А и В на 1 тонну соответствующих красок приведены ниже в таблице.


Исходный продукт

Расход исходных продуктов

(в тоннах на тонну краски)


Краска Е Краска 1

Максимально возможный запас, т

А

1

2

6

В

2

1

8

Изучение рынка сбыта показало, что суточный спрос на краску 1 никогда не превышает спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску 1 никогда не превышает 2 тонн в сутки. Оптовые цены одной тонны красок равны: 3 тыс. долларов для краски Е, 2 тыс. долларов для краски 1.

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?
Упражнение 2.1.1. Выполните применительно к рассматриваемой модели следующие операции.

(а) Запишите в математической форме каждое из сформулированных ниже ограничений.



  1. Суточный спрос на краску 1 превышает спрос на краску Е по крайней мере на 1 тонну.

  2. Суточный расход исходного продукта А не может превышать 6 тонн и быть меньше, чем 3 тонны.

  3. Спрос на краску 1 никогда не бывает меньше спроса на краску Е.

(б) Проверьте, являются ли допустимыми следующие решения.

1) Хе=1, Хi=4, 2) Хе=2, Хi=2, 3) Хе=10/3, Хi=4/3, 4) Хе=2, Хi=1, 5) Хе=2, Хi=-1.

(в) Рассмотрите допустимое решение Хе=2, Хi=2. Определите указанные ниже величины.

1) Остаток (неиспользованную часть) исходного продукта А.

2) Остаток исходного продукта В.

(г)Определите, какое из допустимых решений п. (б) является наилучшим.

(д)Каковы ваши предположения о количестве допустимых решений рассматриваемой задачи?



Упражнение 2.1.2.

(а) Определите пространство решений и найдите оптимальное решение задачи фирмы Reddy Mikks, считая, что каждое из указанных ниже условий заменяет, а не дополняет соответствующие исходные данные, причём все остальные заданные соотношения остаются неизменными. (Для получения решения и проверки ответов воспользуйтесь рис.2.1.)

1) Максимальный спрос на краску 1 равен 3 тонны в сутки.

2) Спрос на краску 1 не менее 2 тонн в сутки.

3) Спрос на краску 1 на 1 тонну превышает спрос на краску Е.

4) Допустимый расход исходного продукта В не меньше 8 тонн в сутки.

5) Допустимый суточный расход исходного продукта В не меньше 8 тонн, спрос

на краску 1 превышает спрос на краску Е не менее чем на 1 тонну.

(б) Используя рис.2.2, найдите оптимальные решения при следующих целевых функциях:

1) z=3Xe-Xi

2) z=3Xe+1,5Xi

3) z=Xe+3Xi

4) При условиях п. 2 задача имеет не единственное оптимальное решение. Каково значение целевой функции во всех оптимальных точках?


Упражнение 2.1.3.

(а) Используя рис.2.1, укажите связывающие, не связывающие и избыточные ограничения для каждого из указанных ниже условий.

1) Объем ресурса (2) увеличивается до предельного значения (равного 12 т).

2) Объем ресурса (3) уменьшается до минимально допустимого значения.

3) Объем ресурса (4) уменьшается до минимально допустимого значения.

(б) В исходных данных рис.2.3 только ограничение (1)(для ресурса А), имеющее вид Хе+2Хi<=6, замените ограничением 2Хt+3Хi<=10. Найдите оптимальное решение для новых условий и определите допустимый в этом случае прирост объёма продукта А и соответствующее приращение целевой функции (дохода) z.



Упражнение 2.1.5.

(а) Воспользовавшись рис.2.5, определите область изменения коэффициента Сi, в которой точка С по-прежнему будет оставаться единственной оптимальной точкой. Исходное значение Се=3 оставьте неизменным.

(б) Определите оптимальные угловые точки для случая, когда значение Сi начинает превосходить полученное в п. (а) максимальное значение.

(в) Пусть целевая функция z=3Xe+2Xi заменена на z=3Xe+Xi. В этом случае оптимальной угловой точкой будет точка В с координатами Хе=4 и Хi=0. Это означает, что краску 1 производить не целесообразно. При какой цене на краску Е станет выгодным производство краски 1?


задачи

2.1. Предприятие электронной промышленности выпускает две модели радиоприёмников, причём каждая модель производится на отдельной технологической линии. Суточный объём производства первой линии - 60 изделий, второй линии - 75 изделий. На радиоприёмник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприёмник второй модели - 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыли от реализации одного радиоприёмника первой и второй моделей равны 30 и 20 долларов соответственно.



Определите оптимальные суточные объёмы производства первой и второй моделей.

2.2. Процесс изготовления двух видов промышленных изделий состоит в последовательной обработке каждого из них на трех станках. Время использования этих станков для производства данных изделий ограничено 10 ч в сутки. Время обработки и прибыль от продажи одного изделия каждого вида приведены в таблице. Найдите оптимальные объёмы производства изделий каждого вида.







Время обработки 1 изделия, мин

Удельная

Изделие

станок 1

станок 2

станок 3

прибыль

1

10

6

8

2 долл.

2

5

20

15

3 долл.

2.3. Фирма имеет возможность рекламировать свою продукцию, используя местные радио- и телевизионную сети. Затраты на рекламу в бюджете фирмы ограничены величиной 1000 долларов в месяц. Каждая минута радиорекламы обходится в пять долларов, а каждая минута телерекламы - 100 долларов. Фирма хотела бы использовать радиосеть по крайней мере в два раза чаще, чем сеть телевидения. Опыт прошлых лет показал, что объём сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определите оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу, между радио- и телерекламой.


2.4. Фирма производит два вида продукции - А и В. Объём сбыта продукции вида А составляет не менее 60% общего объёма реализации продукции обоих видов. Для изготовления продукции А и В используется одно и то же сырьё, суточный запас которого ограничен величиной 100 фунтов. Расход сырья на единицу продукции А составляет 2 фунта, а на единицу продукции В - 4 фунта. Цены продукции А и В равны 20 и 40 долларам соответственно. Определите оптимальное распределение сырья для изготовления продукции А и В.
2.5. Фирма выпускает ковбойские шляпы двух фасонов. Трудоёмкость изготовления шляпы фасона 1 вдвое выше трудоёмкости изготовления шляпы фасона 2. Если бы фирма выпускала только шляпы фасона 1, суточный объём производства мог бы составить 500 шляп. Суточный объём сбыта шляп обоих фасонов ограничен диапазоном от 150 до 200 штук. Прибыль от продажи шляпы фасона 1 равна 8 долларам, а фасона 2 - 5 долларов. Определите, какое количество шляп каждого фасона следует изготавливать, чтобы максимизировать прибыль.
2.6. Найдите графическим методом пространство решений для следующей совокупности неравенств:

Х12<=4, 4X1+3X2<=12, -X1+X2>=1, X1+X2<=6; X1,X2<=0.

Какое из ограничений является избыточным? Приведите исходные условия к системе ограничений с меньшим числом неравенств, определяющих то же самое пространство решений.
2.7. Сформулируйте ограничения, связанные с пространством решений, изображенным на рис.2.10, и определите все избыточные ограничения.
2.8.Решите задачу:

максимизировать z=6X1-2X2

при ограничениях

Х12<=1, 3X1-X2<=6, X1,X2>=0,

Используя графический метод, покажите, что оптимальное решение допускает неограниченное увеличение переменных Х1 и Х2, не влияющее на значение целевой функции.
2.9. Решите следующую задачу ЛП:

максимизировать z=4X1+4X2

при ограничениях

2X1+7X2<=21, 7X1+2X2<=9, X1, X2>=0.

Найдите оптимальное решение (Х12) графически. Каков диапазон изменения коэффициентов целевой функции, в котором точка (Х12) остаётся оптимальной?
2.10. Решите следующую задачу графическим способом:

максимизировать z=5X1+6X2

при ограничениях Х1-2Х2>=2, -2X1+3X2>=2, X1,X2 не ограничены в знаке.

2.11. Рассмотрите следующую задачу:

максимизировать z=3X1+2X2

при ограничениях 2X1+X2<=2, 3X1+4X2>=12, X1,X2>=0.

Покажите графически, что допустимые экстремальные точки отсутствуют. Какой вывод можно сделать относительно поставленной задачи?
2.12. Решите графическим способом следующую задачу:

максимизировать z=5X1+2X2 при ограничениях X1+X2<=10, X1=5, X1, X2>=0.




2.13. Найдите координаты экстремальных точек пространства решений для задачи 2.12. Заменив ограничение Х1=5 на Х1<5, определите все допустимые экстремальные точки и найдите оптимум, вычисляя значения целевой функции в каждой из таких точек. Покажите, что ответ согласуется с решением, полученным графическим способом. Повторите указанную процедуру, заменив исходное ограничение Х1=5 на ограничение Х1>=5.


2.14. Используя пространство решений, показанное на рис.2.10 (задача 2.7), найдите оптимальные решения для следующих целевых функций:

(а) минимизировать z=2X1+6X2,

(б) максимизировать z=-3X1+4X2,

(в) минимизировать z=3X1+4X2,

(г) минимизировать z=X1-2X2,

(д) минимизировать z=X1,

(е) максимизировать z=X1,
2.15. Модель ЛП имеет следующий вид:

максимизировать z=5X1+3X2, при ограничениях X1+X2<=4 (ресурс 1), 5X1+2X2<=10 (ресурс 2), X1, X2>=0,

Определите:

(а) увеличение запаса ресурса 1, при котором соответствующее ограничение станет избыточным, и связанное с таким увеличением изменение целевой функции z,

(б) уменьшение запаса ресурса 2, при котором ограничение для ресурса 1, станет избыточным, и связанное с таким уменьшением изменение целевой функции z.
2.16. Оптимальное решение задачи 2.1 показывает, что запас элементов электронных схем и производительность технологической линии 1 являются дефицитными ресурсами, тогда как аналогичные ресурсы для линии 2 являются недефицитными. Требуется :

(а) определить предел увеличения производительности линии 1, превышение которого уже не будет улучшать значение целевой функции;

(б) определить предел уменьшения производительности линии 2, при котором полученное оптимальное решение останется неизменным;

(в) определить предел увеличения суточного запаса элементов электронных схем, при превышении которого улучшить значение целевой функции оказывается невозможным;

(г) обосновать решение задачи, исходя из удельной ценности ресурсов, и определить дефицитный ресурс, который имеет наибольший приоритет при возможности увеличения запасов ресурса.
2.17. Проанализируйте решение задачи 2.2 (изготовление двух изделий на трёх станках):

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

(б) для каждого полностью загруженного станка определите “ценность” единицы дополнительного фонда времени;

(в) какой из трёх станков имеет наибольший приоритет при возможности увеличения времени их загрузки?


2.18. Проанализируйте решение задачи 2.3. Определите предел увеличения месячной суммы расходов на рекламу, превышение которого уже не будет влиять на оптимальное решение. Рассмотрите полученный результат с точки зрения его использования в практических ситуациях.
2.19. Проанализируйте решение задачи 2.1. Оптимальному решению соответствуют суточный выпуск 60 радиоприёмников первой модели и 25 - второй модели, оптимальная величина прибыли 2300 долларов.

(а) Определите интервал изменения прибыли от продажи радиоприёмника первой модели, в котором оптимальное решение остаётся неизменным.

(б) Определите аналогичный интервал для приёмника второй модели.

(в) Найдите такое значение удельной прибыли для радиоприёмника первой модели, которое приведёт к получению оптимального решения, где оба ограничения, относящиеся к производительности линии станут несвязывающими. Удельную прибыль для второй модели считайте заданной и равной 20 долларам.

(г) Пусть удельные значения прибыли для первой и второй моделей изменяются одновременно. Определите интервал изменения отношения этих параметров, в котором полученное решение остаётся оптимальным.
2.20. Проанализируйте решение задачи 2.3. Определите, какое увеличение объёма сбыта, приходящееся на 1 мин использования радиорекламы, необходимо для создания условий, при которых все выделяемые средства целесообразно направить только на радиорекламу.
2.21. Изделия четырёх типов проходят последовательную обработку на двух станках. Время обработки одного изделия каждого типа на каждом из станков приведено в таблице.


Станок

Время обработки одного изделия, ч



тип 1

тип 2

тип 3

тип 4

1

2

3

4

2

2

3

2

1

2

Затраты на производство одного изделия каждого типа определяются как величины, прямо пропорциональные времени использования станков (в машино-часах). Стоимость машино-часа составляет 10 долларов для станка 1 и 15 долларов - для станка 2. Допустимое время использования станков для обработки изделий всех типов ограничено следующими значениями: 500 машино-часов - для станка 1 и 380 машино-часов для станка 2. Цены изделий типов 1, 2, 3 и 4 равны 65, 70, 55 и 45 долларов соответственно. Сформулируйте для приведённых условий задачу максимизации суммарной чистой прибыли.


2.22. Завод выпускает изделия трёх моделей (1, 11, и 111). Для их изготовления используются два вида ресурсов (А и В), запасы которых составляют 4000 и 6000 единиц. Расход ресурсов на одно изделие каждой модели приведен в таблице.


Ресурс

Расход ресурса на одно изделие данной модели




I

II

III

А

2

3

5

В

4

2

7

Трудоёмкость изготовления изделия модели 1 вдвое больше, чем изделия модели 11, и втрое больше, чем изделия модели 111. Численность рабочих завода позволяет выпускать 1500 изделий модели 1. Анализ условий сбыта показывает, что минимальный спрос на продукцию завода составляет200, 200 и 150 изделий моделей 1, 11 и 111 соответственно. Однако соотношение выпуска изделий моделей 1, 11 и 111 должно быть равно 3 : 2 : 5. Удельные прибыли от реализации изделий моделей 1, 11 и 111 составляют 30, 20 и 50 долларов соответственно. Сформулируйте для данных условий задачу определения объёмов выпуска изделий каждой модели, при которых прибыль будет максимальной.


2.23. Денежные средства могут быть использованы для финансирования двух проектов. Проект А гарантирует получение прибыли в размере 70 % на вложенный доллар через год. Проект В гарантирует получение прибыли в размере 2 долларов на каждый инвестированный доллар, но через два года. При финансирование проекта В период инвестиций должен быть кратным двум годам. Как следует распорядиться капиталом в 100 000 долларов, чтобы максимизировать суммарную величину прибыли, которую можно получить через три года после начала инвестиций? Сформулируйте данную задачу как задачу ЛП.

2.24. Минимально необходимое количество автобусов в 1-й час суток равно bi, i=1, 2,....., 24. Каждый автобус непрерывно используется на линии в течение 6 часов. Превышение числа автобусов в период i по сравнению с величиной bi приводит к дополнительным издержкам на один машино-час в размере Ci. Сформулируйте данную задачу как задачу минимизации общей величины дополнительных издержек.


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


Тип

самолёта


Вместимость (число пассажиров)

Количество самолётов

Количество рейсов в сутки на каждом маршруте










1

2

3

4

1

2

3



50

30

20



5

8

10



3

4

5



2

3

5



2

3

4



1

2

2



Суточный пасажиропоток

100

200

90

120

Стоимостные характеристики авиаперевозок:




Тип самолета


Эксплуатационные расходы на 1 рейс по данному маршруту, в долларах




1

2

3

4

1

2

3



Убыток от неудовлетворённого спроса (на одного неперевезённого пассажира)

1000

800


600

40


1100

900


800

50


1200

1000


800

45


1500

1000


900

70

Сформулируйте задачу линейного программирования, в которой требуется минимизировать сумму эксплуатационных расходов и потерь из-за неудовлетворённого спроса.
2.26. Для получения двух сплавов А и В используется четыре металла 1, 11, 111 и IV. Требования к содержанию этих металлов в сплавах А и В приведены ниже.


Сплав

Требования к содержанию металлов

А

В


Не более 80% металла I

Не более 30% металла II

Не менее 50% металла IV
От 40 до 60% металла II

Не менее 30% металла III

Не более 70% металла IV


Характеристики и запасы руд, из которых получаются металлы I, II, III и IV, указаны в таблице.




Руда

Максимальный

Состав, %

Цена,




запас, т

I

II

III

IV

Другие компоненты

долл./т

1

1000

20

10

30

30

10

30

2

2000

10

20

30

30

10

40

3

3000

5

5

70

20

0

50

Пусть цена 1 т сплава А равна 200 долларам, а 1 т сплава В - 300 долларам. Сформулируйте задачу ЛП, в которой требуется максимизировать прибыль от продажи сплавов А и В. (Указание: обозначьте через Xijk количество тонн металла i, получаемого из руды j и используемого для изготовления сплава k. )


2.27. Требуется распределить имеющиеся денежные средства; по четырём альтернативным вариантам. Игра имеет три хода. В таблице приведены размеры выигрыша (или проигрыша) на каждый доллар, вложенный в соответствующий альтернативный вариант, для каждого из трёх исходов. У игрока имеется 500 долларов,


Исход

Выигрыш (или проигрыш) на 1 долл., вложенный в данный вариант




1

2

3

4

1

-3

4

-7

15

2

5

-3

9

4

3

3

-9

10

-8

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

(Примечание: Отдача от вложенных средств может быть отрицательной, нулевой или положительной.)

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ: АЛГЕБРАИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ


3.1. Приведите следующую линейную оптимизационную модель к стандартной форме:

максимизировать: z=2X1+3X2+5X3

при ограничениях: X1+X2-X3>=-5, -6X1+7X2-9X3<=4, X1+X2+4X3=10, X1,X2>=0, X3 не ограничена в знаке.
3.2. Изменив модель, использованную в задаче 3.1, в соответствии с каждым из приведённых ниже условий (используемых независимо друг от друга), приведите её к стандартной форме.

(а) Первое ограничение имеет вид X1+X2-X3>=-5

(б) Второе ограничение имеет вид -6X1+7X2-9X3<=4

(в) Третье ограничение имеет вид X1+X2+4X3=10

(г) Х>=0.

(д) Хi не имеет ограничения в знаке.

(е) Целевая функция z=2X1+3X2+5X3 полежит минимизации.

(ж) Условия пп. (а), (б) и (в) вводятся одновременно.

(з) Условия пп. (в), (г), (д) и (е) вводятся одновременно.
3.3. Задано трёхмерное пространство решений задачи ЛП с экстремальными точками А, В, С,...., J (рис 3.10). Координаты экстремальных точек указаны на рисунке.

(а) Являются ли следующие пары экстремальных точек смежными?

1) А, В, 2) В, D, 3) Е, Н, 4) А, I.

(б) Пусть процесс решения задачи с помощью симплекс-метода начинается с точки А и заканчивается нахождением оптимума, соответствующего точке Н. Могут ли итерации симплекс-метода привести к оптимуму в точке Н путём реализации следующих переходов от одной экстремальной точки к другой?

1)ABGH, 2) AFJH, 3)ACIH, 4) AIH, 5) ADGH, 6) ADABGH, 7) ACFDABGH
3.4. На рис. 3.10 все ограничения, определяющие пространство решений, имеют знак <=. Пусть S1, S2, S3, S4 - остаточные переменные, ассоциированные с ограничениями, которые представляются плоскостями CEIJF, BEIHG, DFJHG и HIJ соответственно. Идентифицируйте базисные и не базисные переменные, соответствующие каждой допустимой экстремальной точке. (Указание: подразумевается, что Х1, Х2, Х3>=0.)
3.5. Для условий задачи 3.4 определите включаемые в базис и исключаемые из базиса переменные для итерации, соответствующих переходам между следующими парами экстремальных точек:

(а) DB, (б) EI, (в) FJ, (г) DG.




3.6. Рассмотрите следующую задачу:

максимизировать z=2X1-4X2+5X3-6X4

при ограничениях

X1+4X2-2X3+8X4<=2,

-X1+2X2+3X3+4X4<=1,

X1, X2, X3, X4>=0.
(а) Определите максимальное количество возможных базисных решений.

(б) Идентифицируйте допустимые экстремальные точки.

(в) Найдите допустимое базисное решение.

3.7. Пусть при решении задачи, условия которой соответствуют рис. 3.10, исходной точкой (начальным решением) является точка А. Определите переменную, вводимую в базис на первой итерации, значение этой новой базисной переменной и улучшение значения максимизируемой целевой функции, если она имеет следующий вид:

(а) z=X1-2X2+3X3;

(б) z=5X1+2X2+4X3;

(в) z=-2X1+7X2+2X3;

(г) z= X1+X2+X3.


3.8. Пусть для условий, соответствующих рис. 3.11, задана следующая целевая функция: максимизировать z=3X1+6X2

а) Найдите графическим способом оптимальную экстремальную точку.

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

в) Полагая, что реализация симплекс-метода начинается с точки А,

определите вводимую в базис переменную и отношения, используемые при проверке условия допустимости, если целевая функция имеет вид максимизировать z=4X1+X2

г) Выполните задание п.(в), используя следующую целевую функцию: максимизировать z=X1+2X2

д) Применительно к условиям пп. (в) и (г) определите результирующее улучшение целевой функции.

3.9. Дана следующая система уравнений:

X1+2X2-3X3+5X4+X5=4,

5X1-2X2+6X4+X6=8,

2X1+3X2-2X3+3X4+X7=3,

-X1+X3+2X4+X8=0,X1,X2, ...,X8>=0

Известно начальное базисное решение (X5,...,X8). В базис вводится переменная X1. Какая из переменных предыдущего базиса должна стать нулевой небазисной переменной, чтобы все переменные остались неотрицательными, и каково значение X1 в новом базисном решении? Дайте ответ на поставленные вопросы для случаев, когда в базис вводятся переменные X2, X3, X4.
3.10. В нижеследующей таблице приведены результаты некоторой итерации симплекс-метода


Базисные




























переменные

x1

x2

x3

x4

x5

x6

x7

x8

Решение

x8



0

3

0

-2

-3

-1

5

1

12

x1



1

-1

0

0

6

-4

0

0

0

(а) Определите исключаемую из базиса переменную, если в базис вводятся переменные: 1) x2, 2) x4, 3) x5, 4) x6, 5) x7

(б) Для каждого из случаев, перечисленных в п. (а), определите результирующие увеличение или уменьшение целевой функции z.
3.11.Решите следующие системы линейных уравнений, используя процедуру преобразования строк (Жордана - Гаусса), являющуюся составной частью симплекс-метода.

(а) -3x1 + 2x2 + 5x3 = 5,

4x1 + 3x2 + 2x3 = 8,

x1 - x2 +3x3 = 10.

(б) x2 + x3 = 5,

2x1 + x2 - x3 = 12,

x1 + 3x2 + 4x3 = 10.
3.12.Дана следующая совокупность ограничений

x1 + 7x2 + 3x3 + 7x4 <= 46,

3x1 - x2 + x3 + 2x4 <= 8,

2x1 + 3x2 - x3 + x4 <= 10.

Решите задачу ЛП симплекс-методом при следующих целевых функциях:

(а) максимизировать z = 2x1 + x2 - 3x3 + 5x4;

(б) максимизировать z = -2x1 + 6x2 + 3x3 - 2x4;

(в) максимизировать z = 3x1 - x2 + 3x3 + 4x4;

(г) минимизировать z = 5x1 - 4x2 + 6x3 + 8x4;

(д) минимизировать z = 3x1 - 6x2 - 2x3 + 4x4.


3.13.Решите следующую задачу, анализируя и обосновывая ход решения, исходя из положений, на которых базируется симплекс-метод:

максимизировать z = 5x1 - 6x2 + 3x3 - 5x4 + 12x5 при ограничениях

x1 + 3x2 + 5x3 + 6x4 + 3x5 <= 90,

x1 , x2 , x3 , x4 , x5 >= 0.


3.14.Рассмотрите следующую задачу ЛП:

минимизировать z = x1 - 3x2 - 2x3 при ограничениях

3x1 - x2 + 2x3 < 7,

-2x1 + 4x2 < 12,

-4x1 + 3x2 + 8x3 < 10,

x1 , x2 , x3 >= 0.

(а) Решите задачу симплекс-методом, выбирая на каждой итерации в качестве новой базисной переменной ту небазисную переменную, которая в z - уравнении имеет наибольший положительный коэффициент.

(б) Решите задачу симплекс-методом, выбирая в качестве новой базисной переменной ту небазисную переменную, которая имеет в z - уравнении наименьший положительный коэффициент.

(в) Сравните количество итераций, потребовавшихся для решения в пп. (а) и (б).

(г) Если требование минимизации целевой функции заменяется требованием ее максимизации, исходную целевую функцию умножают на -1 и при реализации симплекс-метода используют решение, соответствующее процессу максимизации. Как изменяются при этом вычислительные процедуры симплекс-метода по сравнению со случаем, когда целевая функция должна быть минимизирована?


3.15.Решите следующую задачу, используя для получения начального (допустимого) базисного решения переменные x4 , x5 и x6

максимизировать

z = 3x1 + x2 + 2x3 при ограничениях

12x1 + 3x2 + 6x3 + 3x4 = 9,

8x1 + x2 - 4x3 + 2x5 = 10,

3x1 - x6 = 0,

x1 , x2 , ... , x6 >= 0.
3.16.Рассмотрите систему ограничений:

-2x1 + 3x2 = 3, (1)

4x1 + 5x2 >= 10, (2)

x1 + 2x2 <= 5, (3)

6x1 + 7x2 <= 3, (4)

4x1 + 8x2 >= 5, (5)

Пусть x1 , x2 >=0. С помощью подстановки искусственных переменных, используемой в М-методе, составьте начальное z - уравнение для каждого из следующих случаев:

(а) максимизировать z = 5x1 + 6x2 при ограничениях (1), (3) и (4);

(б) максимизировать z = 2x1 - 7x2 при ограничениях (1), (2), (4) и (5);

(в) минимизировать z = 3x1 + 6x2 при ограничениях (3), (4) и (5);

(г) минимизировать z = 4x1 + 6x2 при ограничениях (1), (2) и (5);

(д) минимизировать z = 3x1 + 2x2 при ограничениях (1) и (5).


3.17.С помощью М-метода решите задачу ЛП, имеющую систему ограничений

x1 + x2 + x3 = 7,

2x1 - 5x2 + x3 >= 10,

x1, x2, x3 >= 0,

и следующую целевую функцию:

(а) максимизировать z = 2x1 + 3x2 - 5x3,

(б) минимизировать z = 2x1 + 3x2 - 5x3,

(в) максимизировать z = x1 + 2x2 + x3,

(г) минимизировать z = 4x1 - 8x2 + 3x3.
3.18.Рассмотрите следующую задачу:

максимизировать z = x1 + 5x2 + 3x3

при ограничениях

x1 + 2x2 + x3 = 3,

2x1 - x2 = 4,

x1, x2,x3 >= 0.

Пусть R соответствует искусственной переменной, вводимой в уравнение второго ограничения. Решите задачу, используя в начальном базисном решении переменные x3 и R.
3.19.Рассмотрите следующую задачу:

минимизировать z = 2x1 + 4x2 + 4x3 - 3x4

при ограничениях

x1 + x2 + x3 = 4,

x1 + 4x2 + x4 = 8,

x1, x2, x3, х4 >= 0.

Найдите оптимальное решение, используя в начальном базисном решении переменные х3 и х4.
3.20.Решите следующую задачу, используя в начальном допустимом базисном решении переменные х3 и х4:

минимизировать z = 3x1 + 2x2 + 3x3

при ограничениях

x1 + 4x2 + x3 >= 7,

2x1 + x2 + x4 >= 10,

x1, x2, x3, х4 >= 0.


3.21.Применительно к каждому из случаев, перечисленных в задаче 3.16, постройте целевую функцию для этапа 1 двухэтапного метода решения.
3.22.Решите задачу 3.17 с помощью двухэтапного метода и сравните количество выполненных итераций при решении задачи М-методом
3.23.Рассмотрите следующую задачу ЛП:

максимизировать z = с1x1 + с2x2

при ограничениях

а11x1 + а12x2 <= b1,

a21x1 + a22x2 <= b2,

x1, x2 >= 0,

где 1<= c1<=3, 4<=c2<=6, -1<=a11<=3, 2<=a12<=5, 8<=b1<=12, 2<=a21<=5, 4<=a22<=6, 10<=b2<=14. Найдите нижнюю и верхнюю границы оптимального значения z. (Указание. Более ограниченному пространству решений соответствует меньшее значение z.)
3.24. Рассмотрите следующую задачу:

максимизировать z = x1 + 2x2 + 3x3

при ограничениях

x1 + 2x2 + x3 <= 10,

x1 + x2 <= 5,

x1 <= 1,

x1, x2, x3 >= 0.

Найдите по крайней мере три альтернативных оптимальных базисных решения. Какой вид будет иметь общее выражение для всех небазисных оптимальных решений, “охватываемых” полученными базисными решениями?


3.25.Пусть решению задачи ЛП соответствуют следующие четыре оптимальные точки:
123)=(1,2,5),(6,1,3),(4,2,1),(2,1,2).
Какой вид имеет общее выражение для всех альтернативных базисных и небазисных решений?

3.26.Расмотрите следующую задачу ЛП:

максимизировать z = 2x1 - 5x2 + 3x3

при ограничениях

x1 - x2 + 5x3 <= 10,

2x1 - x2 + 3x3 <= 40,

x1, x2, x3 >= 0.
Покажите, что задача имеет альтернативные оптимальные решения, причем все они являются небазисными. Какой вывод можно сделать относительно пространства решений и целевой функции? Покажите, что оптимальные значения базисных переменных можно сделать сколь угодно большими, тогда как значение z остается постоянным.
3.27.Расмотрите следующую задачу:

максимизировать z = 3x1 + x2

при ограничениях

x1 + x2 <= 5,

x1 + x2 - x3 <= 2,

7x1 + x2 - 5x3 < 20,

x1, x2, x3 > 0.
Покажите, что оптимальное решение - вырожденное и что задача имеет три альтернативных решения, причем все они являются небазисными.
3.28.Условия ЛП таковы:

максимизировать z = 20x1 + 10x2 + x3

при ограничениях

3x1 - 3x2 + 5x3 <= 50,

x1 + x3 <= 10,

x1 - x2 + 4x3 <= 20,

x1, x2, x3 >= 0.

В каком направлении пространство решений не ограничено? Какой вывод можно сделать относительно оптимального решения задачи, не проводя дополнительных вычислений?


3.29.Расмотрите следующую задачу:

максимизировать z = 3x1 + 2x2 + 3x3

при ограничениях

2x1 + x2 + x3 <= 2,

3x1 + 4x2 + 2x3 >= 8,

x1, x2, x3 >= 0.

Используя М-метод, покажите, что в оптимальном решении может фигурировать искусственная базисная переменная, равная нулю, т.е. существует допустимое оптимальное решение.
3.30.Расмотрите следующую задачу ЛП, связанную с распределением ресурсов:

максимизировать z = 3x1 + 2x2 (прибыль)

при ограничениях

4x1 + 3x2 <= 12 (ресурс 1),

4x1 + x2 <= 8 (ресурс 2),

4x1 - x2 <= 8 (ресурс 3),

x1, x2 >= 0.

Симплекс-таблица, соответствующая оптимальному решению задачи:




Базисные



















переменные

x1

x2

x3

x4

x5

Решение

z

0

0

5/8

1/8

0

17/2

x2

0

1

1/ 2

-1/2

0

2

x5



0

0

1

-2

1

4

(а) Определите статус каждого ресурса.

(б) Определите ценность каждого ресурса.

(в) Используя данные о ценности каждого ресурса, определите запас какого из них следует увеличить в первую очередь.

(г) Определите максимальный интервал изменения запасов ресурса 1, в пределах которого текущее решение остается допустимым.

(д) Выполните задание п. (г) применительно к ресурсу 2.

(е) Для пп. (г) и (д) определите соответствующее изменение оптимальных значений z.

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

(з) Выполните задание п. (ж) применительно к переменной х2.
3.31. Рассмотрите следующую линейную оптимизационную модель распределения ресурсов:

максимизировать z = 2x1 + 4x2 (прибыль)

при ограничениях

x1 + 2x2 <= 5 (ресурс 1),

x1 + x2 <= 4 (ресурс 2),

x1, x2 >= 0.

Симплекс-таблица, соответñтвующая оптимуму, имеет вид


Базисные
















переменные

x1

x2

x3

x4

Решение

z

0

0

2

0

10

x2

1/ 2

1

1/ 2

0

5/2

x4

1/ 2

0

-1/ 2

1

3/2

(а) Определите статус ресурса (дефицитный, недефицитный).

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

(в) Используя результаты, полученные в п. (б). Найдите соответствующие интервалы изменения оптимальных значений z.

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

(д) Выполните задание в п. (г) применительно к переменной х2.
3.32.Расмотрите следующую линейную оптимизационную модель распределения ресурсов:

максимизировать z = 3x1 + 2х2 + 5x3 (прибыль)

при ограничениях x1 + 2x2 + х3 < 430 (ресурс 1),

3x1 + 2x3 < 460 (ресурс 2),

x1 + 4x2 < 420 (ресурс 3),

x1, x2, х3 >= 0.


В результате решения задачи получена симплекс-таблица:

Базисные






















переменные

x1

x2

x3

x4

x5

x6

Решение

z

4

0

0

1

2

0

1350

x2

-1/4

1

0

1/ 2

-1/4

0

100

x6



2

0

0

-2

1

1

20

(а) Определите, остается ли полученное решение допустимым в каждом из следующих случаев. Если да, то найдите соответствующие значения х1, х2, х3, z

  1. Запас ресурса 1 уменьшен до 400 единиц.

  2. Запас ресурса 1 увеличен до 500 единиц.

  3. Запас ресурса 2 уменьшен до 450 единиц.

  4. Запас ресурса 3 увеличен до 440 единиц.

  5. Запас ресурса 3 уменьшен до 380 единиц.

(б) Определите, останется ли полученное решение оптимальным, если в целевой функции модели



  1. коэффициент при х1 уменьшить до 2;

  2. коэффициент при х1 увеличить до 9;

  3. коэффициент при х2 увеличить до 5;

  4. коэффициент при х2 уменьшить до 1.

3.33.Определите оптимальные значения х1 и х2 при следующих изменениях задачи 3.30 запаса ресурса 1 увеличен на 2 единицы и на 1 единицу уменьшен запас ресурса 2.
3.34.Пусть в задаче 3.31 изменены запасы обоих ресурсов, причем изменение для ресурса 1 составляет D1 единиц, а для ресурса 2 равняется D2 единицам. Найдите соотношение для параметров D1 и D2, при котором полученное решение остается оптимальным.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ: ТРАНСПОРТНАЯ МОДЕЛЬ


5.1.Три нефтеперерабатывающих завода с максимальной ежедневной производительностью в 6, 5 и 8 млн. галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на одну милю, рассчитанная с учетом длины трубопровода, составляет 1 цент на 100 галлонов. В таблице расстояний, приведенной ниже, показано, что завод 1 не связан с хранилищем 3. Сформулируйте соответствующую транспортную задачу.








Бензохранилища







1

2

3




1

120

180

-

Заводы

2

300

100

80




3

200

250

120

5.2.Пусть в задаче 5.1 производительность нефтеперерабатывающего завода 3 снизилась до 6 млн. галлонов. Кроме того, обязательно полное удовлетворение спроса бензохранилища 1, а недопоставки в хранилища 2 и 3 штрафуются 5 центами за каждый галлон. Сформулируйте соответствующую транспортную задачу.


5.3.Пусть в задаче 5.1 ежедневный спрос хранилища 3 падает до 4 млн. галлонов. Избыток продукции на нефтеперерабатывающих заводах 1 и 2 должен переправляться на грузовиках в другие хранилища. Соответствующие средние транспортные издержки составляют 1,5 долл. за 100 галлонов при перевозке с завода 1 и 2,2 долл. при перевозке с завода 2. Завод 3 может использовать избыток бензина для нужд своего химического производства. Сформулируйте соответствующую транспортную задачу.
5.4.Автомобили перевозят в трейлерах из трех центров распределения пяти продавцам. Стоимость перевозки рассчитана на основе расстояний между исходными пунктами и пунктами назначений. Стоимость не зависит от того, насколько полно загружается трейлер. В приведенной ниже таблице указаны расстояния между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос и объем производства, исчисляемые количеством автомобилей. Один трейлер может перевозить до 18 автомобилей.

Сформулируйте транспортную задачу, принимая во внимание тот факт, что стоимость в расчете на 1 милю пути, пройденного трейлером, равна 10 долл.













Продавцы







Объемы







1

2

3

4

5

поставок

Центры

1

100

150

200

140

35

400

распределения

2

50

70

60

65

80

200




3

40

90

100

150

130

150







100

200

150

160

140




5.5. Пример 5.1.1. (стандартная транспортная модель.) Заводы автомобильной фирмы MG расположены в Лос-Анджелесе, Детройте и Новом Орлеане. Основные центры распределения продукции сосредоточены в Денвере и Майами. Объемы производства указанных трех заводов равняются 1000, 1500 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимость перевозки по железной дороге одного автомобиля на одну милю равняется примерно 8 центам. Расстояния в милях между заводами и центрами распределения приведены в таблице.







Денвер

Майами

Лос-Анджелес

1000

2690

Детройт

1250

1350

Новый Орлеан

1275

850

Расстояния можно перевести в стоимость перевозки одного автомобиля (переводной коэффициент

= 0.88 долл./миля). В результате получается следующая таблица стоимостей (округленных до доллара), которая содержит коэффициенты сij общей модели.








Денвер

Майами







(1)

(2)

Лос-Анджелес

(1)

1000

2690

Новый Орлеан



(3)

1275

850

5.6.Решите задачу распределения станков четырех различных типов по пяти типам работ. Пусть имеется 25,30,20 и 30 станков соответствующих типов. Пять типов характеризуются 20,20,30,10 и 25 операциями соответственно. На станке 4 не может выполняться работа 4. Исходя из коэффициентов стоимости операции, представленных в приведенной ниже таблице, постройте модель для оптимального распределения станков по работам.









Тип работ







1

2

3

4

5




1

10

2

3

15

9

Тип

2

5

10

15

2

4



4

20

15

13

-

8
  1   2   3


База данных защищена авторским правом ©ekonoom.ru 2016
обратиться к администрации

    Главная страница