«• Ерин В.Г. • Ткаченко О.В. • Христиановский В.В. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Методическое пособие и контрольные задания ( для студентов-заочников экономических специальностей ) Донецк, ДонНУ-2000 УДК 519.85/075.8/ ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

• Ерин В.Г.

• Ткаченко О.В.

• Христиановский В.В.

МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ

Методическое пособие и контрольные задания

( для студентов-заочников экономических специальностей )

Донецк, ДонНУ-2000 УДК 519.85/075.8/ Христиановский В.В., Ерин В.Г., Ткаченко О.В. Математическое программирование. Методическое пособие и контрольные задания для студентов-заочников экономических специальностей. - Донецк. ДонГУ. 1999с.

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

В пособии представлены методы решения задач линейного, целочисленного, параметрического, дробно-линейного программирования. Рассмотрены транспортные и матричные игровые задачи. Показан графический подход к решению нелинейных задач, а также пример реализации метода динамического программирования.

Уделено существенное внимание вопросам двойственности и устойчивости решений в линейном программировании.

Все методы решения и приемы анализа решений сопровождены конкретно реализованными примерами.

Рецензенты: Гузь Н.Г., д.э.н., проф.

Амитан В.Н., д.э.н., проф.

Электронный вариант Породникова В.Д.

I. ОБЩИЕ ЗАМЕЧАНИЯ К ИЗУЧЕНИЮ КУРСА

“МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ” И

ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ.

ЛИТЕРАТУРА

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

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

2. Контрольная работа состоит из восьми заданий. Необходимо выполнить по одной задаче из каждого задания согласно своему варианту. Номер варианта обозначается римскими числами и выбирается согласно двум последним цифрам номера зачетной книжки:

Последние две цифры номера зачетной книжки Номер варианта 01 21 41 61 81 I 02 22 42 62 82 II 03 23 43 63 83 III 04 24 44 64 84 IV 05 25 45 65 85 V 06 26 46 66 86 VI 07 27 47 67 87 VII 08 28 48 68 88 VIII 09 29 49 69 89 IX 10 30 50 70 90 X 11 31 51 71 91 XI 12 32 52 72 92 XII 13 33 53 73 93 XIII 14 34 54 74 94 XIV 15 35 55 75 95 XV 16 36 56 76 96 XVI 17 37 57 77 97 XVII 18 38 58 78 98 XVIII 19 39 59 79 99 XIX 20 40 60 80 00 XX 3. В заголовке контрольной работы, помещенном на обложке тетради, должны быть указаны фамилия, имя и отчество студента, номер зачетной книжки, какой раз выполняется работа, дата отсылки работы в университет, домашний адрес студента.

4. Решение задач контрольной работы и необходимый анализ должны быть сопровождены объяснениями.

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Акулич И.Л. Математическое программирование в примерах и задачах:

Учебное пособие для студентов экономических специальностей вузов. – М.:

Выс. шк., 1986 – 319 с.

2. Балашевич В.А. Основы математического программирования: учебное пособие для инженерно-экономических и экономических специальностей. – Минск:

Вышэйшая шк., 1985. – 173 с.

3. Деордица Ю.Л., Нефедов Ю.М. Исследование операций в планировавнии и управлении: Учебное пособие для экономических специальностей. – Киев:

Выс.шк., 1991. – 270 с.

4. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш.

Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман: Под ред. проф. Н.Ш.

Кремера. – М.: Банки и биржи, ЮНИТИ, 1997 – 407 с.

5. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.В. Математическое программирование: учебное пособие. – М.: Высшая школа, 1985. – 301 с.

6. Кузнецов А.В., Новикова Г.И., Холод Н.И. Сборник задач по математическому программированию: Для экономических специальностей вузов. – Минск:

Вышейшая шк. 1985 – 143 с.

7. Линейное и нелинейное программирование / Под ред. И.И. Ляшенко. – Киев:

Выс.шк., 1979 – 372 с.

8. Решение задач математического программирования: курс лекций для студентов экономических специальностей / В.В. Христиановский, В.Г. Ерин, О.В. Ткаченко. – Донецк: ДонГУ, 1992. – 254 с.

9. Сборник задач по математическому программированию: в помощь студентамэкономистам / В.В. Христиановский, В.Г. Ерин, О.В. Ткаченко. – Киев: УМК ВО, 1992 – 336 с.

10.Абрамов А.М., Капустин В.Ф. Математическое программирование: Учебное пособие. – Л.: Издательство ЛГУ, 1981 – 328 с.

11.Воробьев Н.Н. Теория игр для экономистов – кибернетиков. – М.: Наука, 12.Денисов В. Windows 95 с самого начала – СПб: Питер, 1996. –240 с.

13.Зайченко Ю.Л. Исследование операций: Учебник. – Высшая школа, 1988. – 14.Канторович Л.В. Экономический расчет наилучшего использования ресурсов.

– М.: Наука, 1959.-200 с.

15.Ляшенко И.Н., Ляшенко Е.И. Математика для экономистов: учебное пособие. – Донецк, ДонГУ, 1998.

16.Математика и кибернетика в экономике: Словарь-справочник. – М.:

Экономика, 1975 – 70 с.

17.Методические указания и задачи по математическому программированию: Ч.

1. Для студентов экономических специальностей / В.В. Христиановский, В.Г Ерин, О.В. Ткаченко. – Донецк: ДонГУ, 1990 – 175 с.

18.Методические указания и задачи по математическому программированию: Ч.2.

Для студентов экономических специальностей / В.В. Христиановский, В.Г.

Ерин, О.В. Ткаченко – Донецк: ДонГУ, 1990 – 154 с.

19.Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях: Учебное пособие. – М.: Выс.шк., 1986 – 285 с.

20.Данциг Дж. Линейное программирование, его обобщения и применение. –М.:

Прогресс, 1966.- 600 с.

21.Фигурнов В.Э. IBM РС для пользователя. Изд. 6-е, перераб. и доп. – М.:

ИНФРА – М, 1995. – 432 с.

22.Шелдон Т. Windows 95. Проще простого. К.: Диалектика, 1996. – 512 с.

23. Эльстер К.Х, Рейгард, Шойбле М., Донат Г. Введение в нелинейное программирование. – М.: Наука, 1985 – 280 с.

24.Юдин Д.Б., Гольштейн Е.Г. Линейное программирование: теория, методы и приложения. –М.: Наука, 1969. – 424 с.

II. ЗАДАНИЯ ДЛЯ ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

СТУДЕНТАМИ-ЗАОЧНИКАМИ ЭКОНОМИЧЕСКИХ

СПЕЦИАЛЬНОСТЕЙ

ПЕРВОЕ ЗАДАНИЕ. Построить математическую модель, осуществить графическое и симплексное решение с последующим необходимым экономическим анализом следующей оптимизационной задачи.

Предприятие может выпускать товары Т1 и Т2, используя ресурсы S1, S2, S3.

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

Нормозатраты ресурсов в условных единицах на производство 1 т каждого из товаров, объемы наличных ресурсов, цены реализации товаров известны и приведены в таблице. Также приведены нужные нам обозначения переменных величин.

Товары на производство 1 т товара (усл.ед./т) йся объем цены ресурсов Ресурсы выпуска товаров Здесь aij, bi, cj ( i = 1,3; j = 1,2 ) - известные нам величины, заданные для каждого варианта контрольной работы в ниже приводимой таблице;

xj, yi, z - переменные искомые величины.

В приводимой таблице данные колонок d13, d23, d33, d3 используются лишь при анализе возможности выпуска третьего гипотетического товара. Основная же модель задачи использует лишь данные прочих колонок.

Подробный перечень требований по выполнению первого задания контрольной работы:

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

2. Составить математическую модель двойственной задачи.

3. Выполнить графическое решение исходной задачи. Проанализировать это решение.

4. Привести исходную задачу к каноническому виду. Осуществить симплексное решение с целью получения оптимальных ответов для исходной и двойственной задач.

5. Проанализировать дефицитность (или недефицитность) каждого ресурса при реализации оптимального плана исходной задачи.

6. Выделить обратную матрицу преобразований, приведших к оптимальной таблице. Провести анализ по столбцам этой матрицы.

7. Проанализировать устойчивость полученного оптимального результата исходной задачи в зависимости от изменения коэффициентов целевой функции.

8. Проанализировать устойчивость двойственных оценок («теневых» цен) относительно изменения объемов имеющихся ресурсов.

9. Рассмотреть гипотезу о рациональности выпуска еще одного товара Т3 при первоначально имеющихся ресурсах. Предполагаемые нормозатраты и цена для этого товара приведены в колонках d13, d23, d33, d3 таблицы данных вариантов.

10.Вычислить норму заменяемости ресурсов, активно влияющих на полученный оптимальный план.

Примечание: данные колонок d13, d23, d33, d3 используются только при проведении анализа по п. 9 данного перечня требований.

ВТОРОЕ ЗАДАНИЕ. Решить транспортную задачу.

В таблицах ai - наличие товара у i-го поставщика, bj - потребность j-го потребителя в этом товаре. В рабочих клетках указаны известные цены cij за перевозку единицы груза от i-го поставщика j-му потребителю.

ТРЕТЬЕ ЗАДАНИЕ. С помощью симплекс-метода решить задачу дробнолинейного программирования. Полученное решение проверить использованием графического метода.

15.

ЧЕТВЕРТОЕ ЗАДАНИЕ. Решить параметрическую задачу.

11. 16. ПЯТОЕ ЗАДАНИЕ. С помощью метода отсечений Гомори найти полностью целочисленное оптимальное решение.

8. 3x 1 + 5x 2 60, 12. 19. 5x 20. x ШЕСТОЕ ЗАДАНИЕ. Для игры с заданной платежной матрицей А необходимо определить смешанные стратегии.

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

В таблицах всех задач слева во втором вертикальном столбце указаны возможные доли выделения капиталовложений в тыс. гривен. В остальных столбцах приведены приросты продукции в относительных единицах qi(x) по каждому i-му предприятию (i = 1, 2, 3, 4) в зависимости от вложения средств x.

При расчетах для каждого предприятия считать qi(0) = 0, т.е. если i-му предприятию капиталовложения не выделяются, то прироста продукции нет.

Номер Выделяемые Прирост продукции в относительных единицах ВОСЬМОЕ ЗАДАНИЕ. Решить графически заданную задачу нелинейного программирования, рассмотреть применение градиентного метода для этой задачи.

10. 11.

13.

14.

15.

16.

17.

18. 3x 1 + x 2 15,

III. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЗАДАНИЙ

КОНТРОЛЬНОЙ РАБОТЫ

§ 1. О ПРОЦЕССЕ ПРИНЯТИЯ РЕШЕНИЙ В ИССЛЕДОВАНИИ

ОПЕРАЦИЙ

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

Математическое программирование является основным разделом исследования операций. Процесс принятия решений в исследовании операций включает следующие основные этапы:

1) экономическая постановка задачи;

2) построение математической модели;

3) решение задачи;

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

Первый этап является наиболее важным. Он предполагает выделение важнейших свойств объекта и абстрагирование от второстепенных; изучение структуры объекта и тех зависимостей, которые связывают его элементы;

формулирование гипотез, объясняющих поведение и развитие объекта.

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

На третьем этапе на основе выбранной модели проводится решение задачи.

Этот этап может включать создание алгоритмов и программ для решения на ЭВМ.

На четвертом этапе проводится экспертная проверка результатов. Если нет адекватности модели и моделируемого объекта, производится корректировка экономической постановки или математической модели. Если корректировка не нужна, то результаты решения используются для принятия решений.

Блок-схема принятия решений показана на рис.1.1.

Одним из основных этапов процесса принятия решений в исследовании операций является построение математической модели. Математическая модель – это записанная в математических символах и выражениях абстракция реального явления или процесса. Математические модели экономических процессов и явлений называются экономико-математическими моделями. По способу логикоматематического описания объектов модели делятся на:

1) линейные, в которых все зависимости описываются линейными соотношениями, и нелинейные, в которых имеются нелинейные соотношения;

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

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

В соответствии с целями создания и применения можно выделить оптимизационные модели, в которых выбор осуществляется в зависимости от экстремизации некоторого критерия, и неоптимизационные, в которых критерия оптимальности нет.

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

Рассмотрим общую постановку задачи математического программирования.

Общая задача математического программирования состоит в определении оптимального значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Математически определение оптимального решения выражается в нахождении экстремума ( max или min) функции многих переменных в заданной области изменения этих переменных где Ri - один из знаков, =,.

§ 2. ПРИМЕРЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

ОПТИМИЗАЦИОННЫХ ЭКОНОМИЧЕСКИХ ЗАДАЧ

Задача оптимального планирования предполагает составление плана производства, обеспечивающего в максимальной степени выполнение задания.

Сформулируем ее в общем виде.

Имеется m видов материальных ресурсов, каждый из которых ограничен величиной bi единиц (i = 1, 2,…, m). Из этих ресурсов следует изготовить n видов продукции. Известны нормы расхода i-го ресурса на выпуск единицы j-й продукции aij (j = 1, 2,…, n), а также прибыль, получаемая от реализации единицы продукции jго вида или цена единицы продукции j-го вида cj.

Требуется определить план производства продукции, обеспечивающий получение максимальной прибыли или максимальной стоимости.

Для составления математической модели данной задачи принимаем искомое количество продукции j-го вида равным xj. Сформулированные условия в этом случае записываются следующим образом. Определить множество неотрицательных переменных xj 0 (j = 1, 2,…, n), которые удовлетворяют условию ограничений по суммарную прибыль от реализации всей продукции или суммарную ее стоимость, равна Приведем пример построения математической модели задачи оптимального планирования производства.

Пусть химический цех может производить ценные вещества двух наименований – B1 и B2. Известно, что производство этих веществ зависит от наличия четырех ресурсов (сырье, энергия, временной ресурс автоматовпроизводителей). Нормозатраты каждого из ресурсов на производство 1 кг вещества известны и приведены в таблице. В этой же таблице указаны величины имеющихся ресурсов и цена производимых веществ:

Учитывая наличие ресурсов, нормозатраты и прибыль, необходимо составить такой план выпуска веществ B1 и B2, который бы обеспечил цеху наибольшую суммарную стоимость.

Чтобы решать задачу с помощью математических приемов, следует сначала составить математическую модель задачи.

Все данные нашей задачи сосредоточены в одной таблице. Будем считать, что с экономических позиций нам задача понятна и имеется вся необходимая информация. Для построения модели введем переменные величины. Обозначим через x1 план выпуска веществ B1 и через x2 план выпуска веществ B2. Эти величины нам как раз и нужно определить, и они должны быть такими, чтобы получалась максимальная стоимость, которую мы обозначим через z. В нашей простой задаче мы ограничены наличием ресурсов. Ресурсы P1 имеют 60 условных единиц.

Очевидно, что суммарные затраты на выпуск B1 и B2 не должны превысить 60. Из таблицы видно, что нормозатраты P1 на 1 кг вещества B1 составляют 6 усл. единиц, тогда затраты на весь план выпуска B1 составят 6x1. Соответственно нормозатраты P на 1 кг вещества B2 равны 3 усл. единицам и затраты на план выпуска B2 составят 3x2. Следовательно, суммарные затраты ресурса P1 составят (6x1 + 3x2) и не должны превысить величину наличия P1, т.е. не должны превысить 60. Итак, по ресурсу P имеем неравенство 6x1 + 3x2 60. Аналогично неравенства можно записать и для ресурсов P2, P3, P4:

Видно, что ресурс P3 используется лишь на производство вещества B1, а ресурс P4 - на производство B2. Из ограничений еще надо учесть неотрицательность планов выпуска веществ, т.е. x1 0, x2 0. Для составления модели остается сформировать функцию стоимости z. Стоимость z складывается из стоимости вещества B1 и стоимости вещества B2. Так как выпуск вещества B1 обозначен через x1, то стоимость вещества B1 будет равна 4x1. Соответственно стоимость вещества B будет равна 5x2. Но тогда суммарная стоимость составит целевую функцию нашей задачи:

Суммируя сказанное, можно сформулировать следующую математическую модель нашей задачи: найти такие значения переменных x1 и x2, которые бы отвечали условиям и обеспечивали бы максимум целевой функции Во многих отраслях промышленности технологический процесс требует одновременного использования нескольких компонентов, в связи с чем возникает проблема такого их соединения, при котором достигался бы максимальный эффект.

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

Сформулируем задачу о смесях в общем виде.

Имеется n различных видов сырья, каждый из которых включает m видов веществ. Известны количество i-го вещества в единице j-го вида сырья aij (i = 1,…, m;

j = 1, 2,…, n), а также стоимость единицы сырья j-го вида cj. Через bi и bi обозначим соответственно наименьшее и наибольшее допустимое количество веществ i-го вида в смеси, а через dj - запас сырья j-го вида. Требуется из имеющегося сырья получить смесь с заданными свойствами при минимальных затратах. Для составления математической модели принимаем искомое количество сырья j-го вида, используемого для получения смеси, равным xj.

Сформулированные требования теперь можно записать следующим образом.

2,…, n), которые удовлетворяют условиям:

по ограничению ресурсов сырья:

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

Известно, что откорм животных экономически выгоден при условии, когда животное получает в дневном рационе не менее 6 единиц питательного вещества A, не менее 12 единиц вещества B, не менее 4 единиц вещества C. Для откорма животных используются два вида кормов. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице:

Питательные Количество единиц питательных веществ в 1 кг корма корма Определить, какое количество каждого вида корма необходимо расходовать, чтобы общие затраты на откорм были минимальными.

Построим математическую модель. Обозначим через x1 и x2 количество входящего в оптимальный рацион корма соответственно I и II вида. При этом ограничения по содержанию питательных веществ А, В и С будут выражены следующим неравенствами:

Требование неотрицательности x1 0, x2 0. Целевая функция Раскрой материалов – необходимый этап большинства производств. Сущность оптимального раскроя материалов состоит в определении такого плана раскроя, при котором получается необходимый ассортимент заготовок, а отходы (по длине, площади или весу) сводятся к минимуму.

Сформулируем задачу раскроя в общем виде. Исходный материал следует раскроить на m видов заготовок, причем заготовок i-го (i = 1, 2,…, m) вида должно получиться Ai штук. Раскроить материал можно n различными способами. Известны количество заготовок i-го вида, получаемых при раскрое единицы исходного материала по j-му способу (j = 1, 2,…, n) bij, а также величина отхода, получаемого при раскрое единицы исходного материала по j-му способу cj. Требуется определить такой план раскроя исходного материала, который обеспечит получение необходимого количества заготовок каждого вида с минимальными отходами.

Для составления математической модели принимаем искомое количество единиц исходного материала, которое следует раскроить по способу j, равным xj.

Сформулированные требования можно записать следующим образом.

2,…, n), которые удовлетворяют условию получения необходимого количества заготовок каждого вида и при этом целевая функция, выражающая суммарные отходы от раскроя по всем способам, равна Рассмотрим пример построения математической модели задачи о раскрое.

Рулоны ткани длиной 35 метров следует разрезать на куски 13,5; 10; 7 м в количестве 50, 70 и 80 штук соответственно.

Определить оптимальный план раскроя ткани.

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

раскроя одного рулона (м) Обозначим через x1, x2,…, x8 количество рулонов ткани, которые следует раскроить соответственно по первому, второму и т.д. способам.

При этом ограничения по количеству необходимых кусков ткани будут выражены следующими уравнениями:

Требования неотрицательности Целевая функция Рассмотрим постановку однопродуктовой (однотоварной) транспортной задачи (например, задачи о перевозке угля в рамках региона).

Пусть имеется m поставщиков с резервами (запасами) товара ai единиц (i = 1, 2,…, m). Имеется соответственно n потребителей с потребностями bj единиц (j = 1, 2,…, n). Известны транспортные расходы по перевозке единицы продукции от i-го поставщика j-му потребителю, которые равны cij.

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

Задание транспортной задачи и ее решение удобно осуществлять с помощью транспортной таблицы (матрицы) следующего вида:

Потр.

Если сумма a1 + a2 +…+ am равна сумме b1 + b2 +…+ bn, то в таком случае весь товар будет вывезен от поставщиков и весь необходимый товар будет получен каждым из потребителей. Для этого случая составим математическую модель, описывающую однопродуктовую транспортную задачу.

…, n), удовлетворяющих условиям вывоза всего продукта из пунктов производства условиям удовлетворения запросов потребителей при которых достигает минимума целевая функция Рассмотрим пример построения математической модели транспортной задачи.

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

Составить такой план перевозки груза от поставщиков потребителям, чтобы суммарные затраты на перевозку были минимальными.

Составим математическую модель. Обозначим через xij (i = 1, 2, 3; j = 1, 2, 3, 4) количество единиц груза, перевозимого от i-го поставщика на j-е предприятие.

Тогда условия вывоза и доставки имеющегося и необходимого количества груза обеспечиваются за счет выполнения следующих соотношений:

Требование неотрицательности Целевая функция Имеется n специалистов и n работ, на которые могут быть направлены специалисты. Пусть известна эффективность (например, в баллах) от назначения каждого i-го (i = 1, 2,…, n) специалиста на каждую j-ю работу. Эту эффективность будем обозначать через cij. Требуется таким образом назначить специалистов на работы, чтобы итоговая (суммарная) эффективность была максимальной.

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

1, если i - й специалист назначается на j - ю работу, Математическая модель задачи. Ограничения:

1) каждый специалист может выполнять только одну работу 2) каждая работа может выполнятся только одним работником 3) условие изменения переменной Целевая функция – максимизация суммарной эффективности Приведем пример построения математической модели задачи об оптимальных назначениях.

Необходимо оптимальным образом распределить пять работников для выполнения каждой из пяти работ. Производительность указана в таблице:

I II III IV V

Составим математическую модель задачи.

Обозначим через x ij (i = 1,5; j = 1,5) переменную, равную 1, если i-й работник назначен на выполнение j-й работы, и равную 0 в противном случае.

Условие выполнения каждым работником только одной работы выразится равенствами а условие выполнения каждой работы только одним работником – равенствами Целевая функция – максимизация суммарной производительности:

§ 3. ПРИВЕДЕНИЕ ПРОИЗВОЛЬНОЙ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ К КАНОНИЧЕСКОМУ ВИДУ.

В самом общем виде задача линейного программирования ставится следующим образом.

Найти значения переменных x1, x2,…, xn, которые бы удовлетворяли условиям

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

Найти такие значения x1,…, xn, которые подчиняются условиям

и приносят минимум целевой функции С помощью простых преобразований любая задача линейного программирования может быть сведена к каноническому виду, т.е. представлена в форме записей (3.3), (3.4), (3.5). Кратко рассмотрим эти преобразования.

1. Из условий (3.3) ясно, что в каноническом задании на все переменные задачи наложено требование неотрицательности. Во многих экономических задачах это так и бывает. Но в общем случае могут встретиться переменные неотрицательные, неположительные и такие, которые могут принимать как положительные, так и отрицательные значения. И в этом общем случае задачу надо свести к таким переменным, каждая из которых подчинялась бы требованию неотрицательности. Покажем, как это делать. Пусть по отношению к некоторой переменной xk имеется требование неотрицательности, т.е. xk 0. Тогда эта переменная никаким преобразованиям не подвергается. Пусть по отношению к некоторой переменной xp имеется требование xp 0. Это требование противоположно тому, что нам надо. Поэтому мы вводим новую переменную xp = xp, но уже по отношению к переменной xp мы можем утверждать xp 0. Если же по отношению к некоторой переменной xq нет требования по знаку, т.е. она может принимать любые значения (положительные и отрицательные), то переменная xq заменяется разностью неотрицательных переменных.

Именно, вводятся новые дополнительные переменные x 0 и x 0 и делается замена xq = x x. В результате этой замены переменная xq исключается из задачи, а в задаче остаются переменные x, x, на которые уже наложено требование неотрицательности. Итак, переменные, на которые наложено требование неотрицательности, остаются в задаче без неположительности заменяются переменными с противоположным знаком;

переменные, которые могут менять знак, заменяются разностью новых неотрицательных переменных.

2. Условия (3.4) представлены в виде уравнений. Это означает, что любое из имеющихся в условии неравенств (кроме условий неотрицательности переменных ) должно быть переделано в уравнение. Делается это с помощью введения дополнительных неотрицательных балансирующих переменных. Пусть, например, некоторое условие задано в виде Тогда вводим дополнительную балансирующую переменную xn+ прибавлением к меньшей части неравенства:

Если в исходном задании имеется r неравенств, то вводится r дополнительных переменных xn+1 0, xn+2 0, …, xn+r 0.

3. В одних задачах в зависимости от экономического смысла целевой функции требуется осуществлять максимизацию, в других – минимизацию.

Между процедурами максимизации и минимизации имеется следующая связь: max z(x) = -min [-z(x)] и min z(x) = -max [-z(x)]. В каноническом виде мы условились ввести минимизацию для целевой функции (3.5).

Следовательно, если в первоначальном условии задачи требуется минимизировать z(x), то никаких изменений не делается. Если же требуется Пример. Пусть задана следующая задача линейного программирования:

В нашей задаче количество переменных n = 4, количество ограничений (без требований неотрицательности) m = 3. Заданную задачу необходимо преобразовать к каноническому виду. На переменные x1 и x2 наложено требование неотрицательности. Переменную x3 заменяем переменной x3 = x3, считая уже x3 0. Переменная x4 должна быть заменена разностью неотрицательных переменных x 0 и x 0. Именно x 4 = x x. И еще надо ввести две дополнительные балансирующие переменные для преобразования двух неравенств в уравнения. Для этого введем перейдем к функции z(x) = z(x). Учитывая сказанное, задача примет вид Замечание. Все заменяющие переменные можно было бы ввести с новыми индексами j > n, не пользуясь черточками или штрихами над обозначающей буквой.

§ 4. ГРАФИЧЕСКОЕ РЕШЕНИЕ ПРОСТЕЙШИХ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Любая задача линейного программирования (ЗЛП) имеет несложную геометрическую интерпретацию. Пусть, например, задача имеет самый общий вид (3.1)-(3.2). Так как полный набор переменных этой задачи состоит из n переменных x1, x2, …, xn и переменной z, то прежде всего задачу самым естественным образом рассматривать в (n + 1)-мерном пространстве. И вся интерпретация состоит в том, что в множестве точек, удовлетворяющих условиям (3.1), надо найти такую точку (или такие точки), в которой (которых) бы координата z целевой функции принимала бы экстремальное значение (максимум или минимум в зависимости от требований задачи). Однако, пользуясь уровнями целевой функции (z = const), можно задачу интерпретировать и в n-мерном пространстве. Именно, совокупность условий (3.1) будет «высекать» в n-мерном пространстве выпуклое многогранное множество, а изоцели z = const (т.е. уровни целевой функции) будут выявлять экстремальные точки (если они существуют) в области допустимых решений. А так как z = c1 x1 + c2 x2 + +…+ cn xn, то уровнями одного и того же значения целевой функции будут гиперплоскости c1 x1 + c2 x2 + …+ cn xn = const. Отсюда вытекает общая рекомендация для практически решаемых задач. Сначала строят область допустимых решений, а затем по прохождению изоцелей-гиперплоскостей z = const через область делают вывод об экстремальных решениях рассматриваемой задачи.

Поскольку для линейной задачи изоцели представляют собой семейство параллельных гиперплоскостей c1 x1 + c2 x2 + …+ cn xn = const, то для поиска оптимальных точек в области допустимых решений очень удобно пользоваться градиентом целевой функции Вектор-градиент как раз указывает направление наибольшего возрастания функции. Зная градиент целевой функции, нетрудно построить уровни этой функции.

Подытоживая сказанное, приведем два примера.

Пример А. В § 2 был рассмотрен конкретный пример составления математической модели экономической задачи. Модель задачи предстала в виде (2.1)-(2.2). Решение начнем с построения области допустимых решений. В условиях (2.1) имеется шесть неравенств. Для построения области допустимых решений надо выделить то геометрическое место точек на рис.4.1, которое подчиняется всем ограничениям (2.1). Итак, вводим первое ограничение x1 0.

Границей этого нестрогого неравенства является прямая x1 = 0 (это ось x2).

Согласно первому неравенству нам подходят все точки правой полуплоскости и сама ось x2. Второе неравенство x2 0 с границей x2 = 0 (ось x1) разрешает нам точки оси x1 и всей верхней полуплоскости. Если же рассматривать одновременно требования первого и второго неравенств, то нам будут подходить точки первого координатного угла системы координат x1, x2 вместе с положительными полуосями 0x1 и 0x2. Вводим третье неравенство этого неравенства является прямая 6x1 + 3x2 = 60, которую мы проводим на плоскости через точки ее пересечения с осями K (0, 20) и L (10, 0). Взяв в качестве контрольной точки начало координат O (0, 0), мы проверяем зону допустимости. Проверка даст 6 0 + 3 0 < 60, т.е. по отношению к третьей границе допускается полуплоскость книзу. Объединяя требование трех первых неравенств, мы получаем допустимое множество в виде треугольника OKL.

Вводим четвертое неравенство проходящей через точки пересечения с осями M(0, 8) и N(20, 0). Если взять в качестве контрольной точки начало координат O (0, 0), то мы и здесь наблюдаем признак допустимости, именно 2 0 + 5 0 < 40. Теперь уже четырем условиям вместе будет отвечать четырехугольник OMCL. Остается ввести еще два ограничивающих неравенства 9x1 81 с границей 9x1 = 81 и 8x2 56 с границей 8x2 = 56. Граница 9x1 = 81 есть вертикальная прямая ((5) на рис. 4.1), граница 8x2 = 56 имеет отметку (6) на этом же рисунке. Контроль показывает, что пятое ограничение допускает левую полуплоскость от вертикальной границы (5), а шестое ограничение – нижнюю полуплоскость от горизонтальной границы (6). В целом все шесть неравенств на плоскости x1, x2 выделяют шестиугольник OABCDE.

Переходим ко второй части решения нашей задачи, к определению оптимальной точки в найденной области допустимых решений. Для этого сначала определяем градиент целевой функции (2.2) Вектор (4,5) изобразим в виде направленного отрезка, исходящего из точки O(0, 0). Тогда линии уровня функции z будут представлены сеткой параллельных прямых, которые перпендикулярны к вектору grad z и возрастают в сторону, указываемую направлением градиента. На рис. 4.1 показан градиент и уровни целевой функции. По расположению изоцелей очевидно, что максимум целевой функции имеет место в точке C. При достаточно хорошем масштабе, выбранном для рабочего рисунка, координаты оптимальной точки определяются непосредственно на рисунке. Если же выбранный масштаб такой, что мы затрудняемся определить координаты оптимальной точки, то их можно доопределить аналитически, выяснив, какие граничные прямые пересекаются в ней. В нашем примере в точке C пересекаются границы условий (3) и (4). Тогда для точного определения координат C решаем совместно следующие два уравнения:

Решая эту систему по методу Гаусса, получаем x1 = 7,5 и x2 = 5. Итак, максимум заданной целевой функции z = 4x1 + 5x2 наступает в точке C (7,5; 5) и при этом zmax = z(C) = 4 7,5 + 5 5 = 30 + 25 = 55. Кстати, на рис. 4.1 видно, что минимум наступает в точке O(0, 0) и соответственно Пример Б.

В этом примере n = 5 и линейно независимых уравнений m = 3. Так как n – m = 2, то задача может быть решена графически. Но нам надо предварительно выделить базисные переменные и исключить их для обеспечения возможности графического решения. Постараемся выделить в качестве базисных переменных x1, x2, x3. Переменная x1 в первом уравнении может быть использована в качестве базисной. Выделим x2 во втором уравнении. Для этого мы из первого уравнения вычтем второе. Наша система уравнений примет вид В системе (4.4) из второго уравнения вычтем третье, тогда получим Тем самым мы от системы (4.2) перешли к эквивалентной системе (4.5) с уже выделенными базисными переменными x1, x2, x3. Из системы (4.5) легко найти выражения базисных переменных через свободные переменные x4 и x5.

Делаем это:

Воспользовавшись (4.6), можно целевую функцию (4.3) представить через свободные переменные x4, x5:

Итак, для целевой функции мы получили выражение через свободные переменные x4 и x5.

Далее, согласно (4.1) каждая из переменных должна подчинятся условию неотрицательности. Эти условия в совокупности с равенствами (4.6) позволят нам вывести базисные x1, x2, x3 из условий. Именно, имея в виду, что x1 0 и что из (4.6) x1 = 3 – 2x5, мы можем эти два условия заменить неравенством 3 – 2x5 0.

Аналогично, исходя из исходных условий x2 0 и x2 = 1 – 2x4 + 2x5 записываем неравенство x3 = 1 + x4 – x5 имеем неравенство 1 + x4 – x5 0. Все это нам позволяет перейти к задаче с меньшим количеством неизвестных:

Количество неизвестных задачи (4.7) позволяет провести графическое решение. Определив оптимальные значения переменных x40 и x50, мы затем определяем с помощью (4.6) оптимальные значения переменных x10, x20, x30. На рис. 4.2 представлено графическое решение задачи (4.7). Областью допустимых решений на этом рисунке является пятиугольник OABCD. По градиенту к целевой функции grad z = (2, -3) и сопутствующим ему изоцелям, т.е. с помощью прямых z = c1, z = с2, …, z = ck, определяем точку B, как приносящую нам минимум (min) в рамках допустимой области OABCD. Координаты точки B очевидны из рисунка, но в общем случае могут быть точно определены как пересечение границ x 5 = и –x4 + x5 = 1.

x3 = 0. Итак, получаем оптимальное решение для задачи (4.1)-(4.3):

§ 5. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

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

Необходимо четко представлять, что ограничения задач линейного программирования геометрически представляют собой выпуклые многогранные множества, число угловых точек (угловая точка является геометрическим образом опорного плана) которых можно подсчитать по формуле K Cn, где n - число векторов, образующих систему ограничений, r - ранг этой системы векторов. Для задач, имеющих практическое приложение, K является достаточно большим числом. Например, задача линейного программирования, имеющая размеры матрицы системы ограничений A4x10, содержит Kоп.пл. C10 = 210 опорных планов. Исходя из теоремы о целевой функции ЗЛП, линейная форма может достигать оптимальное значение в опорных планах. Поэтому для решения задачи можно просто перебрать значения целевой функции во всех опорных планах и выбрать среди них наименьшее или наибольшее. Однако такой простой перебор не является целесообразным даже для решения задач с помощью современных быстродействующих ЭВМ. Симплекс-метод дает способ целенаправленного перебора опорных планов. Он позволяет существенно сократить количество планов, выбираемых для проверки на оптимальность.

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

Пусть нам задана следующая задача линейного программирования:

Таким образом, математическая модель рассматриваемой задачи представляется в стандартной форме записи и имеет вид (5.1 – 5.3).

Прежде чем решить задачу симплекс-методом, необходимо привести ее модель к канонической форме. Особенности канонической формы модели состоят в том, что система ограничений задачи (5.1) должна быть представлена в форме уравнений, условия неотрицательности накладываются на все переменные, а целевая функция стремится к min. Воспользовавшись теоремой связи между формами моделей задач линейного программирования, преобразуем исходную модель задачи путем введения балансовых переменных следующим образом:

Студент должен четко представлять, что смысл применения вышеуказанной теоремы к преобразованию исходной системы ограничений сводится к введению в каждое из условий так называемых балансовых переменных x3, x4, x5, x6, которые должны быть обязательно неотрицательные, а в целевую функцию они вводятся с коэффициентом 0. Целевая функция сводится к min путем замены знаков коэффициентов при переменных на противоположные. Итак, первый шаг алгоритма, заключающийся в приведении исходной задачи линейного программирования к канонической форме, выполнен. Второй шаг заключается в том, что необходимо выбрать начальный опорный план задачи, а для этого предварительно необходимо выбрать исходный базис заданной системы векторов (речь идет о векторах исходной системы ограничений).

Еще из курса высшей математики студенты должны усвоить понятие базиса и способы выделения базиса из заданной системы векторов. Если речь идет о выделении любого базиса, то проще всего брать единичный базис, т.е.

базис, образованный из единичных векторов, т.к. они всегда линейно независимы.

Для данной задачи таким базисом будет Б1 = (A 3, A 4, A 5, A 6 ). Отсюда следует, что переменные x3, x4, x5, x6 будут базисными. Зная, что опорный план – это допустимое базисное решение системы ограничений (5.4), легко можно его найти, придав свободным переменным x1, x2 нулевое значение.

Итак, начальным опорным планом для решения задачи будет вектор X Б = (0;0;60;40;81;56).

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

Таким образом, нам необходимо проверить на оптимальность опорный план X Б = (0;0;60;40;81;56) и z (X Б ) = 0.

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

Таблица 5.1.

Опишем симплекс-таблицу 5.1. В первой строке шапки симплекс-таблицы указаны векторы исходной системы ограничений задачи, а во второй – коэффициенты при переменных в целевой функции задачи. В первом столбце (столбец Б 1 ) указаны векторы, образующие базис заданной системы векторов, а во втором столбце – коэффициенты целевой функции при базисных переменных.

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

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

Особо необходимо сказать о третьем столбце (столбец В ). В нем стоят значения базисных переменных в соответствующем опорном плане. Студент должен точно уяснить, что опорный план – это по-другому названное допустимое решение, а поэтому для того, чтобы выписать опорный план, соответствующий симплекс-таблице, необходимо свободным переменным придать нулевое значение, а значение базисных переменных выбирается из столбца В. Поэтому, заполнив симплекс-таблицу 5.1, мы можем сразу же записать Х Б = (0;0;60;40;81;56).

Последняя строка называется индексной. В третьем столбце этой строки стоит значение целевой функции при проверяемом опорном плане z(X Б ) = 0, а во всех остальных клетках индексной строки стоят оценки оптимальности zj - Cj для всех векторов исходной задачи. Здесь zj - значение целевой функции, если в нее вместо переменных подставить коэффициенты разложения вектора A j по векторам базиса, а Cj - коэффициент целевой функции при соответствующей переменной. Для первой симплекс-таблицы коэффициенты индексной строки рассчитываются по следующим формулам:

Эти формулы легко реализуются на составленной таблице, так как суммы в них представляют скалярное произведение вектора СБ соответственно на все остальные векторы таблицы.

Проверка выбранного опорного плана на оптимальность осуществляется по соображениями, вытекающими из теоремы оптимальности.

Проверяемый опорный план будет оптимальным в том случае, если оценки оптимальности для всех векторов будут неположительными. Воспользуемся этим критерием для проверки на оптимальность опорного плана, представленного в таблице 5.1. Проверяемый опорный план X Б = (0;0;60;40;81;56) не является оптимальным, т.к. в индексной строке имеются положительные оценки для векторов A1 и A 2. Необходимо перейти к новому опорному плану, а это значит, что нужно выбрать и новый базис.

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

Студенты должны четко уяснить, что в базис можно вводить только вектор, которому соответствует положительная оценка оптимальности. Если же таких оценок несколько, то в базис вводится вектор, которому соответствует max 0 j (z j c j ), где 0 j - симплексное отношение для вектора A j. На практике z c > часто для уменьшения предварительных расчетов в базис вводят вектор, которому соответствует наибольшая положительная оценка оптимальности. Мы так и поступим. В нашем случае в базис будем вводить вектор A 2, т.к. ему соответствует наибольшая из положительных оценок который соответствует вектору A 2, вводящемуся в базис, называется направляющим столбцом.

Для определения вектора, выводящегося из базиса, определяется симплексное отношение по формуле:

здесь j - индекс вектора, вводящегося в базис.

Симплексное отношение соответствует вектору A 6, а значит этот вектор будет выводиться из базиса. Строка, соответствующая базисному вектору A 6, называется направляющей строкой, а на пересечении направляющей строки и направляющего столбца стоит разрешающий элемент. Выделим направляющий столбец и направляющую строку. Теперь базис будет состоять из векторов ( A 3, A 4, A 5, A 2 ) = Б2 и необходимо пересчитать симплексную таблицу.

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

Модификация 1 (правило 1). Воспользуемся двумя элементарными преобразованиями Гаусса:

А) элементы направляющей строки можно делить на разрешающей элемент;

Б) элементы направляющей строки умножаем на нужное число и осуществляем векторное сложение с определяемой другой строкой таблицы (в т.ч. и с индексной строкой).

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

- элементы направляющей строки делятся на разрешающий элемент;

- направляющий столбец записывается единичным;

- те строки и столбцы, которые имеют в направляющем столбце или строке нули, записываются в новую симплекс-таблицу без изменений;

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

Это же правило можно пояснить следующей мнемосхемой и выразить в виде формулы:

В формуле (5.10) xpq - разрешающий элемент таблицы; xij - рассчитываемый элемент таблицы; xij - элемент таблицы, стоящий на месте рассчитываемого старой симплекс-таблицы; xiq и xpj - элементы, стоящие на диагонали составленного четырехугольника, на которой не стоит разрешающий элемент.

Пересчитаем теперь по первому правилу симплекс-таблицу 5.1. Так как разрешающий элемент равен 8, то направляющая строка делится на 8.

Примечание.

Так как в базис вместо вектора A 6 теперь включен вектор A 2, то в новой симплекс-таблице в столбце Б2 на месте вектора A 6 должен стоять A 2, а вместо коэффициента С6 в столбце С Б должен стоять коэффициент С2.

Наша задача при пересчете – сделать столбец для вектора A 2 единичным.

Для этого необходимо сделать нули с помощью векторного сложения направляющей строки с другими строками таблицы. Сделаем, например, на месте элемента x12 = 3 нуль. Для этого умножим направляющую строку на (-3/8) и сложим ее с первой строкой. Тогда получим:

- 21 0 –3 0 0 0 –3/8 - направляющая, умноженная на (-3/8) Результат записываем на месте первой строки в новую симплекс-таблицу.

Аналогично переcчитывается вторая строка таблицы.

Строку для вектора A 5 при записи в новую симплекс-таблицу пересчитывать не надо, т.к. в направляющем столбце элемент x32 = 0.

Индексная строка преобразовывается путем сложения ее с направляющей строкой, умноженной на (-5/8).

Результаты вычислений записываются в табл. 5.2.

Заполнением симплекс-таблицы 5.2 заканчивается первая итерация симплекс алгоритма. Дальнейшее решение задачи заключается в повторении вышеописанной итерации.

Опять рассматривается индексная строка. В ней есть положительная оценка оптимальности для вектора А1, а это значит, что соответствующие этой таблице опорный план X Б = (0;7;39;5;81;0) и z(Х Б ) = 35 не являются оптимальными. Необходимо еще раз перейти к новому опорному плану.

Выбираем в качестве направляющего столбец для вектора А1 (ему соответствует положительная оценка оптимальности z1 – c1 = 4) и определяем вектор, выводящийся из базиса, путем расчета симплексного отношения:

01 соответствует строке для вектора А 4, а поэтому вектор А 4 будет выводиться из базиса. Соответствующая ему строка будет направляющей.

Разрешающим элементом будет x21 = 2. Выделим в симплекс-таблице 5. направляющую строку и столбец.

Для пересчета симплекс-таблицы 5.2 воспользуемся второй модификацией – правилом четырехугольника. Для этого разделим направляющую строку на разрешающий элемент, запишем в новую таблицу направляющий столбец в виде единичного, перенесем строку для вектора А 2 и столбцы для векторов А 3, А 2, А 5 в новую таблицу без изменений, т.к. им соответствуют в направляющем столбце и направляющей строке нули. Остальные элементы таблицы пересчитаем по формуле (5.10).

Покажем, например, как будет пересчитан элемент таблицы x16. Для этого элемента таблицы показан четырехугольник.

Заполним симплекс-таблицу 5.3.

Таблица 5.3.

Этой таблице соответствует опорный план X Б = (5 / 2;7;24;0;117 / 2;0) и значение целевой функции z(Х Б ) = 45.

Как видно, значение целевой функции еще уменьшилось, а значит сделан еще один шаг к оптимуму.

Просмотрим опять оценки оптимальности в индексной строке. Видим, что для вектора А6 оценка оптимальности z6 – c6 = 5/8 положительна, значит, проверяемый опорный план опять не является оптимальным и необходимо еще раз перейти к новому опорному плану. Для этого будем вводить в базис вектор А6, а выводить А 3. Разрешающим элементом будет x16 = 12/8. В результате пересчета по методу полных жордановых исключений получим симплекс-таблицу 5.4.

Этой таблице соответствует опорный план X Б = (15 / 2;5;0;0;27 / 2;16) и z (Х Б ) = 55. Проверим его на оптимальность, для чего рассмотрим в индексной строке оценки оптимальности. Так как в индексной строке стоят все отрицательные или нулевые элементы, то проверяемый опорный план является оптимальным, а значение целевой функции минимально. Таким образом, Х opt = (15 / 2;5;0;0;27 / 2;16 ), z min = 55.

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

Получен ответ: Х opt = (15 / 2;5), z max = 55. Вернемся к экономической постановке задачи и прокомментируем полученное решение. Предприятие должно выпускать 7,5 кг вещества В1 и 5 кг вещества В2. При этом будет получен доход в количестве 55 единиц. Такой же результат был получен при графическом решении.

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

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

Если в целевую функцию, стремящуюся к минимуму, добавить искусственные переменные с очень большими положительными коэффициентами М, то эти переменные будут стремиться к нулю.

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

Если же исходная задача неразрешима, то это обнаруживается в результате решения новой задачи.

Рассмотрим пример решения задачи с помощью искусственного базиса.

Пусть задача имеет каноническую форму:

Так как в ограничениях (5.11) нет единичного базиса, вводим искусственные базисные переменные x5 и x6: Б1 = ( А 5, А6 ), x5 0, x6 0. В целевую функцию z переменные x5 и x6 добавим с очень большими положительными коэффициентами M. Получим расширенную задачу Опорный план расширенной задачи будет являться опорным планом исходной задачи, если x5 = 0, x6 = 0. Если будем решать задачу (5.15) – (5.16), то очевидно, что x5 и x6 стремятся к нулю.

Решение оформляем в симплексных таблицах.

Таблица 5.5.

X Б = (0;0;0;0;5;8). Расчет индексной строки:

Вся индексная строка разбивается на две подстроки. В предпоследней записываем свободные члены выражения z(Х Б ) и Zj - Cj, в последней – коэффициенты при М.

Решается задача с помощью симплексных преобразований при условии, что критерием оптимальности является последняя индексная строка. Наибольшая положительная оценка Zj - Cj = 3. Вводим в базис вектор А1. Симплексное отношение при j = соответствует вектору А6, который выводится из базиса.

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

Таблица 5.6.

X Б = (4;0;0;0;1;0) определяется из третьего столбца симплексной табл. 5.6.

Направляющий столбец соответствует наибольшей положительной оценке в последней индексной строке z2 – c2 = 5\2. А 2 вводим в базис. Следует обратить внимание на то, что в направляющем столбце единственное число больше нуля (5\2), значит, симплексное отношение находить не следует, первая строка направляющая и А 5 выводится из базиса. Векторы А 5 и А6, соответствующие искусственным переменным x5 и x6, не рассчитываем, так как они выведены из базиса.

Таблица 5.7.

(Zj - Cj) в последней индексной строке равны 0, искусственные переменные выведены из базиса, значит, x5 = 0, x6 = 0, X Б = (21 / 5;2 / 5;0;0;0;0).

Получен опорный план исходной задачи и z(Х Б ) = 10. Этот план проверяется на оптимальность на основании предпоследней индексной строки.

Минимум функции не достигнут, так как z4 – c4 = 7 > 0.

Продолжаем симплексные преобразования, ориентируясь на предпоследнюю строку. Пересчет даст нам табл. 5.8.

Таблица 5.8.

Достигнут минимум функции z, так как все оценки индексной строки Zj – Ci 0. Оптимальный план единственный, потому что свободные векторы А и А 3 имеют отрицательные оценки Z2 – C2 = - 35; Z3 – C3 = -1. При x1 = 3; x2 = 0;

x3 = 0; x4 = 2; zmin = -4.

Рассмотрим пример, когда задача не имеет допустимых решений.

Задача (5.17), (5.18), (5.19) задана в общей форме. Перейдем к канонической форме Полный единичный базис выделить нельзя, поэтому во второе уравнение добавим искусственную базисную переменную x6. Получим расширенную задачу:

Решаем задачу (5.23) – (5.25) симплексным методом, оформляя решение в таблицах.

Таблица 5.9.

Направляющая строка может быть либо I, либо III. Выбираем третью, чтобы разрешающий элемент был «I». Вводим в базис А 2, выводим А 5.

Таблица 5.10.

В нижней строке Zj - Cj все оценки Zj - Cj 0, при этом искусственная переменная осталась в базисе x6 = 1, и это ее минимальное значение. Значит, исходная задача не имеет допустимых решений, системы ограничений (5.20), (5.21) и (5.17), (5.18) несовместные.

§ 6. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ. ПРИМЕР ЭКОНОМИКОМАТЕМАТИЧЕСКОГО АНАЛИЗА СТАНДАРТНОЙ ПЛАНОВОЙ ЗАДАЧИ

В § 2 был рассмотрен пример задачи определения оптимального плана выпуска веществ.

Получена математическая модель:

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

Припишем каждому из видов ресурсов, используемых для производства веществ, двойственную оценку, соответственно равную y1, y2, y3 и y4.

Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка ресурса, используемого на производство единицы вещества каждого вида, была не меньше цены единицы вещества данного вида, т.е. y1, y2, y и y4 должны удовлетворять следующей системе неравенств:

Общая оценка ресурсов, используемых на производство веществ, составит Задачи (6.1) – (6.3) и (6.4) – (6.6) образуют пару задач, называемую в линейном программировании двойственной парой.

Каждой задаче линейного программирования можно сопоставить двойственную задачу по следующим правилам:

1. Во всех ограничениях исходной задачи свободные члены должны находиться справа, а члены с неизвестными - слева.

2. Ограничения-неравенства исходной задачи должны иметь знаки, направленные в одну строну.

3. Если целевая функция в исходной задаче минимизируется, ограничениянеравенства следует записать со знаком «», тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограниченийнеравенств будут «».

4. Каждому ограничению исходной задачи соответствует переменная в двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).

5. Коэффициенты при переменных в ограничениях двойственной задачи коэффициентов при переменных исходной задачи.

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

Отметим также, что соотношение двойственности взаимное, т.е. задача, двойственная по отношению к двойственной, совпадает с исходной.

Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре ограничения прямой и двойственной задач являются нестрогими неравенствами и, следовательно, переменные обеих задач могут принимать только неотрицательные значения.

Запишем симметричную пару двойственных задач для общего случая.

Исходная задача:

Двойственная задача:

Дальнейший анализ будем проводить на примере симметричных двойственных задач. Основой для анализа являются следующие теоремы.

Первая теорема двойственности.

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

Вторая теорема двойственности.

Если при подстановке координат оптимального плана x ( x 1, x 0,..., x 0 ) в систему ограничений исходной задачи i-e ограничение выполняется как строгое неравенство, то соответствующая i-я переменная в оптимальном плане y ( y 1,..., y 0 ) двойственной задачи равна нулю, т.е.

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

удовлетворяют условиям:

Экономическая трактовка результатов этой теоремы состоит в следующем.

Положительную двойственную оценку могут иметь лишь ресурсы, полностью используемые в оптимальном плане, оценки не полностью используемых ресурсов всегда равны нулю.

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

Если же выпускать данную продукцию нерационально и она не вошла в оптимальный план, то и по оценкам ее производство будет убыточным, т.е.

оценка затрачиваемых ресурсов окажется выше цены этой продукции.

Третья теорема двойственности.

В оптимальном плане двойственной задачи значение переменной y 0 i численно равно частной производной функции zmax (b1, b2, …, bm) по данному аргументу, т.е.

Таким образом, оптимальные оценки определяют влияние свободных членов bi условий – ограничений задачи линейного программирования на оптимальную величину целевой функции, т.е. вычисление наряду с оптимальным планом связанных с ним оптимальных оценок позволяет взвесить относительную важность отдельных ресурсов для достижения поставленной в задаче цели.

Вернемся к рассмотренной ранее паре симметричных двойственных задач определения оптимального плана выпуска веществ (6.1) – (6.3) и нахождения оптимальных двойственных оценок используемых ресурсов (6.4) – (6.6).

При симплексном решении одной из задач получаем в итоговой таблице решение и для двойственной задачи. Именно для исходной задачи решение считываем из столбца свободных членов последней таблицы, которая уже отвечает признакам оптимальности. В свою очередь, решение двойственной задачи считывается из индексной строки. Именно y1 считывается из индексной строки в том столбце, которому соответствовала базисная переменная в первой строке первой симплексной таблицы, y2 - для второй строки начальной таблицы и т.д. в предположении, что цены для базисных переменных в первой таблице равны нулю.

Решение исходной задачи приведено в таблице (5.4). Из этой таблицы видно, что оптимальным планом производства веществ является такой, при котором изготовляется 7,5 кг вещества B1( x 10 = 7,5) и 5 кг вещества B2( x 0 = 5).

При данном плане производства остаются неиспользованными 13,5 ед. ресурса веществ равна 55.

Из таблицы также видно, что оптимальным решением двойственной задачи является y10 = 5/12, y20 = 3/4, y30 = 0, y40 = 0 ( знаки поменяли в связи с тем, что прямую задачу на max решали как задачу на min ). Переменные y1 и y обозначают двойственные оценки единицы ресурсов соответственно первого и второго видов. Эти оценки отличны от нуля, а ресурсы первого и второго видов полностью используются при оптимальном плане производства веществ.

Двойственные оценки ресурсов третьего и четвертого видов равны нулю. Эти виды ресурсов не полностью используются при оптимальном плане производства веществ.

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

Так, увеличение количества ресурса P1 на одну единицу приведет к тому, что появится возможность найти новый оптимальный план производства веществ, при котором общая стоимость изготовляемых веществ возрастет на 5/12 и станет При этом числа, стоящие в столбце вектора A3 табл. (5.4) показывают, что указанное увеличение общей стоимости изготовляемых веществ может быть достигнуто за счет увеличения выпуска вещества B1 на 5/24 ед. и сокращения выпуска вещества B2 на 1/12 ед. Вследствие этого использования ресурса P уменьшится на 8/12 ед., а ресурса P3 увеличится на 45/24 ед.. Аналогично увеличение на одну единицу ресурса P2 позволит найти новый оптимальный план производства веществ, при котором общая стоимость изготавливаемых веществ возрастет на 3/4 ед. и составит 55 + = 55 3/4 (ед.).

Это будет достигнуто в результате увеличения выпуска вещества B2 на 2/ использования ресурса P3 уменьшиться на 9/8 ед, а ресурса P4 увеличится на 2 ед.

Вычисляя минимальное значение целевой функции двойственной задачи видим, что оно совпадает с максимальным значением целевой функции исходной задачи.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем:

Оба ограничения двойственной задачи выполняются как строгие равенства.

Это означает, что двойственные оценки ресурсов, используемых для производства единицы соответственно веществ B1 и B2, равны в точности их ценам. Поэтому выпускать эти два вида веществ по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

Двойственные оценки могут служить инструментом анализа и принятия правильных решений в условиях постоянно меняющегося производства. Так, например, с помощью двойственных оценок ресурсов возможно сопоставление оптимальных условных затрат и результатов производства Предположим, в рассмотренной ранее задаче определения оптимального плана выпуска веществ B1 и B2 появилась возможность выпуска еще одного вида веществ B3. Затраты на 1 кг вещества B3 составляют: a13 =12 единиц ресурса P1, a23 = 8 единиц ресурса P2, a33 = 1 единица ресурса P3 и a43 = 3 единицы ресурса P4;

цена 1 кг вещества B3 равна C3 = 10 (грн.). Требуется установить, даст ли прибыль включение в план выпуска дополнительно вещества B3 и какой должна быть цена 1 кг вещества B3, чтобы его производство было рентабельным.

Используя двойственные оценки ресурсов, сопоставим дополнительные затраты на ресурсы в расчете на 1 кг вещества B3 с ценой его реализации.

1 0 + 3 0 = 11 (грн), больше цены продукции C3 = 10 (грн), поэтому вещество B не следует включать в план выпуска. Необходимость повторного решения задачи в изменившихся условиях отпадает. Чтобы производство вещества B3 стало рентабельным, его цена должна составлять не менее 11 (грв.).

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

Для задачи (6.1) – (6.3) найдем интервалы устойчивости (неизменности) двойственных оценок по отношению к изменениям запасов ресурсов каждого вида. Определим, изменятся ли эти оценки, если увеличить запасы каждого из ресурсов на 10 единиц: а) в отдельности; б) одновременно. Найдем соответствующее изменение максимальной выручки от реализации продукции с помощью двойственных оценок.

первоначально 60, 40, 81 и 56 единицам, изменились соответственно на величины b1, b2, b3 и b4.

Для определения интервалов устойчивости двойственных оценок по отношению к изменениям ресурсов каждого вида необходимо определить такие значения b1, b2, b3, b4, при которых среди компонент вектора нет отрицательных.

Здесь D-1 - матрица, обратная матрице B, составленной из компонент векторов базиса A6, A1, A5, A2, который определяет оптимальный план задачи (5. – 5.3 ). В рассматриваемом примере элементы матрицы B-1 могут быть взяты из столбцов векторов ( табл. 5.4) A3, A4, A5, A6, образующих первоначальный единичный базис.

Условие неотрицательности компонент указанного выше вектора приводит к следующей системе неравенств:

Предположим, что изменяется только запас ресурса P1, а остальные запасы ресурсов остаются неизменными: b2 = b3 = b4 = 0.

Тогда получим:

неизменности двойственных оценок ресурсов запас ресурса P1 может изменяться в пределах от 36 до 67 единиц.

Аналогично можно получить, что Таким образом, при запасе только одного из ресурсов P1 в пределах от 36 до 67 единицы или P2 - в пределах от 28 до 48 единиц, или P3 - в пределах не менее 67 единицы, или P4 - в пределах не менее 40 единиц оптимальное решение двойственной задачи остается прежним, т.е.

Следовательно, увеличение на 10 единиц в отдельности запаса ресурса P (равного 60 единицам) или P2 (40 единиц) приведет к изменению их двойственных оценок, а запаса ресурса P3 (81 единица) или P4 ( 56 единиц) оставит оценки этих ресурсов прежними (равными нулю ). В результате с помощью полученных двойственных оценок ресурсов можно найти соответствующее изменение максимальной выручки zmax.

Если запасы ресурсов изменяются одновременно, то исследование устойчивости двойственных оценок усложняется, т.к. в данном случае нужно найти многогранник решений системы неравенств (6.7). Однако всегда можно проверить, удовлетворяют ли конкретные изменения запасов ресурсов системе (6.7). Так, в нашей задаче при одновременном увеличении запасов всех ресурсов на 10 единиц т.е. при b1 = b2 = b3 = b4 = 10 все неравенства системы (6.7) справедливы, следовательно, оптимальное решение двойственной задачи остается прежним, т.е.

Поэтому изменение максимальной выручки составит:

0 10 = 35/3 (грн).

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

Определим нормы заменяемости ресурсов P1 и P2.Составим отношение двойственных оценок ресурсов P1 и P2, т.е. y10 : y20 = 5/12 : = = 5 : 9, т.е. для максимизации общей выручки каждые дополнительные 9 единиц ресурса P1, эквивалентны дополнительным 5 единицам ресурса P2. Вывод верен в пределах устойчивости двойственных оценок, когда изменения запасов ресурсов b1, b2, b3, b4 удовлетворяют системе (6.7).

Всего выше изложенного достаточно, чтобы приступить к решению задачи первого задания контрольной работы. Однако для облегчения работы студентовзаочников проведем дополнительное полное исследование примера, аналоги которого как раз и входят в варианты первого задания. Такое дополнительное рассмотрение оправдано прежде всего из-за того, что ниже приведенный комплекс исследований мало освещен в доступной учебной литературе. Для цельности изложения целый ряд фрагментов будет повторять уже изложенный материал.

Пример.

При изготовлении товаров двух наименований Т1 и Т2 используется три ресурса S1, S2, S3. Пусть выпуск товаров исчисляется в тоннах [т], а используемые ресурсы в условных единицах [усл. ед.], причем единица измерения для каждого ресурса своя.

Известны и приведены в таблице 6.1 нормозатраты каждого из ресурсов на производство 1 тонны каждого из товаров [усл.ед./т], имеющийся объем ресурсов [усл. ед.], цены за 1 тонну производимых товаров [тыс.грн./т].

Таблица 6.1.

Товары производство товаров, [усл.ед./т] я объемы теневых цен товаров, [т] Необходимо определить оптимальные планы выпуска товаров x1, x2, т.е.

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

Математическая модель. Решение всякой оптимизационной задачи начинается с составления математической модели этой задачи.

Как уже показано в таблице 6.1, через x1 обозначен план выпуска товара Т1, через x2 - план выпуска товара Т2. Так как планы выпуска товаров не могут быть отрицательными, то фиксируем ограничения x1 0, x2 0. Кроме этого, мы ограничены наличными объемами ресурсов S1, S2, S3. Отсюда возникнут три ограничения-неравенства. Очевидно, что если aij - нормозатраты i-го ресурса на производство единицы (1 т) j-го товара, то aijxj - затраты i-го ресурса на весь план выпуска j-го товара. Учитывая, что у нас два товара, можно записать ограничение по использованию ресурса S1: a11x1 + a12x2 b1; а по второму и третьему ресурсам соответственно: a21x1 + a22x2 b2 и a31x1 + a32x2 b3. В силу численных данных в таблице 6.1 ограничения по ресурсам примут вид:

Зная цены c1 и c2 товаров, планируемых к выпуску, можно зафиксировать целевую функцию задачи: z = c1x1 + c2x2 max.

Тогда математическая модель задачи будет представлена в таком виде:

найти такие значения планов x1 и x2, которые бы удовлетворяли условиям и обеспечивали бы наибольшее значение целевой функции Получена математическая модель, которая может быть отнесена к классу стандартных плановых задач при двух планируемых товарах и трех ограничениях по ресурсам (n = 2, m = 3). Для задачи (6.9)-(6.11) может быть найден оптимальный план выпуска товаров. Вместе с тем, если обозначить через y1, y2, y - соответственно цены ресурсов S1, S2, S3 в конкретных условиях планируемого производства, то возникает возможность зафиксировать, так называемую, двойственную задачу. Как описывалось выше, эта задача будет иметь вид:

Экономически такую задачу можно интерпретировать возникшим желанием продать ресурсы, не производя товары и получая вместе с тем не меньший доход.

Именно, в (6.13) каждое слагаемое aijyi выступает как цена доли затрат i-го ресурса на производство 1 т j-го товара. Неравенство (6.13.1) фиксирует требования по первому товару (но этот товар мы уже и не собираемся выпускать), а (6.13.2) – по второму товару. Но тут же вместе с этим покупатель ресурсов стремиться минимизировать свою целевую функцию (6.14), т.е. минимизировать затраты на покупку ресурсов.

Можно образно считать, что y1 и y2 это «теневые» цены ресурсов в условиях конкретного предполагаемого выпуска товаров T1 и T2.

Графическое решение конкретной задачи.

Задачу (6.9)-(6.11) будем считать исходной.

Задачу (6.12)-(6.14) – двойственной к исходной.

На рис. 6.1 представлено графическое решение задачи (6.9)-(6.11). Сущность и правила графического решения были изложены ранее при рассмотрении основного примера. Область допустимых планов – пятиугольник ОАВСD – образован ограничениями неотрицательности переменных исходной задачи (6.9) и ограничениями по наличию ресурсов (6.10). Граница ограничения (6.10.1), т.е.

прямая линия x1+4x2=28 проходит через точки А и В. Граница ограничения (6.10.2) – через точки В и С; граница ограничения (6.10.3) – через точки С и D. На рис. 6.1 показан градиент целевой функции (grad z) и уровни этой функции (z=const). По прохождению уровней в области допустимых планов очевидно, что максимум заданной целевой функции наступает в точке C(7;3). Следовательно, Zmax=7x1c+3x2c=7·7+3·3=58 (тыс.грн). Если подставить координаты оптимальной точки С в ограничения (6.10), то обнаружим, что нестрогое неравенство (6.10.1) выполняется как неравенство:

в случае отрицательности 2 знак минус можно отнести к числителю.

Задачу (8.1)- (8.3) мы ниже перепишем в новых переменных, которые будут обозначены через y0, y1, y2, …, yn. Для этого полагаем Тогда в новых переменных задача (8.1)-(8.3) примет вид По отношению к новым переменным yj задача (8.6) – (8.9) уже является задачей линейного программирования, которую можно решать с помощью симплексного метода. Приведем дополнительные пояснения к получению записей (8.6)- (8.9). Начнем с целевой функции. В исходном виде целевая функция имеет вправе записать Поэтому для целевой функции получаем что как раз и совпадает с записью (8.9). А теперь поясним получение остальных записей (8.6)- (8.8). В исходной задаче имеем требования (j = 1, n ), поэтому, учитывая подстановку (8.5), т.е. yj = y0 xj, и то, что и по допущению 2 > 0, можно считать справедливыми требования y j = y0x j = (8.7) умножим равенства (8.2) слева и справа на величину y0, получим И еще в условиях эквивалентной задачи мы должны учесть, что переменная y подчинена равенству как раз и отражает ту закономерность, которой должна отвечать величина y0 в эквивалентной задаче.

Преобразование задачи дробно-линейного программирования к виду (8.6)и последующее симплексное решение проиллюстрируем на следующем примере:

В задаче (8.10) условия неотрицательности сохраняем, а остальные ограничения с помощью балансирующих переменных x3 0 и x4 0 преобразуем в уравнения. Тогда получаем Если еще ввести новые переменные yj = y0xj вышеизложенной методике для задачи (8.11) можно получить линейный аналог Задача (8.12) уже является задачей линейного программирования и, если с помощью третьего уравнения исключить y0 из первого и второго уравнений, то мы получим задачу в которой в качестве базисных переменных удобно использовать переменные y3, y4, y0. В записи задачи (8.13) целевая функция переписана в том же виде, что и остальные уравнения, т.е. слева размещены все переменные, а справа – свободный член. Полученную задачу (8.13) решаем с помощью симплексных таблиц:

В первой таблице для ведущего столбика y1 имеем min,, =, что соответствует 1-й строке, она станет разрешающей.

Yопт = ;0;0; ;, max =.

Итак, Xопт = (2, 0, 0, 2), max =. Или для исходного задания задачи (8.10) x1опт = 2, x2опт = 0 и max =.

Примечание. В таблицах проводилось решение на максимум.

§ 9. РЕШЕНИЕ ЗАДАЧ ПАРАМЕТРИЧЕСКОГО

ПРОГРАММИРОВАНИЯ. АНАЛИЗ УСТОЙЧИВОСТИ

ОПТИМАЛЬНОГО ПЛАНА ВЫПУСКА ТОВАРОВ В ЗАВИСИМОСТИ ОТ

ИЗМЕНЕНИЯ ЦЕНЫ ОТДЕЛЬНОГО ТОВАРА.

Ниже приводятся образцы решения задачи с параметром в целевой функции и задачи с параметром в правых частях условий-ограничений.

Решение примера с параметром в целевой функции:

Вводя дополнительные балансовые переменные x3 0 и x4 0 неравенства () преобразуем в уравнения, получая тем самым канонический вид нашей задачи В первом уравнении переменную x3 можно взять в качестве базисной переменной, а вот во втором уравнении из-за знака минус при x4 эта переменная в обычной симплексной схеме решения не может быть использована в качестве базисной переменной. Поэтому мы во второе уравнение введем искусственную базисную переменную x5 0. Для решения по схеме М-метода искусственная базисная переменная войдет в целевую функцию с достаточно большим положительным коэффициентом М. Задача принимает вид:

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

В нашей таблице 9.1 имеется лишь одна искусственная переменная – это x5.

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

В столбиках Aj (m + 2)-й целевой строки содержатся коэффициенты при М для относительных данциговских оценок, соответствующих переменным xj задачи. По признакам неоптимальности в этой строке начинается первый этап минимизации целевой функции z.

Таблица 9.1.

Имеем дело с первым базисным решением X Б = (0,0,5,0,3).

В табл 9.1 признак неоптимальности на минимум имеет место в столбиках A1 и A2. Пусть столбик A1 взят ведущим в первой симплексной операции, т.е. в базис будет вводиться вектор A1. Для определения вектора, выводимого из базиса (т.е. для определения разрешающей строки) находим симплексный минимум для столбика A1: min ; = 3, что соответствует 2-й строке (вектор A5 с искусственной базисной переменной будет выводиться из базиса). 2-я строка становится разрешающей. На пересечении ведущего столбика и разрешающей строки имеем дело с разрешающим элементом. В нашей табл. 9.1 разрешающий элемент равен 1.

Для перехода к следующей таблице надо совершить процедуры по ГауссуЖордану. Сейчас у нас будет цель - исключить переменную x1 из всех строк, кроме 2-й (разрешающей). Для исключения x1 из 1-й строки разрешающая строка умножается на «-1» и прибавляется к 1-й строке. Так как разрешающий элемент равен единице, то вторая строка переписывается без изменений. Для исключения x1 из строки m+1 разрешающая строка умножается на «-t» и прибавляется к (m+1)-й строке. И наконец, разрешающая строка умножается на «-1» и прибавляется к (m+2)-й строке.

В результате этих процедур по Гауссу-Жордану мы получим таблицу 9.2.

Таблица 9.2.

Этой таблице соответствует базисное решение X Б = (3,0,2,0,0). И так как искусственная переменная x5 стала равна нулю, мы от расширенной задачи возвращаемся к исходной. При этом (m+2)-ю строку и столбик A5 не будем учитывать в последующих таблицах. Однако у нас все же добавится строка значений относительных данциговских оценок при исследуемом фиксированном значении параметра t.

В таблице 9.2. взято для исследования значение левого конца отрезка допустимых значений параметра t [-1, 3], т.е. взято t=-1. При этом значении параметра наблюдается признак неоптимальности по столбику A2, который и берется ведущим, т.е. вектор условий A2 будет вводится в базис. Но в столбике A может быть разрешающим лишь элемент «1» во 2-й строке. А это означает, что вектор A1 будет выводиться из базиса. Совершив процедуры по Гауссу-Жордану, получим табл. 9.3.

Таблица 9.3.

Получено базисное решение X Б = (0,3,2,0), которое при t=-1 не является оптимальным, т.к. в столбике A4 мы имеем неблагоприятную относительную оценку «3». Столбик A4 будет ведущим. Разрешающим элементом будет первый элемент «1» столбика A4.

По методу Гаусса-Жордана переходим к таблице 9.4. Необходимые множители для реализации метода таковы: первая строка умножается на 1 и прибавляется ко второй строке; первая строка умножается на (-5/2+t/2) и прибавляется к третьей строке; первая строка умножается на (-3) и прибавляется к последней строке.

Таблица 9.4.

В таблице 9.4 добавлена для исследования новая дополнительная строка, что будет прокомментировано ниже. Таблице же соответствует оптимальное при еще значениях X Б останется оптимальным. Это, очевидно, будет при всех t, когда относительные оценки таблицы 9.4 будут неположительные, т.е. когда будет выполняться неравенство:

Из первого неравенства имеем t, из второго t 5. Для удовлетворения обоих неравенств t должно быть меньше меньшего, т.е. t. Эта граница продиктована столбиком A1.

Итак, при t [-1, ] X Б = (0,5,0,2) будет оставаться оптимальным.

Для оценки задачи при t = в табл. 9.4 добавлена строка относительных оценок при этом значении t. Видно, что по нулевой оценке в столбце A1 мы имеем признак наличия других оптимальных решений. Столбик A1 берется ведущим, в нем выбирается единственный возможный разрешающий элемент и делаем пересчет к табл. 9.5, в которой строка (zj-cj) при t=-1 уже исключается. По ГауссуЖордану вторая строка табл. 9.4 умножается на (5/2-3/2t) и прибавляется к строке (m+1).

Таблица 9. Получено новое оптимальное базисное решение (оптимальная угловая точка) при значении параметра t = : X Б = (5,0,0,2). Это решение остается оптимальным и при других значениях t, что определяется из требований неположительности относительных данциговских оценок - по столбику A2:

- t 0 t 0, oба неравенства выполняются при t. Итак, точка X Б = (5,0,0,2) остается X Б остается оптимальной при t ;3. И еще: в таблице 9.5 при t = относительная оценка целевой функции в столбике A2 становится равной нулю, что свидетельствует о возможных других оптимальных базисных решениях. Но если столбик A2 взять ведущим в табл. 9.5, то мы вернемся к предыдущей таблице 9.4. Исследование окончено.

Можно привести синтезированный ответ:

1) при t 1; оптимальное базисное решение X 1опт = X Б = (0,5,0,2) и 2) при t ;3 оптимальное базисное решение X 2 = X Б = (5,0,0,2) и 3) при t = оптимальный результат на отрезке X 1опт X 2, т.е. в любой точке Задачу с параметром в правой части ограничений также рассмотрим на конкретном примере:

Вводя неотрицательные балансовые переменные x3 и x4, преобразуем ограничения задачи к каноническому виду:

Для решения задачи без параметра по обычной схеме симплексного метода нам надо было бы в первое уравнение ввести неотрицательную искусственную базисную переменную. Но так как справа в уравнении имеется параметр, то достаточно само уравнение слева и справа умножить на «-1», тогда x3 в первом уравнении предстанет с коэффициентом «+1». Переменную x3 можно будет формально взять в качестве базисной переменной в первом уравнении.

Тогда в целом задача примет следующий канонический вид с выделенными базисными переменными x3 и x4:

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

Канонизированный пример отображаем в симплексной таблице 9.6.

Таблица 9.6.

Таблице 9.6 соответствует базисное решение X Б = (0,0,6 + 2µ,4 + µ).

По столбцу A2 в строке m+1 мы наблюдаем признак неоптимальности. Пусть столбик A2 будет ведущим. В этом столбике лишь во второй строке стоит элемент, который может быть разрешающим. Итак, вектор A2 вводится в базис, а вектор A4 выводится из базиса. Совершая процедуры по Гауссу-Жордану с помощью выделенной разрешающей строки, получаем таблицу 9.7.

Таблица 9.7.

Во второй симплексной таблице нашего примера получен признак оптимальности. X Б = (0,4 + µ,2 + 4µ,0) - этот оптимальный результат будет допустимым при неотрицательности всех его компонент, т.е. при таких µ, Оба неравенства выполняются при µ. Граница продиктована первой строкой таблицы 9.7, которая и станет разрешающей в рамках двойственного симплекс-метода. Так как в этой строке лишь один отрицательный элемент «-1»

(стоит в столбике A1), то он становится разрешающим. С помощью 1-й разрешающей строки табл 9.7 производится пересчет к табл 9.8.

Таблица 9.8.

В таблице 9.8 признак оптимальности сохраняется для полученного базисного решения X Б = (2 4µ,6 + 5µ,0,0). Результат этот будет оптимальным и допустимым при µ, подчиняющимся неравенствам:

При таких µ X Б будет допустимым и оптимальным.

Выше мы уже получили, что при µ,+ оптимальным и допустимым будет базисное решение X Б. Остается доисследовать возможности оптимальных результатов при µ <. Граница µ = продиктована второй строкой табл. 9.8.

Но в этой строке нет ни одного отрицательного элемента, который мог бы стать разрешающим в схеме двойственного симплекс-метода. Следовательно, при µ < мы не можем получить допустимых решений.

Подытожим полученные результаты по примеру с параметром в правых частях ограничений.

При µ < допустимых решений не существует.

При µ имеем оптимальное решение X Б = (2 4µ,6 + 5µ,0,0) и при этом z = -10 - 13µ.

При µ имеем оптимальное решение X Б = (0,4 + µ,2 + 4µ,0) и при этом z = -4 - µ.

Разумеется, что при µ = X Б и X Б совпадают и равны (0, 7/2, 0, 0) и соответственно zmin( µ = ) = - 7/2.

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

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

Этот анализ мы проведем на следующем конкретном примере:

Сначала приводим задачу к каноническому виду:

Затем с помощью симплекс-метода определяем оптимальное решение и исследуем устойчивость этого решения в зависимости от отдельно изменяемой цены 1-го (x1) или 2-го (x2) товара. Причем исследование будем делать с помощью варьируемого параметра для каждой из цен.

Таблица 9.9.Симплексное решение:

В таблице 9.9 зафиксирован канонический вид задачи. Этой таблице соответствует базисное решение X Б = (0,0,36,16,42).

Пусть A1 - ведущий столбик в табл. 9.9.

Определяем симплексный минимум min ; ; = 14, что соответствует 3й строке. Она будет разрешающей.

С помощью процедур по Гауссу-Жордану переходим к таблице 9.10.

Таблица 9.10.

Мы видим по строке (m + 1) новой таблицы, что получен оптимальный результат X Б = (14,0,22,2,0) и zmax = 126.

Согласно этому результату надо выпускать 1-й товар в количестве x1 = 14, а второй товар не выпускать, т.к. x2 = 0.

В силу того, что x3 = 22, x4 = 2 и x5 = 0, при реализации оптимального плана X = ( x 10 = 14; x 0 = 0) у нас останутся не реализованными 22 единицы первого ресурса и 2 единицы 2-го ресурса. Третий ресурс будет использован полностью (x5 = 0).

Просматривая еще (m + 1)-ю строку оптимальной таблице 9.10 видим, что по столбику внебазисной переменной A2 данциговская относительная оценка равна «0». Это означает, что имеются и другие оптимальные решения. Но мы займемся исследованием на устойчивость лишь полученного решения x0 = (14; 0).

Именно нами будет исследоваться устойчивость от возможной вариации цен.

Сначала исследование проведем по цене 1-го товара, т.е. пусть для цены этого товара введен варьирующий параметр t1 (т.е. t1 = c1) и цена предстает в записи Это варьирование учтем в уже полученной оптимальной таблице 9.10.

Таблица 9.11 в строках 1, 2, 3 столбиков от B и A1, до A5 копирует все, что получено в таблице 9.10, а вот в обрамлении таблицы цена 1-го товара предстает в виде (9 + t1) и в целевой строке сделан новый расчет относительных оценок.