XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 10
Текст из файла (страница 10)
хг+, = 6; — анх1 — а;гхг, с1х1+ сгхг -+ пп1п; апхг+аьзхг ( 6;, г = 1, Ь, — х1 — хг <4, х1>0, хг >О. примером. 66 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Отметим, что эта задача отличается от исходной задачи ли- нейного программирования (2.2). Если задача линейного программирования представлена в стандартной форме (2.5) и при этом то для ее решения можно использовать геометрический метод. Действительно, в этом случае система линейных алгебраических уравнений (2.6) имеет два свободных неизвестных, например х1 и хг, а все остальные неизвестные — базисные и выражаются через свободные неизвестные: Исключая из задачи базисные переменные, мы приходим к задаче линейного программирования с двумя переменными и системой ограничений в виде неравенств: Частным случаем этой задачи является задача (2.2).
Все дальнейшие рассуждения, относяшиеся к возможностям геометрического метода и техники его применения, ничем не отличаются от рассуждений, проведенных при рассмотрении примера 2.2. Поэтому в данном случае ограничимся иллюстративным Пример 2.6, Пусть необходимо найти решение задачи линейного программирования в стандартной форме: — у1+ уг — 2уз+У4+ Зуь — ув+2ут -+ шах; У1 — Уг+ Уз = 4, 2У1 — Уг — Уз — У4 = — 5, У1+ Уг — уь — — 4, Уг+ Ув = 5, 2Уг — 2уг — Ув+ 2ут = 7, уь > О, й = 1, 7.
2.2. Формы записи задач линейного программирования 67 В данном случае )у = 7 и Ь = 5. Непосредственной проверкой можно убедиться в том, что система линейных алгебраических уравнений, задающих ограничения, является базисной и может быть представлена в виде уь = У1 + уг + 4, Ув = -Уг + 5, у, = -у, + 0,5у, + 6. Исключив из целевой функции базисные переменные уг, ..., Ут, получим — У1 + уг — 2уз+ ул+ Зуь — ув+ 2уг = 5У1 + 2уг+ 12. Обозначив х1 — — уг и хг — — уг, приходим к следующей задаче, эквивалентной исходной: 5х1+ 2хг -+ шах; х1 — хг ~ (4, — Зх1+ 2хг < 1, хг ( 5, х1 — 0,5хг < 6, хг>0, хг>0. На рис.
2.4 видно, что омпгиллальмая вершима границы ГО множества С допустимых решений — это точка С пересечения прямых, задаваемых уравнениями хг — — 5 и х1 — 0,5хг —— т '= б. Таким образом, оптимальное решение Х' = (8,5 5), которое в исходных переменных уг, ..., Ув имеет вид У (8,5 5 0,5 16,5 17,5 0 0) . Завершая рассмотрение геометрического метода решения Задач линейного программирования, сделаем следующие замечания.
Замечание 2.1. Если 1' = (У1 .„УН), Г = (71 "° 7~ч) ля = (орь) р Мьн(И), В = (б, ... ~3ь), Он — нуль-вектор и Рис. 2.5 Рис. 2.4 ГУ вЂ” + шах; АУ = В, У > ОН. 12.11) 68 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1ь~, то задача линейного программирования, представленнзл в стандартной форме (2.5), принимает вид Здесь неравенство У > ОН понимается как совокупность нера- венств уь > О, й= 1, № Замечание 2.2. Задача линейного программирования может не иметь решения даже тогда, когда множество С допустимых решений не пусто, Эту ситуацию иллюстрирует рис. 2.5. Замечание 2.3. При 1ч' — Е = 2 оптимальное решение У' задачи 12.5) линейного программирования в стандартной форме всегда имеет не менее двух нулевых координат 1см. пример 2.6).
Это связано с тем, что оптимальная вершина границы Ггэ множества С допустимых решений является точкой пересечения 23. задачи, приводящие к задачам линейного программирования 69 как минимум двух прямых, уравнения которых определяются ограничениями исходной задачи 1в примере 2.6 таковыми явля- ются ув = О и у7 = О, т.е. хз — — 5 и х1 — 0,5х2 = 6). 2.3.
Задачи, приводящие к задачам линейного программирования В процессе изучения основных понятий исследования операций и основ линейноео проераммироваиия мы познакомились с двумя задачами линейного программирования: 1) в примере 1.2 рассмотрена задача о составлении пищевого пайка, которая при более общей постановке известна как задача о пиилеволя рационе; 2) в 2.1 рассмотрена задача распределительного типа, которую называют также задачей о роспределеиии оераиичеииых ресурсов.
Для расширения представлений о возможных сферах практического применения линейного программирования изложение его основ завершим анализом нескольких практически важных задач, обратив особое внимание на специфические особенности построения их математических моделей. Транспортная задача. Рассмотрим задачу, возникающую перед транспортным отделом фирмы, имеющей и предприятий П;, 1= 1, п, производящих однородную продукцию, и т складов С,, З = 1, т, для ее хранения.
Производственные 70 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 2.3. Задачи, прииодяи1ие и задачам линейного программирования 71 мощности предприятий (о; — мощность предприятия П;, т.е, месячный объем производимой им продукции) и возможности приема продукции складами (Р— объем продукции, который может принять склад С в течение месяца) известны на каждый месяц. Кроме того, известны транспортные расходы с; по доставке единицы объема продукции с любого предприятия П;, 1 = 1, и, на любой склад С,, ! = 1, т.
Требуется распределить продукцию, производимую предприятиями П;, по складам С, так, чтобы минимизировать общие транспортные расходы. Пусть х, — объем продукции, поставляемой на склад С, с предприятия П;. В этом случае х; > 0 при 1 = 1, в и !' = 1, т. А так как с;,х; — затраты на транспортировку объема продукции я! с предприятия П; на склад С, (в предположении, что транспортные расходы пропорциональны объему перевозимого груза), то общие транспортные расходы фирмы равны значению целевой функции ~(Х!1~ ~Хань) ~ 2~~ СОХ!1~ 1=1 1=1 которое необходимо минимизировать путем выбора неотрицательных значений (хб), удовлетворяющих следующим ограничениям: ) Х! =5;, 1=1,П, 1=1 так как произведенная продукция должна быть вывезена с каждого предприятия; так как объем продукции, который может принять каждый склад С, ограничен его емкостью Р . Естественно, что рассматриваемая задача имеет решение, если суммарный объем произведенной продукции не превышает суммарной емкости складов: Следует отметить, что приведенная выше постановка транспортной задачи является далеко не единственной, в чем можно убедиться, ознакомившись со специальной литературой*.
Задача о календарном планировании комплекса работ. Эта задача может быть сформулирована следующим образом. Пусть некоторая фирма должна реализовать проект строительства, состоящий из конечного набора различных операций (работ). Специалисты-строители оценили продолжительность выполнения каждой операции и для каждой операции, содержащейся в проекте, установили все другие опера, ции, которые должны быть выполнены к началу ее реализации. Руководство фирмы заинтересовано в минимально возможных сроках реализации проекта. Для удобства дальнейших рассуждений предположим, что весь проект состоит из пяти операций А, В, С, Р, Е и все данные о нем представлены в табл.
2.1, где введена информация о фиктивной операции Е, начинающейся в момент завершения реализации проекта. Из табл. 2.1 видно, что операцию С нельзя начать до завершения выполнения операции А, а к операции Е можно приступать лишь после реализации операций В и Р. Весь комплекс работ будет выполнен, как только будет завершено выполнение операций С и Е. В рассматриваемой задаче управляемыми передаеннылаи являются моменты начала выполнения различных операций, за исключением операций А и В.
Это связано с тем, что операции "Смл Вагнер Г., т. 1; Вени!цель Е. СЛ Таха Х., т. 1. Таблица 2.1 Таблица 2.2 72 й. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ А и В не имеют предшествующих, поэтому можно считать их началом нулевой момент времени. Заметим также, что условия задачи не ограничивают количества одновременно начинаемых работ, что позволяет предполагать совпадение моментов начала выполнения операций С и Р, так как им непосредственно предшествует одна и та же операция А. Таким образом, математическая модель рассматриваемой задачи в качестве управляемых переменных содержит лишь следующие: х1 — момент начала операций С и Р; хз — момент начала операции Е; хз— момент начала операции В.
А так как хз — момент завершения всего комплекса работ, то необходимо минимизировать хз при условии выполнения следующих ограничений (см. табл. 2.1): Х1 ) 1А, ХЗ )~ ~В, ХЗ ) )1р+х1, ХЗ ) )Фс+х1, хэ ~ )~В+ Хи, Следует отметить, что благодаря специфике ограничений йд > О, 1В > О, ~с > О, 1О > О, Ы > 0 нет необходимости в явном виде задавать условия неотрицательности хь ) О, к = 1, 3. Формально это приводит к тому, что в математической модели рассматриваемой задачи управляемые переменные не ограничены в знаке, что и будет использовано далее для ее решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
