close

Вход

Забыли?

вход по аккаунту

?

Zaharova Bednyak Osnovy teorii prinyatiya reshenij uchebnoe posobie 2018

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
Кафедра Информационных систем и технологий
О.И. Захарова, С.Г. Бедняк
ОСНОВЫ ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ
Учебное пособие
Самара, ИУНЛ ПГУТИ,
2018
ББК 32.973
УДК 681.3.06
Рекомендовано к изданию методическим советом ПГУТИ,
протокол №49 от 8.05.2018 г.
Захарова О.И., Бедняк С.Г. Основы теории принятия решений: Учебное пособие. – Самара: ИУНЛ ПГУТИ, 2018. – 164 с.
Рецензент:
Кандидат экономических наук, доцент, научный сотрудник
ИПУСС РАН Т.В. Моисеева
В учебном пособии рассмотрены вопросы основ теории принятия
решений, использования современных информационных технологий в задачах поддержки принятия управленческих решений.
Предназначается для менеджеров разных уровней и профессиональной ориентации, интересующихся вопросами использования информационных технологий в практике анализа и исследования систем управления предприятиями и организациями, а также студентов, обучающихся
по направлению подготовки 09.03.02 – «Информационные системы и технологии».
ISBN
 Захарова О.И.
 Бедняк С.Г.
Оглавление
Введение: Процессы принятия решений ....................................................... 5
1. Общая постановка задачи о принятии решения ................................ 6
1.1 Математическое программирование .................................................... 6
1.2 Подробное рассмотрение задачи линейного программирования11
1.3 Свойства основной задачи линейного программирования .......... 25
1.3.1 Геометрическое истолкование задачи линейного
программирования ............................................................................................ 25
1.3.2 Примеры решения задач линейного программирования с
помощью геометрическое истолкования .................................................... 33
2. Симплекс метод ......................................................................................... 41
2.1 Составление математической модели задачи................................... 64
2.2 Пример решения задач симплекс – методом с уточнением базиса
70
2.2.1 Симплекс-метод, решение задачи с начальным базисом...... 70
2.2.2 Симплекс-метод, решение задачи с искусственным базисом
77
2.3 Особые случаи применения симплекс-метода ................................. 81
3. Определение двойственной задачи....................................................... 83
3.1 Связь между решениями прямой и двойственной задач............... 87
3.2 Геометрическая интерпретация двойственных задач ................... 89
3.3 Экономическая интерпретация двойственных задач .................... 95
4. Транспортная задача ..............................................................................110
4.1 Стандартная транспортная задача ....................................................114
4.2 Модификации стандартной транспортной задачи........................116
4.3 Многопродуктовые модели..................................................................117
5. Целочисленные задачи линейного программирования. Метод
Гомори .................................................................................................................123
5.1 Определение оптимального плана задачи целочисленного
программирования. .........................................................................................127
5.2 Метод Гомори ..........................................................................................128
6. Статистический анализ .........................................................................140
6.1 Шкалы измерения ..................................................................................140
6.2 Меры центральной тенденции ............................................................144
6.3 Статистические гипотезы.....................................................................148
6.4 Статистический критерий ...................................................................150
6.5 Уровни значимости ................................................................................155
6.6 Мощность критерия...............................................................................156
3
7. Классификация задач и методов их решения .................................158
7.1 Классификация задач и методов их решения .................................159
7.2 Принятие решения о выборе метода математической обработки
162
Введение: Процессы принятия решений
Процесс принятия решений преследует определенные
цели, например, повысить производительность работы цеха
или распределить финансовые вложения наиболее эффективным образом.
С формальной точки зрения любая целенаправленная
деятельность, связанная с принятием управленческих решений должна характеризоваться показателями ее эффективности – критериями или целевыми функциями, которые
определяют наиболее желаемые решения задачи с точки менеджера или исследователя.
В общем случае цели, связанные с эффективностью получения желаемых решений, могут содержать в себе определенные противоречия, которые составляют дисбаланс целей
– ситуация, которая способна привести к полной неэффективности принимаемого решений.
На практике принятие управленческих решений связано
с наличием определенных ресурсов (материальных, информационных, экономических и т.п.).
Связи между такими ресурсами необходимо рассматривать как связанный план между количественными объемами
ресурсов. Этот план должен включать в себя зависимости
между ресурсами, ресурсные ограничения, возможные количественные показатели эффективности принимаемого решения.
5
1. Общая постановка задачи о принятии решения
Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование и
взаимодействие”. В научных исследованиях – позволяют выделить важнейшие научные проблемы, найти способы их
изучения, предопределяют развитие экспериментальной базы
и теоретического аппарата. При создании новой техники –
составляют важный этап в проектировании машин,
устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере –
используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют достигать цели при минимальных
затратах трудовых, материальных и сырьевых ресурсов.
В классической математике методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании.
1.1 Математическое программирование
Математическое программирование является одним из
разделов исследования операций – прикладного направления
кибернетики, используемого для решения практических организационных задач. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).
Значительное число задач, возникающих в обществе,
связано с управляемыми явлениями, т. е. с явлениями, регулируемыми на основе сознательно принимаемых решений.
При том ограниченном объеме информации, который был
доступен на ранних этапах развития общества, принималось
оптимальное в некотором смысле решение на основании интуиции и опыта, а затем, с возрастанием объема информации
об изучаемом явлении, – с помощью ряда прямых расчетов.
Так происходило, например, создание календарных планов
работы промышленных предприятий.
Совершенно иная картина возникает на современном
промышленном предприятии с многосерийным и многономенклатурным производством, когда объем входной информации столь велик, что его обработка с целью принятия
определенного решения невозможна без применения современных электронных вычислительных машин. Еще большие
трудности возникают в связи с задачей о принятии наилучшего решения.
Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:
1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит
за пределы математики.
2-й этап. Построение математической модели рассматриваемой проблемы, т. е. запись в математических терминах
качественной модели. Таким образом, математическая модель – это записанная в математических символах абстракция
реального явления, так конструируемая, чтобы анализ ее давал возможность проникнуть в сущность явления. Математическая модель устанавливает соотношения между совокупностью переменных – параметрами управления явлением. Этот
7
этап включает также построение целевой функции переменных, т. е. такой числовой характеристики, большему (или
меньшему) значению которой соответствует лучшая ситуация с точки зрения принимающего решения.
Итак, в результате этих двух этапов формируется соответствующая математическая задача. Причем, второй этап
уже требует привлечения математических знаний.
3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение
математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.
Широкий класс задач управления составляют такие
экстремальные задачи, в математических моделях которых
условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования.
На третьем этапе, пользуясь математическим аппаратом,
находят решение соответствующих экстремальных задач.
Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не
мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания
программ для ЭВМ, реализующих те или иные алгоритмы,
либо использования уже имеющихся стандартных программ.
4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким
образом, на этом этапе устанавливается степень адекватности
модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:
1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса.
При этом уточняется входная информация о моделируемом
объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).
2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений,
возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности
предприятия. Тогда эксплуатация модели включает в себя
сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
В математическом программировании можно выделить
два направления.
К первому, уже вполне сложившемуся направлению –
собственно математическому программированию – относятся детерминированные задачи, предполагающие, что вся исходная информация является полностью определенной.
Ко второму направлению – так называемому стохастическому программированию – относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят слу9
чайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности
зачастую производится в условиях неполной информации о
реальной ситуации, в которой будет выполняться план. Или,
скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными
помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке
задач, главным образом из-за сложности анализа исходной
информации.
Традиционно в математическом программировании
выделяют следующие основные разделы.
Линейное программирование – целевая функция линейна, а множество, на котором ищется экстремум целевой
функции, задается системой линейных равенств и неравенств.
В свою очередь в линейном программировании существуют
классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач.
Нелинейное программирование – целевая функция и
ограничения нелинейны. Нелинейное программирование
принято подразделять следующим образом:
Выпуклое программирование – целевая функция выпукла (если рассматривается задача ее минимизации) и выпукло
множество, на котором решается экстремальная задача.
Квадратичное программирование – целевая функция
квадратична, а ограничениями являются линейные равенства
и неравенства.
Многоэкстремальные задачи. Здесь обычно выделяют
специализированные классы задач, часто встречающихся в
приложениях, например, задачи о минимизации на выпуклом
множестве вогнутых функций.
Важным разделом математического программирования
является целочисленное программирование, когда на переменные накладываются условия целочисленности.
Целью математического программирования является
создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов – создание
эффективных вычислительных способов получения приближенного решения.
1.2 Подробное рассмотрение задачи линейного программирования
Рассмотрим более подробно задачу линейного программирования.
Пример 1.
Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного
изделия для каждого из типов оборудования указаны в
табл. 1. В ней же указан общий фонд рабочего времени
каждого из типов используемого оборудования, а также
прибыль от реализации одного изделия каждого вида.
11
Таблица 1
Тип
оборудования
Затраты времени
(станко-часы)
на обработку одного
изделия
каждого вида
Общий фонд
рабочего
времени оборудования
(часы)
А
В
С
Фрезерное
2
4
5
120
Токарное
1
8
6
280
Сварочное
7
4
5
240
Шлифовальное
4
6
7
360
Прибыль (руб.)
10
14
12
Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.
Решение. Предположим, что будет изготовлено x1 единиц
изделий вида А, единиц – вида В и единиц – вида С.
Тогда для производства такого количества изделий потребуется затратить
станко-часов фрезерного оборудования.
Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам:
При этом так как количество изготовляемых изделий не
может быть отрицательным, то
(1)
Далее, если будет изготовлено x1 единиц изделий вида А,
единиц изделий вида В и единиц изделий вида С, то
прибыль от их реализации составит
Таким образом, приходим к следующей математической
задаче: дана система
(2)
четырех линейных неравенств с тремя неизвестными
и линейная функция относительно этих же переменных
. (3)
13
Требуется среди всех неотрицательных решений системы
неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем.
Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую
модель исходной задачи.
Так как функция (3) линейная, а система (2) содержит
только линейные неравенства, то задача (1) - (3) является
задачей линейного программирования.
Пример 2.
Продукцией городского молочного завода являются молоко, кефир и сметана, расфасованные в бутылки. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны
заняты специальные автоматы в течение 3,25 часов. Всего
для производства цельномолочной продукции завод может
использовать 136000 кг молока. Основное оборудование
может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно
производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции не имеется никаких ограничений.
Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы при-
быль от ее реализации была максимальной. Составить математическую модель задачи.
Решение. Предположим, что молочный завод будет ежедневно производить x1 тонн молока,
тонн кефира и
тонн сметаны. Тогда ему для изготовления этой продукции необходимо
кг молока.
Так как завод может использовать ежедневно не более
136000 кг молока, то должно выполняться неравенство
Аналогичные рассуждения, проведенные относительно
возможного использования линий разлива цельномолочной
продукции и автоматов по расфасовке сметаны, позволяют
записать следующие неравенства:
Так как ежедневно должно вырабатываться не менее 100 т
молока, то
. Далее, по своему экономическому
смыслу переменные и могут принимать только лишь
неотрицательные значения:
Общая прибыль от
реализации x1 тонн молока, тонн кефира и тонн сметаны равна
руб. Таким образом, приходим к
следующей математической задаче. Дана система
15
(4)
четырех линейных неравенств с тремя неизвестными x1, ,
и линейная функция относительно этих же переменных
(5)
требуется среди всех неотрицательных решений системы
неравенств (4) найти такое, при котором функция (5) принимает максимальное значение. Так как система (4) представляет собой совокупность линейных неравенств и
функция (5) линейная, то исходная задача является задачей
линейного программирования.
Пример 3.
На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-м варианте раскроя
ткани изготовляется
деталей i-го вида
100 м2
, а величи-
на отходов при данном варианте раскроя равна м2. Зная,
что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое
количество деталей каждого вида при минимальных общих
отходах. Составить математическую модель задачи.
Решение. Предположим, что по j-му варианту раскраивается
сотен м2 ткани. Поскольку при раскрое 100 м2 ткани
по j-му варианту получается деталей i-го вида, по всем
вариантам раскроя из используемых тканей будет получено
деталей i-го вида. Так как должно быть изготовлено
талей данного вида, то
де-
Общая величина отходов по всем вариантам раскроя ткани
составит
Таким образом, приходим к следующей математической
задаче: найти минимум функции
(6)
при условии, что ее переменные удовлетворяют системе
уравнений
(7)
и условию неотрицательности
Сформулированная задача является задачей линейного
программирования, так как функция (6) линейная, а система (7) содержит только лишь линейные уравнения.
17
Ранее были рассмотрены примеры задач линейного программирования. Во всех этих задачах требовалось найти
максимум или минимум линейной функции при условии,
что ее переменные принимали неотрицательные значения и
удовлетворяли некоторой системе линейных уравнений
или линейных неравенств либо системе, содержащей как
линейные неравенства, так и линейные уравнения. Каждая
из этих задач является частным случаем общей задачи линейного программирования.
Определение 1.
Общей задачей линейного программирования называется
задача, которая состоит в определении максимального (минимального) значения функции
(8)
при условиях
(9)
(10)
(11)
где
- заданные постоянные величины и
.
Определение 2.
Функция (8) называется целевой функцией (или линейной
формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.
Определение 3.
Стандартной (или симметричной} задачей линейного
программирования называется задача, которая состоит в
определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.
Определение 4.
Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении
условий (10) и (11), где k = 0 и l = п.
Определение 5.
Совокупность чисел
, удовлетворяющих
ограничениям задачи (9) – (11), называется допустимым
решением (или планом).
Определение 6.
План
, при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.
19
Значение целевой функции (8) при плане Х будем обозначать через
. Следовательно, X* – оптимальный план
задачи, если для любого Х выполняется неравенство
[соответственно
].
Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них с
помощью несложных преобразований может быть переписана в форме другой задачи. Это означает, что если имеется способ нахождения решения одной из указанных задач,
то тем самым может быть определен оптимальный план
любой из трех задач.
Чтобы перейти от одной формы записи задачи линейного
программирования к другой, нужно уметь, во-первых, сводить задачу минимизации функции к задаче максимизации;
во-вторых, переходить от ограничений-неравенств к ограничениям-равенствам и наоборот; в-третьих, заменять переменные, которые не подчинены условию неотрицательности.
В том случае, когда требуется найти минимум функции
симума функции
.
, можно перейти к нахождению мак, поскольку
Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в
ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничениенеравенство
преобразуется в ограничение-равенство
(12)
а ограничение-неравенство
– в ограничение-равенство
(13)
В то же время каждое уравнение системы ограничений
можно записать в виде неравенств:
(14)
Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в
ограничения-равенства равно числу преобразуемых неравенств.
Вводимые дополнительные переменные имеют вполне
определенный экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то
числовое значение дополнительной переменной в плане за21
дачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.
Отметим, наконец, что если переменная , не подчинена
условию неотрицательности, то ее следует заменить двумя
неотрицательными переменными
и
, приняв
.
Пример 4.
Записать в форме основной задачи линейного программирования следующую задачу: найти максимум функции
при условиях
Решение. В данной задаче требуется найти максимум
функции, а система ограничений содержит четыре неравенства. Следовательно, чтобы записать ее в форме основной задачи, нужно перейти от ограничений-неравенств к
ограничениям-равенствам. Так как число неравенств, входящих в систему ограничений задачи, равно четырем, то
этот переход может быть осуществлен введением четырех
дополнительных неотрицательных переменных. При этом к
левым частям каждого из неравенств вида“ “ соответствующая дополнительная переменная прибавляется, а из
левых частей каждого из неравенств вида “
” вычитается. В результате ограничения принимают вид уравнений:
Следовательно, данная задача может быть записана в форме основной задачи таким образом: максимизировать
функцию
при условиях
Пример 5.
Записать задачу, состоящую в минимизации функции
при условиях
в форме основной задачи линейного программирования.
Решение. В данной задаче требуется найти минимум целевой функции, а система ограничений содержит три нера23
венства. Следовательно, чтобы записать ее в форме основной задачи, вместо нахождения минимума функции F нужно найти максимум функции F1 = -F при ограничениях,
получающихся из ограничений исходной задачи добавлением к левым частям каждого из ограничений-неравенств
вида “ ” дополнительной неотрицательной переменной и
вычитанием дополнительных переменных из левых частей
каждого из ограничений-неравенств вида “ ”.
Следовательно, исходная задача может быть записана в
форме основной задачи линейного программирования так:
найти максимум функции
при условиях
Пример 6.
Записать в форме стандартной задачи линейного программирования следующую задачу: найти максимум функции
при условиях
Решение. Методом последовательного исключения неизвестных сведем данную задачу к следующей: найти максимум функции
при условиях
Последняя задача записана в форме основной для задачи,
состоящей в нахождении максимального значения функции
при условиях
Целевая функция задачи преобразована с помощью подстановки вместо и их значений в соответствии с уравнениями системы ограничений задачи.
1.3
1.3.1
Свойства основной задачи линейного программирования
Геометрическое истолкование задачи линейного программирования
Рассмотрим основную задачу линейного программирования. Она состоит в определении максимального значения
25
функции
при
условиях
Перепишем эту задачу в векторной форме: найти максимум
функции
F=CX (15)
при условиях
(16)
(17)
где
,
CX – скалярное произведение;
и – m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных
членах системы уравнений задачи:
Определение 7.
План
называется опорным планом, основной задачи линейного программирования, если система
векторов
, входящих в разложение (16) с положительны-
ми коэффициентами
линейно независима.
Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных
компонент не может быть больше, чем т.
Определение 8.
Опорный план называется невырожденным, если он содержит ровно т положительных компонент, в противном
случае он называется вырожденным.
Свойства основной задачи линейного программирования
(15) – (17) тесным образом связаны со свойствами выпуклых множеств.
Определение 9.
Пусть
– произвольные точки евклидова пространства . Выпуклой линейной комбинацией этих точек
называется сумма
где – произвольные неотрицательные числа, сумма которых равна 1:
Определение 10.
Множество называется выпуклым, если вместе с любыми
двумя своими точками оно содержит и их произвольную
выпуклую линейную комбинацию.
Определение 11.
27
Точка Х выпуклого множества называется угловой, если
она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух других различных точек данного множества.
Теорема 1.
Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).
Определение 12.
Непустое множество планов основной задачи линейного
программирования называется многогранником решений, а
всякая угловая точка многогранника решений – вершиной.
Теорема 2.
Если основная задача линейного программирования имеет
оптимальный план, то максимальное значение целевая
функция задачи принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция задачи принимает более чем в одной вершине, то она
принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.
Теорема 3.
Если система векторов
линейно независима и такова, что
в разложении (16)
(18)
где все
то точка
вершиной многогранника решений.
Теорема 4.
является
Если
– вершина многогранника решений, то
векторы , соответствующие положительным
ложении (16), линейно независимы.
в раз-
Сформулированные теоремы позволяют сделать следующие выводы.
Непустое множество планов основной задачи линейного
программирования образует выпуклый многогранник.
Каждая вершина этого многогранника определяет опорный
план. В одной из вершин многогранника решений (т. е. для
одного из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Если максимальное
значение функция принимает более чем в одной вершине,
то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
Вершину многогранника решений, в которой целевая
функция принимает максимальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более двух переменных или задача, записанная в форме основной, содержит не более двух свободных переменных, т. е.
, где n – число переменных, r
– ранг матрицы, составленной из коэффициентов в системе
ограничений задачи.
Найдем решение задачи, состоящей в определении максимального значения функции
(19)
29
при условиях
(20)
(21)
Каждое из неравенств (20), (21) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
и
. В том случае, если система неравенств (20), (21)
совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как
множество точек пересечения данных полуплоскостей –
выпуклое, то областью допустимых решений задачи (19) –
(21) является выпуклое множество, которое называется
многоугольником решений (введенный ранее термин “многогранник решений” обычно употребляется, если
).
Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.
Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника
решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция
ограничена сверху. При указанных условиях в одной из
вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной
вершины построим линию уровня
(где h – некоторая постоянная), проходящую через многоугольник
решений, и будем передвигать ее в направлении вектора
до тех пор, пока она не пройдет через ее послед-
нюю общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план
данной задачи.
Заканчивая рассмотрение геометрической интерпретации
задачи (19) – (21), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1 - 4.
Рис. 1 характеризует такой случай, когда целевая функция
принимает максимальное значение в единственной точке А.
Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 3 изображен случай, когда целевая функция не ограничена сверху
на множестве допустимых решений, а на рис. 4 – случай,
когда система ограничений задачи несовместна.
31
Отметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается
от нахождения ее максимального значения при тех же
ограничениях лишь тем, что линия уровня
передвигается не в направлении вектора
а в противоположном направлении. Таким образом, отмеченные
выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.
Итак, нахождение решения задачи линейного программирования (19) – (21) на основе ее геометрической интерпретации включает следующие этапы:
1. Строят прямые, уравнения которых получаются в результате замены в ограничениях (20) и (21) знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.
4. Строят вектор
5. Строят прямую
угольник решений.
.
, проходящую через много-
6. Передвигают прямую
в направлении вектора
, в результате чего-либо находят точку (точки), в которой
целевая функция принимает максимальное значение, либо
устанавливают неограниченность сверху функции на множестве планов.
7. Определяют координаты точки максимума функции и
вычисляют значение целевой функции в этой точке.
1.3.2 Примеры решения задач линейного программирования с помощью геометрическое истолкования
Пример 7.
Для производства двух видов изделий А и В предприятие
использует три вида сырья. Нормы расхода сырья каждого
вида на изготовление единицы продукции данного вида
приведены в табл. 2. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество
сырья данного вида, которое может быть использовано
предприятием.
33
Таблица 2
Вид сырья
Нормы расхода сырья Общее ко(кг) на одно изделие личество
сырья (кг)
А
В
I
12
4
300
II
4
4
120
III
3
12
252
Прибыль от реализации одного изделия
(руб.)
30
40
Учитывая, что изделия А и В могут производиться в любых
соотношениях (сбыт обеспечен), требуется составить такой
план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной,
Решение. Предположим, что предприятие изготовит x1 изделий вида А и изделий вида В. Поскольку производство
продукции ограничено имеющимся в распоряжении предприятия сырьем каждого вида и количество изготовляемых
изделий не может быть отрицательным, должны выполняться неравенства
Общая прибыль от реализации x1 изделий вида А и
лий вида В составит
изде-
Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной
системы линейных неравенств требуется найти такое, при
котором функция F принимает максимальное значение.
Найдем решение сформулированной задачи, используя ее
геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы
ограничений и условиях неотрицательности переменных
знаки неравенств заменим на знаки точных равенств и
найдем соответствующие прямые:
Эти прямые изображены на рис. 5. Каждая из построенных
прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному
неравенству, а другой – нет. Чтобы определить искомую
полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой при35
надлежит эта точка, в противном случае – другая полуплоскость.
Найдем, например, полуплоскость, определяемую неравенством
Для этого, построив прямую
(на рис. 5 эта прямая I), возьмем какуюнибудь точку, принадлежащую одной из двух полученных
полуплоскостей, например точку О(0; 0). Координаты этой
точки удовлетворяют неравенству
значит,
полуплоскость, которой принадлежит точка О(0; 0), определяется неравенством
Это и показано стрелками на рис. 5.
Пересечение полученных полуплоскостей и определяет
многоугольник решений данной задачи.
Как видно из рис. 5, многоугольником решений является
пятиугольник OABCD. Координаты любой точки, принад-
лежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное
значение. Чтобы найти указанную точку, построим вектор
и прямую
где h – некоторая постоянная такая, что прямая
имеет общие точки с
многоугольником решений. Положим, например, h = 480 и
построим прямую
(рис. 5).
Если теперь взять какую-нибудь точку, принадлежащую
построенной прямой и многоугольнику решений, то ее координаты определяют такой план производства изделий А
и В, при котором прибыль от их реализации равна 480 руб.
Далее, полагая h равным некоторому числу, большему чем
480, мы будем получать различные параллельные прямые.
Если они имеют общие точки с многоугольником решений,
то эти точки определяют планы производства изделий А и
В, при которых прибыль от их реализации превзойдет 480
руб.
Перемещая построенную прямую
в направ-
лении вектора видим, что последней общей точкой ее с
многоугольником решений задачи служит точка В. Координаты этой точки и определяют план выпуска изделий А и
В, при котором прибыль от их реализации является максимальной.
37
Найдем координаты точки В как точки пересечения прямых II и III. Следовательно, ее координаты удовлетворяют
уравнениям этих прямых
Решив эту систему уравнений, получим
Следовательно, если предприятие изготовит 12 изделий вида А
и 18 изделий вида В, то оно получит максимальную прибыль, равную
Пример 8.
Найти максимум и минимум функции
виях
при усло-
Решение. Построим многоугольник решений. Для этого в
неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки
точных равенств:
Построив полученные прямые, найдем соответствующие
полуплоскости и их пересечение (рис. 6).
Как видно из рис. 6, многоугольником решений задачи является треугольник АВС. Координаты точек этого треугольника удовлетворяют условию неотрицательности и
неравенствам системы ограничений задачи. Следовательно,
задача будет решена, если среди точек треугольника АВС
найти такие, в которых функция
принимает максимальное и минимальное значения. Для нахождения этих
точек построим прямую
(число 4 взято произвольно) и вектор
39
Передвигая данную прямую параллельно самой себе в
направлении вектора
видим, что ее последней общей
точкой с многоугольником решений задачи является точка
С. Следовательно, в этой точке функция F принимает максимальное значение. Так как С – точка пересечения прямых I и II, то ее координаты удовлетворяют уравнениям
этих прямых:
Решив эту систему уравнений, получим
образом, максимальное значение функции
Таким
Для нахождения минимального значения целевой функции
задачи передвигаем прямую
в направлении, противоположном направлению вектора
В этом случае, как видно из рис. 6, последней общей точкой прямой с
многоугольником решений задачи является точка А. Следовательно, в этой точке функция F принимает минимальное значение. Для определения координат точки А решаем
систему уравнений
откуда
Подставляя найденные значения переменных в целевую функцию, получим
2. Симплекс метод
Решение любой задачи линейного программирования
можно найти симплексным методом. Прежде чем применять
указанный метод, следует записать исходную задачу в форме
основной задачи линейного программирования, если она не
имеет такой формы записи.
Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный
план и каждый ее опорный план является невырожденным).
Указанный переход возможен, если известен какой-нибудь
исходный опорный план. Рассмотрим задачу, для которой
этот план можно непосредственно записать.
Пусть требуется найти максимальное значение функции
при условиях
Здесь
и
– заданные постоянные
числа
Векторная форма данной задачи имеет следующий вид:
найти максимум функции
(22)
41
при условиях
(23)
(24)
где
Так как
то
по
определению
опорного
плана
является опорным планом данной задачи (последние
компонент вектора Х равны нулю).
Этот план определяется системой единичных векторов
которые образуют базис m-мерного пространства.
Поэтому каждый из векторов
а также вектор
могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть
Положим
векторы
Так как
– единичные, то
и
а
Теорема 5
(признак оптимальности опорного плана). Опорный
план
задачи (22) – (24) является оп-
тимальным, если
для любого j
Теорема 6.
Если
для некоторого j=k и среди чисел
нет положительных
, то целевая функция (22) задачи
(22) – (24) не ограничена на множестве ее планов.
Теорема 7.
Если опорный план Х задачи (22) – (24) невырожден и
, но среди чисел
есть положительные (не все
),
то существует опорный план X' такой, что
Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить
целесообразность перехода к новому опорному плану.
Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если
условия задачи и первоначальные данные, полученные после
определения исходного опорного плана, записать так, как показано в табл. 3.
В столбце С6 этой таблицы записывают коэффициенты
при неизвестных целевой функции, имеющие те же индексы,
что и векторы данного базиса.
43
В столбце записывают положительные компоненты
исходного опорного плана, в нем же в результате вычислений
получают положительные компоненты оптимального плана.
Столбцы векторов
представляют собой коэффициенты
разложения этих векторов по векторам данного базиса.
В табл. 3 первые m строк определяются исходными
данными задачи, а показатели (m+1)-й строки вычисляют. В
этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном
плане, а в столбце вектора – значение
Значение Zj находится как скалярное произведение вектора
на вектор
Значение
на вектор :
равно скалярному произведению вектора P0
После заполнения таблицы 3 исходный опорный план
проверяют на оптимальность. Для этого просматривают элементы
-й строки таблицы. В результате может иметь
место один из следующих трех случаев:
1)
для j=m+1,
этому в данном случае числа
2)
(при
). По-
для всех j от 1 до n;
для некоторого j, и все соответствующие этому
индексу величины
3)
для некоторых индексов j, и для каждого тако-
го j , по крайней мере, одно из чисел
положительно.
В первом случае на основании признака оптимальности
исходный опорный план является оптимальным. Во втором
случае целевая функция не ограничена сверху на множестве
планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой
функции увеличится. Этот переход от одного опорного плана
к другому осуществляется исключением из исходного базиса
какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов имеющий индекс j, для которого
.
Пусть, например,
и решено ввести в базис вектор
Для определения вектора, подлежащего исключению из
базиса, находят
для всех
Пусть этот минимум
достигается при i=r. Тогда из базиса исключают вектор , а
число
называют разрешающим элементом.
Столбец и строку, на пересечении которых находится
разрешающий элемент, называют направляющими.
После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты
разложения векторов через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана–Гаусса. При
этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам
(25)
45
а коэффициенты разложения векторов через векторы
нового базиса, соответствующего новому опорному плану, –
по формулам
(26)
После вычисления и согласно формулам (25) и (26)
их значения заносят в табл. 4. Элементы
-й строки этой
таблицы могут быть вычислены либо по формулам
(27)
(28)
либо на основании их определения.
Таблица 3
Таблица 4
Наличие двух способов нахождения элементов
-й
строки позволяет осуществлять контроль правильности проводимых вычислений.
Из формулы (27) следует, что при переходе от одного
опорного плана к другому наиболее целесообразно ввести в
базис вектор , имеющий индекс j, при котором максимальным
по
абсолютной
величине
является
число
. Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в
базис, определять, исходя из максимальной абсолютной величины отрицательных чисел
. Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же
индекс, как и максимальное из чисел
, определяемых дан-
ными числами
Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (25)-(28), так и по правилам,
47
непосредственно вытекающим из них. Эти правила состоят в
следующем.
В столбцах векторов, входящих в базис, на пересечении
строк и столбцов одноименных векторов проставляются единицы, а все остальные элементы данных столбцов полагают
равными нулю.
Элементы векторов и
в строке новой симплекстаблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце
в
строке вводимого вектора проставляют величину , где k –
индекс вводимого вектора.
Остальные элементы столбцов вектора
и
новой
симплекс-таблицы вычисляют по правилу треугольника. Для
вычисления какого-нибудь из этих элементов находят три
числа:
1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;
2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;
3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки
вновь вводимого в базис вектора (как отмечено выше, эта
строка получается из строки исходной симплекс-таблицы делением ее элементов на разрешающий элемент).
Эти три числа образуют своеобразный треугольник, две
вершины которого соответствуют числам, находящимся в
исходной симплекс-таблице, а третья – числу, находящемуся
в новой симплекс-таблице. Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают
произведение второго и третьего.
После заполнения новой симплекс-таблицы просматривают элементы
-й строки. Если все
, то новый
опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную
выше последовательность действий, находят новый опорный
план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее
неразрешимость.
При нахождении решения задачи линейного программирования мы предполагали, что эта задача имеет опорные
планы и каждый такой план является невырожденным. Если
же задача имеет вырожденные опорные планы, то на одной
из итераций одна или несколько переменных опорного плана
могут оказаться равными нулю. Таким образом, при переходе
от одного опорного плана к другому значение функции может остаться прежним. Более того, возможен случай, когда
функция сохраняет свое значение в течение нескольких итераций, а также возможен возврат к первоначальному базису.
В последнем случае обычно говорят, что произошло зацикливание. Однако при решении практических задач этот случай встречается очень редко, поэтому мы на нем останавливаться не будем.
Итак, нахождение оптимального плана симплексным
методом включает следующие этапы:
1. Находят опорный план.
2. Составляют симплекс-таблицу.
3. Выясняют, имеется ли хотя бы одно отрицательное
число
. Если нет, то найденный опорный план оптимален.
Если же среди чисел
имеются отрицательные, то либо
49
устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка –
минимальным из отношений компонент столбца вектора к
положительным компонентам направляющего столбца.
5. По формулам (25) – (28) определяют положительные
компоненты нового опорного плана, коэффициенты разложения векторов Pj по векторам нового базиса и числа
,
.
Все эти числа записываются в новой симплекс-таблице.
6. Проверяют найденный опорный план на оптимальность. Если план неоптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае
получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.
Пример 9.
Для изготовления различных изделий А, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида,
цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл. 5.
Вид сырья
I
II
III
А
В
С
Таблица 5
Общее количество
сырья (кг)
18
6
5
15
4
3
12
8
3
360
192
180
Нормы затрат сырья
(кг) на одно изделие
Цена одного изделия
9
10
16
(руб.)
Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.
Составить план производства изделий, при котором
общая стоимость всей произведенной предприятием продукции является максимальной.
Решение. Составим математическую модель задачи.
Искомый выпуск изделий А обозначим через x1, изделий В –
через , изделий С – через . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные
должны удовлетворять следующей
системе неравенств:
(29)
Общая стоимость произведенной предприятием продукции при условии выпуска x1 изделий А, изделий В и
изделий С составляет
51
(30)
По своему экономическому содержанию переменные
могут принимать только лишь неотрицательные значения:
(31)
Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы
неравенств (29) требуется найти такое, при котором функция
(30) принимает максимальное значение.
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограниченийнеравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений
Эти дополнительные переменные по экономическому
смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например,
– это неиспользуемое количество сырья I вида.
Преобразованную систему уравнений запишем в векторной форме:
где
Поскольку среди векторов
имеются три
единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план
Х=(0; 0; 0; 360; 192; 180), определяемый системой трехмер-
ных единичных векторов
которые образуют базис
трехмерного векторного пространства.
Составляем симплексную таблицу для I итерации (табл.
6), подсчитываем значения
опорный план на оптимальность:
и проверяем исходный
Для векторов базиса
i
1
2
3
4
Базис Сб P0
P4
р5
p6
0
0
0
360
192
180
0
9
10
16
Таблица 6
0 0 0
P1
P2
Р3
p4 Р5
P6
18
6
5
-9
15
4
3
-10
12
8
3
-16
1
0
0
0
0
0
1
0
0
1
0
0
Как видно из таблицы 6, значения всех основных переменных
равны нулю, а дополнительные переменные
принимают свои значения в соответствии с ограничениями
задачи. Эти значения переменных отвечают такому “плану”,
при котором ничего не производится, сырье не используется
и значение целевой функции равно нулю (т. е. стоимость
произведенной продукции отсутствует). Этот план, конечно,
не является оптимальным.
Это видно и из 4-й строки табл. 6, так как в ней имеется
три отрицательных числа:
и
Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продук53
ции, но и показывают, на сколько увеличится эта сумма при
введении в план единицы того или другого вида продукции.
Так, число – 9 означает, что при включении в план производства одного изделия А обеспечивается увеличение выпуска продукции на 9 руб. Если включить в план производства по одному изделию В и С, то общая стоимость изготовляемой продукции возрастет соответственно на 10 и 16 руб.
Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий С.
Это же необходимо сделать и на основании формального
признака симплексного метода, поскольку максимальное по
абсолютной величине отрицательное число
стоит в 4-й
строке столбца вектора Р3. Следовательно, в базис введем
вектор Р3. определяем вектор, подлежащий исключению из
базиса.
Для
этого
находим
Найдя число
мы тем самым с экономической
точки зрения определили, какое количество изделий С предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного
вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий С, которое может быть изготовлено предприятием, равно
т. е. ограничивающим фактором
для производства изделий С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье II вида будет полностью
использовано.
Следовательно, вектор Р5 подлежит исключению из базиса. Столбец вектора Р3 к 2-я строка являются направляющими. Составляем таблицу для II итерации (табл. 7).
i
1
2
3
4
Базис Сб
P4
p3
p6
0
16
0
Р0
72
24
108
384
9
10
16
0
Таблица 7
0
0
P1
P2
P3
p4
p5
Р6
9
3/4
11/4
3
9
1/2
3/2
-2
0
1
0
0
1
0
0
0
-3/2
1/8
-3/8
2
0
0
1
0
Сначала заполняем строку вектора, вновь введенного в
базис, т. е. строку, номер которой совпадает с номером
направляющей строки. Здесь направляющей является 2-я
строка. Элементы этой строки табл. 7 получаются из соответствующих элементов таблицы 6 делением их на разрешающий элемент (т. е. на 8). При этом в столбце Сб записываем
коэффициент
, стоящий в столбце вводимого в базис
вектора .
Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк
и столбцов одноименных векторов проставляем единицы, а
все остальные элементы полагаем равными нулю.
Для определения остальных элементов табл. 7 применяем правило треугольника. Эти элементы могут быть вычислены и непосредственно по рекуррентным формулам.
55
Вычислим элементы табл. 7, стоящие в столбце вектора
Р0. Первый из них находится в 1-й строке этого столбца. Для
его вычисления находим три числа:
1) число, стоящее в табл. 6 на пересечении столбца
вектора Р0 и 1-й строки (360);
2) число, стоящее в табл. 6 на пересечении столбца
вектора P3 и 1-й строки (12);
3) число, стоящее в табл. 7 на пересечении столбца
вектора Р0 и 2-й строки (24).
Вычитая из первого числа произведение двух других,
находим искомый элемент: 360 – 12 х 24=72; записываем его
в 1-й строке столбца вектора Р0 табл. 7.
Второй элемент столбца вектора Р0 табл. 7 был уже вычислен ранее. Для вычисления третьего элемента столбца
вектора Р0 также находим три числа. Первое из них (180)
находится на пересечении 3-й строки и столбца вектора Р0
табл. 6, второе (3) – на пересечении 3-й строки и столбца вектора P3 табл. 6, третье (24) – на пересечении 2-й строки и
столбца вектора Р0 табл. 8. Итак, указанный элемент есть 180
– 24 х 3=108. Число 108 записываем в 3-й строке столбца вектора Р0 табл. 7.
Значение F0 в 4-й строке столбца этого же вектора можно найти двумя способами:
1) по
формуле
,
т.е.
2)
по правилу треугольника; в данном случае
треугольник образован числами 0, -16, 24.
Этот способ приводит к тому же результату:
0 - (-16) х 24=384.
При определении по правилу треугольника элементов
столбца вектора Р0 третье число, стоящее в нижней вершине
треугольника, все время оставалось неизменным и менялись
лишь первые два числа. Учтем это при нахождении элементов столбца вектора P1 табл. 7. Для вычисления указанных
элементов первые два числа берем из столбцов векторов P1 и
Р3 табл. 6, а третье число – из табл. 7. Это число стоит на пересечении 2-й строки и столбца вектора P1 последней таблицы. В результате получаем значения искомых элементов: 18 –
12 х (3/4) =9; 5 – 3 х (3/4) = 11/4.
Число
в 4-й строке столбца вектора P1 табл. 7
можно найти двумя способами:
1) по
формуле
2) по
правилу
Z1-С1=(C,P1)-C1
треугольника
имеем
получим
Аналогично находим элементы столбца вектора P2.
Элементы столбца вектора Р5 вычисляем по правилу
треугольника. Однако построенные для определения этих
элементов треугольники выглядят иначе.
При вычислении элемента 1-й строки указанного
столбца получается треугольник, образованный числами 0,12
и 1/8. Следовательно, искомый элемент равен 0 – 12 х (1/8) =
57
-3/2. Элемент, стоящий в 3-й строке данного столбца, равен 0
- 3 х (1 /8) = -3/8.
По окончании расчета всех элементов табл. 7 в ней получены новый опорный план и коэффициенты разложения
векторов
через базисные векторы P4, P3, P6 и значе-
ния
и
. Как видно из этой таблицы, новым опорным
планом задачи является план X=(0; 0; 24; 72; 0; 108). При
данном плане производства изготовляется 24 изделия С и
остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья
III вида. Стоимость всей производимой при этом плане продукции равна 384 руб.
Указанные числа записаны в столбце вектора Р0 табл. 7.
Как видно, данные этого столбца по-прежнему представляют
собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других
столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р2.
Число 1/2 во 2-й строке этого столбца показывает, на сколько
следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В.
Числа 9 и 3/2 в 1-й и 3-й строках вектора P2 показывают
соответственно, сколько потребуется сырья I и II вида при
включении в план производства одного изделия В, а число –
2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска
продукции в стоимостном выражении на 2 руб.
Иными словами, если включить в план производства
продукции одно изделие В, то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб.
Таким образом, числа 9 и 3/2 выступают как бы новыми
“нормами” затрат сырья I и III вида на изготовление одного
изделия В (как видно из табл. 6, ранее они были равны 15 и
3), что объясняется уменьшением выпуска изделий С.
Такой же экономический смысл имеют и данные
столбца вектора Р1 табл. 7. Несколько иное экономическое
содержание имеют числа, записанные в столбце вектора Р5.
Число 1/8 во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на 1/8 ед. Одновременно потребовалось бы дополнительно 3/2 кг сырья I вида и 3/8 кг сырья III
вида. Увеличение выпуска изделий С на 1/8 ед. приведет к
росту выпуска продукции на 2 руб.
Из изложенного выше экономического содержания
данных табл. 7 следует, что найденный на II итерации план
задачи не является оптимальным. Это видно и из 4-й строки
табл. 7, поскольку в столбце вектора P2 этой строки стоит отрицательное число – 2. Значит, в базис следует ввести вектор
P2, т. е. в новом плане следует предусмотреть выпуск изделий
В. При определении возможного числа изготовления изделий
В следует учитывать имеющееся количество сырья каждого
вида, а именно: возможный выпуск изделий В определяется
для
, т. е. находим
Следовательно, исключению из базиса подлежит вектор
Р4 иными словами, выпуск изделий В ограничен имеющимся
в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить
8 изделий В. Число 9 является разрешающим элементом, а
59
столбец вектора P2 и 1-я строка табл. 7 являются направляющими. Составляем таблицу для III итерации (табл. 8).
i
1
2
3
4
Базис Сб
P2
P3
Р6
10
16
0
P0
8
20
96
400
9
10
16
0
Таблица 8
0
0
P1
P2
P3
p4
p5
Р6
1
1/4
5/4
5
1
0
0
0
0
1
0
0
1/9
-1/18
-1/6
2/9
-1/6
5/24
-1/8
5/3
0
0
1
0
В табл. 8 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р2. Элементы этой строки получаем из элементов 1-й
строки табл. 7 делением последних на разрешающий элемент
(т.е. на 9). При этом в столбце Сб данной строки записываем
.
Затем заполняем элементы столбцов векторов базиса и
по правилу треугольника вычисляем элементы остальных
столбцов. В результате в табл. 8 получаем новый опорный
план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов
через базисные векторы
и соответ-
ствующие значения и
Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, табл. 8.
В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и
Следовательно, план выпуска продукции, включающий
изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью ис-
пользуется сырье I и II видов и остается неиспользованным
96 кг сырья III вида, а стоимость производимой продукции
равна 400 руб.
Оптимальным планом производства продукции не
предусматривается изготовление изделий А. Введение в план
выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки
столбца вектора P1, где число 5 показывает, что при данном
плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5
руб.
Решение данного примера симплексным методом можно было бы проводить, используя лишь одну таблицу
(табл. 9). В этой таблице последовательно записаны одна за
другой все три итерации вычислительного процесса.
i
1
2
3
4
1
2
3
4
1
2
3
Базис Сб Р0
P4
р5
p6
P4
p3
p6
P2
p3
p6
0
0
0
0
16
0
0
16
0
360
192
180
0
72
24
108
384
8
20
96
9
10
16
0
Таблица 9
0
0
P1
P2
P3
p4
p5
Р6
18
6
5
-9
9
3/4
11/4
3
1
1/4
5/4
15
4
3
-10
9
1/2
3/2
-2
1
0
0
12
8
3
-16
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
1/9
-1/18
-1/6
0
1
0
0
-3/2
1/8
-3/8
2
-1/6
5/24
-1/8
0
0
1
0
0
0
1
0
0
0
1
61
4
400 5
0
Пример 10.
Найти максимум функции
0
2/9
5/3
0
при услови-
ях
Решение. Систему уравнений задачи запишем в векторной форме:
где
Так как среди векторов
имеется три
единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0, 0,
20, 24; 0; 18). Составляем симплексную таблицу (табл. 10) и
проверяем, является ли данный опорный план оптимальным.
Базис Сб
i
1
2
3
4
p3
P4
p6
0
0
0
Р0
2 -6
0
0
Таблица 10
5
0
P1 P2
P3
p4
p5
Р6
1
0
0
0
0
1
0
0
1
3
-12
-5
0
0
1
0
20 24 -2 1
18
-1 -2
0
3 -1
-2 6
Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному
плану. Это можно сделать, так как в столбцах векторов P1 и
p5, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому
опорному плану введем в базис вектор p5 и исключим из базиса вектор p4. Составляем таблицу II итерации.
i
1
2
3
Базис Сб Р0
p3
P5
p6
0
5
0
12
8
114
40
2
-6
0 0
Таблица 11
5 0
P1
P2
P3 p4
p5 Р6
-5/3
-1/3
-1
-11/3
5/3
-2/3
-9
8/3
1
0
0
0
0
1
0
0
-1/3
1/3
4
5/3
0
0
1
0
Как видно из табл. 11, новый опорный план задачи не
является оптимальным, так как в 4-й строке столбца вектора
P1 стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не
имеет оптимального плана.
63
Пример 1
Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства
краски используется два исходных продукта A и B. Расходы
продуктов A и B на 1 т. соответствующих красок и запасы
этих продуктов на складе приведены в таблице:
Исходный
продукт
A
B
Расход продуктов (в тоннах на 1 т. краски)
краска для
краска для
внутренних внешних
работ
работ
1
2
3
1
Запас продукта на
складе
( тонн )
3
3
Продажная цена за 1 тонну краски для внутренних работ составляет 2 000 рублей, краска для наружных работ продается по 1 000 рублей за 1 тонну. Требуется определить какое количество краски каждого вида следует производить
предприятию, чтобы получить максимальный доход.
Рассмотрим поэтапное решение этой задачи симплексметодом, который состоит из этапов: 1. Составление математической модели задачи.2. Приведение задачи к стандартному виду, т. е. выражение целевой функции и базисных переменных через свободные переменные. 3.Составление первой
симплекс-таблицы. 4. Максимальное увеличение свободных
переменных, входящих в целевую функцию со знаком «+»
,не выходя за пределы ОДР.
2.1 Составление математической модели задачи.
1) Переменные задачи.
Обозначим: x1 - количество производимой краски для
внутренних работ;
x2 - соответствующее количество краски
для наружных работ.
2) Ограничения, которым должны удовлетворять переменные задачи:
x1 , x2  0;
по расходу продукта A: x1 + 2x2  3;
по расходу продукта B: 3x1 + x2  3;
В левых частях последних двух неравенств определены
расходы продуктов A и B, а в правых частях неравенств записаны запасы этих продуктов.
3) Целевая функция задачи.
Обозначим Z доход от продажи краски (в тысячах рублей), тогда целевая функция задачи записывается так:
Z = 2x1 + x2 ,
таким образом, задача состоит в том, чтобы найти max
Z=2x1+x2 , при ограничениях:
x1 + 2x2  3 (A)
3x1 + x2  3 (B)
x1 , x2  0 .
Так как переменные задачи x1 и x2 входят в целевую
функцию и ограничения задачи линейно, то соответствующая
задача оптимизации называется задачей линейного программирования (ЛП).
Приведение задачи к стандартному виду.
Вводя вспомогательные (балансовые) переменные x3 и
x4 в левые части неравенств (А) и (В), запишем ограничения в
виде уравнений:
x1 + 2x2 + x3 = 3 (A)
3x1 + x2 + x4 = 3 (B)
Целевая функция Z = 2x1 + x2 при приведении задачи к
стандартному виду записывается так:
65
Z - 2x1 - x2 = 0 (С)
2) Составление первой симплекс-таблицы.
Симплекс-таблица составляется из коэффициентов при
x1, x2, x3, x4 и чисел, стоящих в правых частях уравненийограничений задачи: в первой строке записываются элементы
уравнения (А), во второй - (В). В последней строке симплекстаблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи
плюс один столбец правых частей (b):
X1
1
3
-2
X2
2
1
-1
X3
1
0
0
X4
0
1
0
b
3
3
0
Переменные, для которых столбцы коэффициентов состоят из одной единицы и нулей, называются базисными (В
приведенном примере x3 и x4 - базисные переменные). Число
базисных переменных равно числу ограничений задачи и не
меняется при симплекс-преобразовании. Остальные переменные называются свободными (x1 и x2).
Симплекс-таблица определяет частное решение системы уравнений-ограничений :
x1 +2x2 + x3 = 3 (A)
3x1 +x2 + x4 = 3 (A)
при котором свободные переменные равны нулю (x1=0,
x2=0), а базисные переменные равны правым частям соответствующих строк (x3=3, x4=3).
Значение целевой функции Z всегда равно числу, стоящему в правом нижнем углу таблицы (Z=2*0+1*0=0). Первая
симплекс-таблица соответствует начальному решению задачи ЛП (х1=0, х2=0, x3=3, x4=3, Z=0). Это решение соответствует вершине А многоугольника допустимых решений
ABCD на рис.3.
4.Симплекс-метод состоит в последовательном перемещении по вершинам многоугольника допустимых решений. Каждой вершине соответствует своя симплекс-таблица,
которая получается из предыдущей при помощи симплекспреобразования.
В качестве разрешающего столбца берут столбец, у которого коэффициент в строке целевой функции является отрицательным и наибольшим по модулю. Если в данной симплекс-таблице строка целевой функции не содержат отрицательных коэффициентов, то решение задачи ЛП закончено и
симплекс-таблица определяет решение задачи, при котором
целевая функция Z принимает максимальное значение.
Разрешающая строка определяется по отношениям коэффициентов столбца b к соответствующим коэффициентам
разрешающего столбца. Разрешающей будет строка, для которой это отношение минимально. При, этом для нулевых и
отрицательных коэффициентов разрешающего столбца отношения не вычисляются.
Для первой симплекс-таблицы разрешающим столбцом
является первый столбец (свободная переменная x1 будет
преобразована в базисную). Среди отношений коэффициентов столбца b к коэффициентам разрешающего столбца: 3/1 и
3/3 минимальным будет отношение 3/3: разрешающей строкой будет вторая строка (базисная переменная x4 будет преобразована в свободную).
67
X1
1
3
-2
X2
2
1
-1
X3
1
0
0
X4
0
1
0
b
3
3
0
На пересечении разрешающего столбца и разрешающей
строки находится разрешающий элемент.
Задача симплекс преобразования состоит в том, чтобы
на месте разрешающего элемента получить единицу, а все
остальные элементы разрешающего столбца сделать нулевыми.
При этом допускается выполнение только двух операций со строками симплекс таблицы:
а) разрешающую строку можно делить (умножать) на
любое число;
б) из любой строки можно вычитать элементы разрешающей строки или к любой строке можно прибавлять элементы разрешающей строки.
Выполним преобразование первой симплекс-таблицы.
1) Делим элементы разрешающей строки на 3:
X1
1
1
-2
X2
2
1/3
-1
X3
1
0
0
X4
0
1/3
0
b
3
1
0
2) Из элементов первый строки вычитаем элементы
второй (разрешающей) строки:
X1
0
1
-2
X2
5/3
1/3
-1
X3
1
0
0
X4
-1/3
1/3
0
b
2
1
0
3. К элементам третьей строки прибавляем элементы
разрешающей строки, предварительно умножив их на два:
X1
0
1
0
X2
5/3
1/3
-1/3
X3
1
0
0
X4
-1/3
1/3
2/3
b
2
1
2
Преобразование закончено. Полученной симплекстаблице соответствует следующее решение:
базисные переменные: x1=1, x3=2
свободные переменные: x2=0, x4=0.
Точка с координатами x1=1, x2=0 – это вершина D (см.
рис.3). Значение целевой функции Z(D)=2.
Так как в строке коэффициентов целевой функции есть
отрицательный коэффициент (-1/3 во втором столбце), то
преобразование продолжается. Второй столбец является разрешающим (свободная переменная x2 переводится в базис2
6
1

3
ную), минимальным среди отношений: 5 / 3 5 и 1 / 3
является первое число, следовательно разрешающей строкой
является первая строка (базисная переменная x3 переводится
в свободную).
69
X1
0
1
0
X2
5/3
1/3
-1/3
X3
1
0
0
X4
-1/3
1/3
2/3
b
2
1
2
Выполнив симплекс-преобразование, получим:
X1
0
1
0
X2
1
0
0
X3
3/5
0
1/5
X4
-1/5
1/3
3/5
b
6/5
3/5
12/5
Так как в строке коэффициентов целевой функции нет
отрицательных, решение задачи закончено.
Оптимальное решение таково:
базисные переменные: x1*=3/5=0.6; x2*=6/5=1.2;
свободные переменные: x3*=0; x4*=0.
Точка с координатами x1*=0.6 и x2*=1.2 это вершина С
(см. рис.3)
Максимальное значение дохода (целевой функции):
Z*(С) = 12/5 = 2.4
2.2 Пример решения задач симплекс – методом с
уточнением базиса
2.2.1
Симплекс-метод, решение задачи с начальным базисом
1) Симплекс-метод для задачи с начальным базисом
(все знаки неравенств-ограничений " ≤ ").
Запишем задачу в канонической форме, т.е. ограничениянеравенства перепишем в виде равенств, добавляя балансовые переменные:
Эта система является системой с базисом (базис s1, s2, s3,
каждая из них входит только в одно уравнение системы с
коэффициентом 1), x1 и x2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод,
должны обладать следующими двумя свойствами:
-система ограничений должна быть системой уравнений с
базисом;
-свободные члены всех уравнений в системе должны быть
неотрицательны.
Полученная система - система с базисом и ее свободные
члены неотрицательны, поэтому можно применить сим71
плекс-метод. Составим первую симплекс-таблицу (Итерация 0), т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь
"БП" означает столбец базисных переменных, «Решение» столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные
коэффициенты.
итерация 0
БП x1 x2 s1 s2 s3 Решение Отношение
z
-4 -6 0 0 0 0
-
s1 2 1 1 0 0 64
64/1=64
s2 1 3 0 1 0 72
72/3=24
s3 0 1 0 0 1 20
20/1=20
Для улучшения решения перейдем к следующей итерации ,
получим следующую симплекс-таблицу. Для этого надо
выбрать разрешающий столбец, т.е. переменную, которая
войдет в базис на следующей итерации. Он выбирается по
наибольшему по модулю отрицательному коэффициенту в
z-строке (в задаче на максимум) – в начальной итерации
это столбец x2 (коэффициент -6).
Затем выбирается разрешающая строка, т.е. переменная,
которая выйдет из базиса на следующей итерации . Она
выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной
итерации это строка s3 (коэффициент 20).
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей
итерации переменная x2 заменит в базисе s3. Заметим, что в
z-строке отношение не ищется, там ставится прочерк " - ".
В случае если есть одинаковые минимальные отношения,
то выбирается любое из них. Если в разрешающем столбце
все коэффициенты меньше или равны 0, то решение задачи
бесконечно.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х2 в единичный (с единицей вместо разрешающего элемента и нулями
вместо остальных элементов).
1) Вычисление строки х2 таблицы "Итерация 1". Сначала
делим все члены разрешающей строки s3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x2 в таблице «Итерации
1». Т.к. разрешающий элемент в данном случае равен 1, то
строка s3 таблицы "Итерация 0" будет совпадать со строкой
х2 таблицы "Итерация 1". Строку x2таблицы "Итерации 1"
мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы
"Итерация 0" следующим образом:
2) Вычисление z-строки таблицы "Итерация 1". На месте 6 в первой строке (z-строке) в столбце х2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация
1". Для этого все элементы строки х2 таблицы "Итерация 1"
0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим
73
эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце
x2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х2 выделены красным цветом.
3) Вычисление строки s1 таблицы "Итерация 1". На месте 1 в s1 строке таблицы "Итерация 0" должен быть 0 в
таблице "Итерация 1". Для этого все элементы строки
х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1
44. В столбце х2 получен необходимый 0.
4) Вычисление строки s2 таблицы "Итерация 1". На месте 3 в s2 строке таблицы "Итерация 0" должен быть 0 в
таблице "Итерация 1". Для этого все элементы строки
х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3
12. В столбце х2 получен нужный 0. Столбец х2 в таблице
"Итерация 1" стал единичным, он содержит одну 1 и
остальные 0.
Строки таблицы «Итерация 1» получаем по следующему
правилу:
Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).
Например для z-строки имеем:
Старая z-строка (-4 -6 0 0 0 0)-(-6)*Новая
разрешающая
строка (0 -6 0 0 -6 -120)
= Новая z-строка (-4 0 0 0 6 120).
Для следующих таблиц пересчет элементов таблицы
делается аналогично, поэтому мы его опускаем.
итерация 1
БП x1 x2 s1 s2 s3 Решение Отношение
z
-4 0 0 0 6 120
-
s1 2 0 1 0
44
1
44/2=22
s2 1 0 0 1
12
3
12/1=12
x2 0 1 0 0 1 20
-
Разрешающий столбец х1, разрешающая строка s2,
s2 выходит из базиса, х1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.
75
итерация 2
БП x1 x2 s1 s2 s3 Решение Отношение
z
0 0 0 4
s1 0 0 1
168
6
5 20
2
x1 1 0 0 1
12
3
x2 0 1 0 0 1 20
20/5=4
20/1=20
Разрешающий столбец s3, разрешающая строка s1,
s1 выходит из базиса, s3 входит в базис.
итерация 3
БП x1 x2 s1 s2 s3 Решение Отношение
z
0 0 6/5 8/5 0 192
-
s3 0 0 1/5
1 4
2/5
-
x1 1 0 3/5
0 24
1/5
-
2/5 0 16
1/5
-
x2 0 1
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x2 = 16,
zmax = 192.
2.2.2
Симплекс-метод, решение задачи с искусственным
базисом
Решим задачу с искусственным базисом (хотя бы один
знак неравенств-ограничений " ≥ " или " = ").
Запишем задачу в канонической форме (в виде системы
уравнений, что требует симплекс-метод), для этого введем
две переменные х3≥ 0 и х4 ≥ 0 получим:
Система ограничений предлагает только одну допустимую
базисную переменную x4, только она входит только в одно
уравнение в третье с коэффициентом 1, поэтому в первое и
второе уравнения добавляем искусственные переменные
R1 ≥ 0 и R2 ≥ 0 Чтобы можно было примененить симплексметод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть
переменная с коэффициентом 1, которая входит только в
77
одно уравнение системы, в нашем случае это R1, R2 и x4.
Получили, так называемую, М-задачу:
Данная система является системой с базисом, в которой R1,
R2 и x4 базисные переменные, а x1, x2 и x3 свободные переменные, свободние члены всех уравнений неотрицательны.
Следовательно, для решения задачи можно применить
симплекс-метод. Запишем начальную симплекс-таблицу:
итерация 0
БП
x1 x2 x3 R1 R2 x4 Решение Отношение
z
-4
R1
3 4 -1 1 0 0 6
6/4=3/2
R2
1 3 0 0 1 0 3
3/3=1
x4
2 1 0 0 0 1 4
4/1=4
0 0 0 0 0
16
Оценка -4 -7 1 -1 -1 0 -
-
-
В таблицу для задач с искусственным базисом добавлена
строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными пере-
менными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по
модулю отрицательному коэффициенту строки "Оценка"
определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет
искусственных переменных) разрешающий столбец будет
определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2, он выбран по наибольшей по модулю отрицательной оценке (7). Разрешающая строка R2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче
без искусственных переменных. Это значит, что на следующей итерации переменная х2 из свободной перейдет в базисную, а переменная R2 из базисной – в свободную. Запишем следующую симплекс-таблицу:
79
итерация 1
БП
x1 x2 x3 R1 R2
x4 Решение Отношение
z
4/3 0 0 0 16/30 0 16
-
R1
5/3 0 -1 1 -4/3
0 2
6/5
x2
1/3 1 0 0 1/3
0 1
3
x4
5/3 0 0 0 -1/3
1 3
9/5
Оценка
0 1 -1 4/3
5/3
0 -
-
Разрешающий столбец х1, разрешающая строка R1,
R1 выходит из базиса, x1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому
строки «Оценка» в следующей таблице нет:
итерация 2
БП x1 x2 x3 R1 R2
z
0 0 4/5
x4 Решение Отношение
32/5 0 72/5
4/5
-
3/5 -4/5 0 6/5
3/5
-
x2 0 1 1/5
3/5 0 3/5
1/5
-
x4 0 0 1
-1 1
-
x1 1 0
1 1
Далее разрешающий столбец выбирается по z-строке. В zстроке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R1, который не влияет на оптимальность, когда искусственные переменные
вышли из базиса. Следовательно, получено оптимальное
решение x1 = 6/5; x2 = 3/5; zmax = 72/5.
2.3 Особые случаи применения симплекс-метода
1) Когда прямая (если рассматривается двухмерная задача
линейного программирования, а в общем случае гиперплоскость), представляющая целевую функцию параллельна прямой (гиперплоскости), соответствующей одному из
неравенств-ограничений (которое в точке оптимума выполняется, как точное равенство) целевая функция принимает одно и тоже оптимальное значение на некотором
множестве точек границы области допустимых решений.
Эти решения называются альтернативными оптимальными решениями. Наличие альтернативных решений
можно определить по оптимальной симплекс-таблице. Если в z-строке оптимальной таблицы есть нулевые коэффициенты небазисных переменных, то есть альтернативные
решения.
2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать
разрешающую строку, в этом случае решение неограничено.
3) Если ограничения задачи линейного программирования
несовместны (т.е. они не могут выполняться одновремен81
но), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение.
Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных
(Ri). Если они там есть, то задача не имеет решений.
3. Определение двойственной задачи
Каждой задаче линейного программирования можно
определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой
задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
(32)
при условиях
(33)
(34)
Определение 1. Задача, состоящая в нахождении
минимального значения функции
(35)
при условиях
83
(36)
(37)
называется двойственной по отношению к задаче (32) –
(34). Задачи (32) – (34) и (35) – (37) образуют пару задач,
называемую в линейном программировании двойственной
парой. Сравнивая две сформулированные задачи, видим, что
двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) –
на минимум.
2. Матрица
(38)
составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица
(39)
в двойственной задаче (35) – (37) получаются друг из
друга транспонированием (т. е. заменой строк столбцами, а
столбцов – строками).
3. Число переменных в двойственной задаче (35) – (37)
равно числу ограничений в системе (33) исходной задачи (32)
– (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные
члены в системе (33) исходной задачи (32) – (34), а правыми
частями в соотношениях системы (36) двойственной задачи –
коэффициенты при неизвестных в целевой функции (32) исходной задачи.
5. Если переменная xj исходной задачи (32) – (34) может
принимать только лишь положительные значения, то j–е
условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “? ”. Если же переменная xj может
принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой
уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными
двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i–я переменная двойственной задачи
. В противном случае
переменная уj может принимать как положительные, так и
отрицательные значения.
Двойственные пары задач обычно подразделяют на
симметричные и несимметричные. В симметричной паре
двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами
вида “ ”. Таким образом, переменные обеих задач могут
принимать только лишь неотрицательные значения.
Пример 1. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции
85
(40)
при условиях
(41)
(42)
Решение. Для данной задачи
и
Число переменных в двойственной задаче равно числу
уравнений в системе (41), т. е. равно трем. Коэффициентами в
целевой функции двойственной задачи являются свободные
члены системы уравнений (41), т.е. числа 12, 24, 18.
Целевая функция исходной задачи (40) – (42) исследуется на максимум, а система условий (41) содержит только
уравнения. Поэтому в двойственной задаче целевая функция
исследуется на минимум, а ее переменные могут принимать
любые значения (в том числе и отрицательные). Так как все
три переменные исходной задачи (40) – (42) принимают
только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида
“? ”. Следовательно, для задачи (40) – (42) двойственная задача
такова:
найти
минимум
функции
при условиях
Пример 2. Для задачи, состоящей в максимизации
функции
при условиях
сформулировать двойственную задачу.
Решение. Для данной задачи
,
В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим
образом:
найти
минимум
функции
при условиях
3.1 Связь между решениями прямой и двойственной задач
Рассмотрим пару двойственных задач, образованную
основной задачей линейного программирования и двойственной к ней. Исходная задача: найти максимум функции
(43)
при условиях
87
(44)
(45)
Двойственная задача: найти минимум функции
(46)
при условиях
(47)
Каждая из задач двойственной пары (43) – (45) и (46),
(47) фактически является самостоятельной задачей линейного
программирования и может быть решена независимо одна от
другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.
Существующие зависимости между решениями прямой
и двойственной задач характеризуются сформулированными
ниже леммами и теоремами двойственности.
Лемма 1. Если Х – некоторый план исходной задачи
(43) – (45), a Y – произвольный план двойственной задачи
(46), (47), то значение целевой функции исходной задачи при
плане Х всегда не превосходит значения целевой функции
двойственной задачи при плане Y, т. е.
Лемма 2. Если
для некоторых планов X* и
Y задач (43) – (45) и (46), (47), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.
Теорема 8 (первая теорема двойственности). Если одна
из задач двойственной пары (43) – (45) или (46), (47) имеет
оптимальный план, то и другая имеет оптимальный план и
*
значения целевых функций задач при их оптимальных планах
равны между собой, т. е.
Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (43) – (45) – сверху,
для двойственной (46), (47) – снизу), то другая задача вообще
не имеет планов.
Теорема 9 (вторая теорема двойственности). План
задачи
(43)
–
(45)
и
план
задачи (46), (47) являются оптимальными
планами этих задач тогда и только тогда, когда для любого
выполняется равенство
3.2 Геометрическая интерпретация двойственных
задач
Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя
геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач.
При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы;
2) планы имеет только одна задача; 3) для каждой задачи
двойственной пары множество планов пусто.
Пример 3. Для задачи, состоящей в определении максимального значения функции
при условиях
89
составить двойственную задачу и найти решение обеих
задач.
Решение. Двойственной задачей по отношению к исходной является задача, состоящая в определении минимального значения функции
при условиях
Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно
найти, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8).
Как видно из рис. 8, максимальное значение целевая
функция исходной задачи принимает в точке В. Следовательно, Х*=(2, 6) является оптимальным планом, при котором
. Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y*=(1;
4) является оптимальным планом двойственной задачи, при
котором
Таким образом, значения целевых функций
исходной и двойственной задач при их оптимальных планах
равны между собой.
Из рис. 7 видно, что при всяком плане исходной задачи
значение целевой функции не больше 46. Одновременно, как
видно из рис. 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при
любом плане исходной задачи значение целевой функции не
превосходит значения целевой функции двойственной задачи
при ее произвольном плане.
Пример 4.
Найти решение двойственной пары задач.
Исходная задача;
Двойственная задача:
91
Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим,
используя геометрическую интерпретацию задачи линейного
программирования (рис. 7 и 8). Из рис. 7 видно, что исходная
задача не имеет оптимального плана из-за неограниченности
снизу ее целевой функции на множестве допустимых решений.
Из рис. 10 следует, что двойственная задача не имеет
планов, поскольку многоугольник решений ее пуст. Это
означает, что если исходная задача двойственной пары не
имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов.
Нахождение решения двойственных задач. Рассмотрим
пару двойственных задач – основную задачу линейного программирования (43) – (45) и двойственную к ней задачу (46),
(47).
Предположим, что с помощью симплексного метода
найден оптимальный план X* задачи (43) – (45) и этот план
определяется базисом, образованным векторами
.
Обозначим через
вектор-строку, составленную из коэффициентов при неизвестных в целевой
функции (43) задачи (43) – (45), а через
– матрицу, обратную матрице Р, составленной из компонент векторов
базиса. Тогда имеет место следующее утверждение.
Теорема 10. Если основная задача линейного программирования имеет оптимальный план X*, то
является оптимальным планом двойственной задачи.
Таким образом, если найти симплексным методом оптимальный план задачи (43) – (45), то, используя последнюю
симплекс–таблицу, можно определить и
и с помощью
соотношения
найти оптимальный план двойственной задачи (46), (47).
В том случае, когда среди векторов
, составленных из коэффициентов при неизвестных в системе уравнений (44), имеется т единичных, указанную матрицу
образуют числа первых т строк последней симплекс–
таблицы, стоящие в столбцах данных векторов. Тогда нет
необходимости определять оптимальный план двойственной
задачи умножением
на
, поскольку компоненты этого
плана совпадают с соответствующими элементами (m+1)–й
строки столбцов единичных векторов, если данный коэффициент
, и равны сумме соответствующего элемента этой
строки и если
Сказанное выше имеет место и для симметричной пары
двойственных задач. При этом так как система ограничений
исходной задачи содержит неравенства вида “ ”, то компо93
ненты оптимального плана двойственной задачи совпадают с
соответствующими числами (m+1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа
стоят в столбцах векторов, соответствующих дополнительным переменным.
Пример 15. Для задачи, состоящей в определении максимального значения функции
при условиях
составить двойственную задачу и найти ее решение.
Решение. Двойственная задача по отношению к исходной состоит в нахождении минимума функции
при условиях
Чтобы найти решение двойственной задачи, сначала
находим решение исходной задачи методом искусственного
базиса. Оно приведено в таблице 12. Из последней симплекстаблицы видно, что двойственная задача имеет решение
Оптимальные двойственные оценки удовлетворяют
всем условиям двойственной задачи. При этом минимальное
значение целевой функции двойственной задачи, равное
совпадает с максимальным
значением целевой функции
исходной задачи.
Таблица 12
Базис
i
1
2
3
4
5
1
2
3
4
1
2
3
4
p4
P5
p6
p4
P5
p1
p2
P5
p1
Сб
Р0
0
12
0
17
–М 4
0
0
–4
0
14
1
15
2
2
0
2
1
4
9
4
12
1
2
–1
0
0
–М
P1
P2
P3
p4
p5 Р6
–1
1
2
–1
–2
0
0
1
0
0
0
1
0
4
1
–1
–2
1
7/2
3/2
–1/2
–5/2
1
0
0
0
–2
2
2
1
–2
–1
1
1
2
–2/7
13/7
6/7
9/7
1
0
0
0
0
1
0
0
0
2/7
–3/7
1/7
5/7
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1/2
–1/2
1/2
1/2
1/7
–5/7
4/7
6/7
3.3 Экономическая интерпретация двойственных
задач
Экономическую интерпретацию двойственных задач и
двойственных оценок рассмотрим на примере.
Пример 6. Для производства трех видов изделий А, В и
С используется три различных вида сырья. Каждый из видов
сырья может быть использован в количестве, соответственно
не большем 180, 210 и 244 кг. Нормы затрат каждого из видов
сырья на единицу продукции данного вида и цена единицы
продукции каждого вида приведены в таблице 13.
Определить план выпуска продукции, при котором
обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продук95
ции. Оценки, приписываемые каждому из видов сырья,
должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,–
не меньше цены единицы продукции данного вида.
Таблица 13
Вид сырья
Нормы затрат сырья (кг) на единицу
продукции
А
В
С
I
II
III
4
3
1
2
1
2
1
3
5
Цена единицы
продукции
(руб.)
10
14
12
Решение. Предположим, что производится x1 изделий
А, изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в
максимизации целевой функции
(48)
при следующих условиях
(49)
(50)
Припишем каждому из видов сырья, используемых для
производства продукции, двойственную оценку, соответ-
ственно равную
и у3. Тогда общая оценка сырья, используемого на производство продукции, составит
(51)
Согласно условию, двойственные оценки должны быть
такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше
цены единицы продукции данного вида, т. е.
и у3 должны удовлетворять следующей системе неравенств:
(52)
(53)
Как видно, задачи (48) – (50) и (51) – (53) образуют
симметричную пару двойственных задач. Решение прямой
задачи дает оптимальный план производства изделий A, В и
С, а решение двойственной – оптимальную систему оценок
сырья, используемого для производства этих изделий. Чтобы
найти решение этих задач, следует сначала отыскать решение
какой–либо одной из них. Так как система ограничений задачи (48) – (50) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.
Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется
82 изделия В и 16 изделий С. При данном плане производства
остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно,
97
что оптимальным решением двойственной задачи является
Таблица 14
i
1
2
3
Базис
p2
P5
p3
Сб
14
0
12
Р0
82
80
16
1340
10
14
12
0
0
0
P1
P2
P3
p4
p5
Р6
19/8
23/8
–3/4
57/4
1
0
0
0
0
0
1
0
5/8
1/8
–1/4
23/4
0
1
0
0
–1/8
–5/8
1/4
5/4
Переменные
и
обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти
оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции.
Двойственная оценка единицы сырья II вида равна нулю.
Этот вид сырья не полностью используется при оптимальном
плане производства продукции.
Таким образом, положительную двойственную оценку
имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому
двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной
двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при
увеличении количества сырья соответствующего вида на 1 кг.
Так, увеличение количества сырья I вида на 1 кг приведет к
тому, что появится возможность найти новый оптимальный
план производства изделий, при котором общая стоимость
изготовляемой продукции возрастет на 5,75 руб. и станет
равной 1340+5,75=1345,75 руб. При этом числа, стоящие в
столбце вектора таблицы 14, показывают, что указанное
увеличение общей стоимости изготовляемой продукции мо-
жет быть достигнуто за счет увеличения выпуска изделий В
на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8
кг. Точно так же увеличение на 1 кг сырья III вида позволит
найти новый оптимальный план производства изделий, при
котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет
достигнуто в результате увеличения выпуска изделий С на
1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.
Продолжим рассмотрение оптимальных двойственных
оценок. Вычисляя минимальное значение целевой функции
двойственной задачи
видим, что оно совпадает с максимальным значением
целевой функции исходной задачи. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем
Первое ограничение двойственной задачи выполняется
как строгое неравенство. Это означает, что двойственная
оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не
предусмотрено оптимальным планом прямой задачи. Второе
и третье ограничения двойственной задачи выполняются как
99
строгие равенства. Это означает, что двойственные оценки
сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому
выпускать эти два вида продукции по двойственным оценкам
экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.
Таким образом, двойственные оценки тесным образом
связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи может оказать влияние как на ее оптимальный план, так и на систему оптимальных двойственных оценок. Поэтому, чтобы проводить экономический анализ с использованием двойственных оценок,
нужно знать их интервал устойчивости. К рассмотрению этого мы сейчас и перейдем.
Двойственный симплекс-метод, как и симплекс-метод,
используется при нахождении решения задачи линейного
программирования, записанной в форме основной задачи, для
которой среди векторов , составленных из коэффициентов
при неизвестных в системе уравнений, имеется m единичных.
Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом
эти числа предполагались неотрицательными). Такую задачу
и рассмотрим теперь, предварительно предположив, что единичными являются векторы
т. е. рассмотрим задачу, состоящую в определении максимального значения
функции
(54)
при условиях
(55)
(56)
где
и среди чисел
имеются отрицательные.
В данном случае
есть решение
системы линейных уравнений (55). Однако это решение не
является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа.
Поскольку векторы
– единичные, каждый из
векторов
можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов
по векторам
служат числа
Таким образом, можно найти
Определение 14.
Решение
системы линейных
уравнений (55), определяемое базисом
, называется псевдопланом задачи (54) – (56), если
для любого
Теорема 11.
101
Если в псевдоплане
, определяемом базисом
, есть хотя бы одно отрицательное
число
такое, что все
вообще не имеет планов.
, то задача (54) – (56)
Теорема 12.
Если в псевдоплане
, определяемом базисом
, имеются отрицательные числа
такие, что для любого из них существуют числа aij<0, то
можно перейти к новому псевдоплану, при котором значение
целевой функции задачи (54) – (56) не уменьшится.
Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.
Итак, продолжим рассмотрение задачи (54) – (56).
Пусть
– псевдоплан этой задачи. На
основе исходных данных составляют симплекс-таблицу
(табл. 15), в которой некоторые элементы столбца вектора
являются отрицательными числами. Если таких чисел нет, то
в симплекс-таблице записан оптимальный план задачи (54) –
(56), поскольку, по предположению, все
. Поэтому для
определения оптимального плана задачи при условии, что он
существует, следует произвести упорядоченный переход от
одной симплекс–таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы.
При этом все время должны оставаться неотрицательными
все элементы (т +1)–й строки, т.е.
для любого
Таким образом, после составления симплекс-таблицы
проверяют, имеются ли в столбце вектора отрицательные
числа. Если их нет, то найден оптимальный план исходной
задачи. Если же они имеются (что мы и предполагаем), то
выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут
какое–нибудь одно из них: пусть это число bl. Выбор этого
числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор Pl. Чтобы определить,
какой вектор следует ввести в базис, находим
, где
Пусть это минимальное значение принимается при
, тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице
производят по обычным правилам симплексного метода.
Итерационный процесс продолжают до тех пор, пока в
столбце вектора Р0 не будет больше отрицательных чисел.
При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы (табл. 15) в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная
задача не имеет решения.
Таким образом, отыскание решения задачи (54) – (56)
двойственным симплекс-методом включает следующие этапы:
1. Находят псевдоплан задачи.
2. Проверяют этот псевдоплан на оптимальность. Если
псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи,
либо переходят к новому псевдоплану.
103
3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного
числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.
4. Находят новый псевдоплан и повторяют все действия
начиная с этапа 2.
Таблица 15
Пример 17.
Найти максимальное значение функции
при условиях
Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум
функции
при условиях
Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции
(57)
при условиях
(58)
(59)
Составим для последней задачи двойственную задачу.
Такой является задача, в результате решения которой требуется найти минимальное значение функции
(60)
при условиях
(61)
(62)
Выбрав в качестве базиса векторы
и , составим
симплексную таблицу (табл. 16) для исходной задачи (57) –
(59).
Таблица 16
i
Базис Сб
Р0
1
1
2
0
0
105
1
2
3
4
p3
P4
p5
2
0
0
8
–4
–6
16
P1
P2
P3
p4
p5
1
–1
–1
1
1
1
–2
1
1
0
0
0
0
1
0
0
0
0
1
0
Из этой таблицы видим, что планом двойственной задачи (57) – (59) является
. При этом плане
Так
как в столбце вектора Р0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет,
то в соответствии с алгоритмом двойственного симплекс–
метода переходим к новой симплекс–таблице. (В данном
случае это можно сделать, так как в строках векторов Р4 и Р5
имеются отрицательные числа. Если бы они отсутствовали,
то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р0. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р5. Чтобы определить, какой вектор необходимо
ввести в базис, находим
где
Имеем
Значит, в базис вводим вектор P2. Переходим к новой
симплекс–таблице (табл. 17).
Таблица 17
i
Базис Сб
Р0
1
1
2
0
0
P1
P2
P3
p4
p5
1
2
3
4
p3
P4
p2
2
0
1
5
–7
3
13
1/2
–3/2
1/2
1/2
0
0
1
0
1
0
0
0
0
1
0
0
1/2
1/2
–1/2
1/2
Из этой таблицы видно, что получен новый план двойственной задачи
При этом плане значение ее линейной формы равно
Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к
другому.
Так как в столбце вектора Р0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди
этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима.
В данном случае переходим к новой симплекс-таблице (табл.
18).
Таблица 18
i
1
2
3
4
Базис Сб
p3
P1
p2
2
1
1
Р0
8/3
14/3
2/3
32/3
1
1
2
0
0
P1
P2
P3
p4
p5
0
1
0
0
0
0
1
0
1
0
0
0
1/3 2/3
–
–1/3
2/3 –1/3
1/3 2/3
1/3
Как видно из таблицы 18, найдены оптимальные планы
исходной и двойственной задач. Ими являются
107
и
. При этих планах значения линейных форм исходной и двойственной задач равны между
собой:
Пример 18.
Найти
максимальное
при условиях
значение
функции
Решение. Умножая первое и третье уравнения системы
ограничений задачи на –1, в результате приходим к задаче
нахождения
максимального
значения
функции
при условиях
Взяв в качестве базиса векторы Р3, Р4 и Р5, составляем
симплекс-таблицу (табл. 19).
Таблица 19
i
1
2
3
4
Базис Сб
p3
P4
p5
0
5
0
Р0
–12
10
–18
50
2
3
0
5
0
P1
P2
P3
p4
p5
2
1
–3
3
–1
2
2
7
1
0
0
0
0
1
0
0
0
0
1
0
В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный
план. Поскольку в указанном столбце отрицательные числа
имеются и такие же числа содержатся в соответствующих
строках, переходим к новой симплекс–таблице (таблица 20).
Для этого исключим из базиса вектор Р5 и введем в базис
вектор Р1. В результате получим псевдоплан X=(6;0;-24;4)
Таблица 20
i
1
2
3
4
Базис Сб
p3
P4
p1
0
5
2
Р0
–24
4
6
32
2
3
0
5
0
P1
P2
P3
p4
p5
0
0
1
0
1/3 1
0
2/3
8/3 0
1
1/3
–
0
0
–1/3
2/3 0
0
1
9
Так как в строке вектора Р3 нет отрицательных чисел,
то исходная задача не имеет решения.
109
4. Транспортная задача
Задача о размещении (транспортная задача) – это РЗ,
в которой работы и ресурсы измеряются в одних и тех же
единицах. В таких задачах ресурсы могут быть разделены
между работами, и отдельные работы могут быть выполнены
с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение
(транспортировка) продукции, находящейся на складах, по
предприятиям-потребителям.
Стандартная ТЗ определяется как задача разработки
наиболее экономичного плана перевозки продукции одного
вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с
помощью тарифов на перевозку единицы продукции.
Исходные параметры модели ТЗ
1) n – количество пунктов отправления, m – количество пунктов назначения.
2)
– запас продукции в пункте отправления
) [ед. прод.].
(
3)
– спрос на продукцию в пункте назначения
) [ед. прод.].
(
4)
– тариф (стоимость) перевозки единицы про-
дукции из пункта отправления
в пункт назначения
[руб./ед. прод.].
Искомые параметры модели ТЗ
1)
– количество продукции, перевозимой из
пункта отправления
в пункт назначения
[ед. прод.].
2)
– транспортные расходы на перевозку всей
продукции [руб.].
Этапы построения модели
Определение переменных.
Проверка сбалансированности задачи.
Построение сбалансированной транспортной матрицы.
Задание ЦФ.
V.Задание ограничений.
Транспортная модель
;
(
1)
ЦФ представляет собой общие транспортные расходы
на осуществление всех перевозок в целом. Первая группа
ограничений указывает, что запас продукции в любом пункте
отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений
указывает, что суммарные перевозки продукции в некоторый
пункт потребления должны полностью удовлетворить спрос
111
на продукцию в этом пункте. Наглядной формой представления модели ТЗ является транспортная матрица (табл.1).
Таблица 1
Общий вид транспортной матрицы
Пункты
отправления, Пункты потребления,
,
[руб./ед. прод.]
…
…
…
Запасы,
ед. прод.
…
…
…
… …
…
…
Потребность
ед. прод.
…
Из модели (4.1) следует, что сумма запасов продукции
во всех пунктах отправления должна равняться суммарной
потребности во всех пунктах потребления, т.е.
(
2)
.
Если (4.2) выполняется, то ТЗ называется сбалансированной (закрытой), в противном случае – несбалансированной (открытой). В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный
фиктивный (реально не существующий) пункт потребления,
который будет формально потреблять существующий излишек запасов, т.е.
.
Если суммарные потребности превышают суммарные
запасы, то необходим дополнительный фиктивный пункт
отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:
.
Для фиктивных перевозок вводятся фиктивные тарифы
, величина которых обычно приравнивается к нулю
. Но в некоторых ситуациях величину фиктивного тарифа можно интерпретировать как штраф, которым облагается каждая единица недопоставленной продукции. В этом
случае величина
может быть любым положительным
числом.
Задача о назначениях – частный случай ТЗ. В задаче о
назначениях количество пунктов отправления равно количеству пунктов назначения. Объемы потребности и предложения в каждом из пунктов назначения и отправления равны 1.
Примером типичной задачи о назначениях является распределение работников по различным видам работ, минимизирующее суммарное время выполнения работ.
Переменные задачи о назначениях определяются следующим образом
113
4.1 Стандартная транспортная задача
Задача
Заводы некоторой автомобильной фирмы расположены
в городах А, В и С. Основные центры распределения продукции сосредоточены в городах D и E. Объемы производства
указанных трех заводов равняются 1000, 1300 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимости перевозки автомобилей по железной дороге по каждому из возможных маршрутов приведены
в табл.2.
Таблица 2
Стоимость перевозки автомобилей, руб./шт.
D
E
А
80
215
В
100
108
С
102
68
Постройте математическую модель, позволяющую
определить количество автомобилей, перевозимых из каждого завода в каждый центр распределения, таким образом,
чтобы общие транспортные расходы были минимальны.
Решение
Определение переменных
Обозначим количество автомобилей, перевозимых из iго завода в j-й пункт потребления через
.
Проверка сбалансированности задачи
Проверим равенство суммарного производства автомобилей и суммарного спроса
откуда следует вывод – задача несбалансирована, поскольку спрос на автомобили превышает объем их производства. Для установления баланса введем дополнительный фиктивный завод с ежеквартальным объемом производства
200 шт. (
). Фиктивные тарифы
приравняем к нулю (т.к. перевозки в действительности производиться не будут).
Построение транспортной матрицы
Согласно результатам проверки сбалансированности
задачи в транспортной матрице должно быть четыре строки,
соответствующих заводам и два столбца, соответствующих
центрам распределения (см. табл.3). Тариф перевозки обычно
вписывают в правом нижнем углу клетки матрицы для
удобства дальнейшего нахождения опорных планов задачи.
Таблица 3
Транспортная матрица задачи
Объем произв.,
D
E
шт./квартал
А
B
C
Фиктивный завод
Спрос,
шт./квартал
2300
80
215
100
108
102
68
0
0
1400
1000
1300
1200
200
3700
115
Задание ЦФ
Суммарные затраты в рублях на ежеквартальную перевозку автомобилей определяются по формуле
Задание ограничений
[шт./квартал]
4.2 Модификации стандартной транспортной задачи
Недопустимые перевозки
Иногда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов
.
Запрещающие тарифы должны сделать невыгодными перевозки в соответствующих направлениях. Для этого величина
запрещающих тарифов должна быть больше реальных тарифов в транспортной матрице
.
Максимизация ЦФ
Существующий алгоритм решения транспортных задач
(метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках
транспортной модели требуется максимизировать ЦФ,
например, общий доход, объем продаж, прибыль, качество
выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ
вводится ЦФ
, в которой
тарифы умножаются на (-1). Таким образом, максимизация
будет соответствовать минимизации
.
4.3 Многопродуктовые модели
Если в задаче идет речь о том, что из каждого пункта
отправления можно перевозить продукцию нескольких видов, то при построении модели можно использовать один из
следующих вариантов:
каждому виду продукции должна соответствовать одна
транспортная матрица;
все виды продукции представлены в одной общей матрице с использованием запрещающих тарифов в клетках, связывающих разные виды продукции
Общая постановка транспортной задачи состоит в
определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления
в п
пунктов назначения
. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его
доставки. Рассмотрим транспортную задачу, в качестве кри117
терия оптимальности которой взята минимальная стоимость
перевозок всего груза. Обозначим через тарифы перевозки
единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через
– потребности в грузе в j–м пункте назначения, а через –
количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции
(63)
при условиях
(64)
(65)
(66)
Поскольку переменные
удовлетворяют системам уравнений (64) и (65) и условию неотрицательности (66), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 15.
Всякое неотрицательное решение систем линейных
уравнений
(64)
и
(65),
определяемое
матрицей
, называется планом транспортной задачи.
Определение 16.
План
, при котором функция (63)
принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные транспортной задачи записывают в виде таблицы 21.
Таблица 21
Очевидно, общее наличие груза у поставщиков равно
, а общая потребность в грузе в пунктах назначения равна
единиц. Если общая потребность в грузе в пунктах
назначения равна запасу груза в пунктах отправления, т. е.
(67)
119
то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.
Теорема 13.
Для разрешимости транспортной задачи необходимо и
достаточно, чтобы запасы груза в пунктах отправления были
равны потребностям в грузе в пунктах назначения, т. е. чтобы
выполнялось равенство (67).
В случае превышения запаса над потребностью, т. е.
вводится фиктивный (n+1)–й пункт назначения с
потребностью
и соответствующие тарифы
считаются равными нулю:
Полученная задача
является транспортной задачей, для которой выполняется равенство (67).
Аналогично, при
(m+1)–й
пункт
отправления
вводится фиктивный
с
запасом
груза
и тарифы полагаются равными нулю:
Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же
модель конкретной задачи является открытой, то, исходя из
сказанного выше, перепишем таблицу условий задачи так,
чтобы выполнялось равенство (67).
Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число
уравнений в системах (64) и (65) равно п+т. Так как мы предполагаем, что выполняется условие (67), то число линейно
независимых уравнений равно п+т–1. Следовательно, опорный план транспортной задачи может иметь не более п + т–1
отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности п+т–1, то план является невырожденным, а если меньше – то вырожденным.
Как и для всякой задачи линейного программирования,
оптимальный план транспортной задачи является и опорным
планом.
Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.
Пример 19.
Четыре предприятия данного экономического района
для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно
равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140,
170 ед. На каждое из предприятий сырье может завозиться из
любого пункта его получения. Тарифы перевозок являются
известными величинами и задаются матрицей
Составить такой план перевозок, при котором общая
стоимость перевозок является минимальной.
121
Решение. Обозначим через
количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и
имеющегося сырья обеспечиваются за счет выполнения следующих равенств:
(68)
При данном плане
щая стоимость перевозок составит
перевозок об-
(69)
Таким образом, математическая постановка данной
транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (68), при котором целевая функция (69) принимает минимальное значение.
5. Целочисленные задачи линейного программирования. Метод Гомори
Экономическая и геометрическая интерпретация задачи
целочисленного программирования. Экстремальная задача,
переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
В математической модели задачи целочисленного программирования как целевая функция, так и функции в системе ограничений могут быть линейными, нелинейными и
смешанными. Ограничимся случаем, когда целевая функция
и система ограничений задачи являются линейными.
Пример 20.
В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено
площади. На приобретение оборудования предприятие
может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., а II вида – 3000 руб. Приобретение одного
комплекта оборудования I вида позволяет увеличить выпуск
продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Зная что для установки одного комплекта оборудования I вида требуется 2 м2 площади, а оборудования II вида – 1 м2 площади определить такой набор дополнительного оборудования, которых дает возможность максимально увеличить выпуск продукции
Решение. Составим математическую модель задачи.
Предположим, что предприятие приобретет x1 комплектов
123
оборудования I вида и
Тогда переменные x1 и
неравенствам:
комплектов оборудования II вида.
должны удовлетворять следующим
(70)
Если предприятие приобретет указанное количество
оборудования, то общее увеличение выпуска продукции составит
(71)
По своему экономическому содержанию переменные x1
и могу принимать лишь целые неотрицательные значения,
т. е.
(72)
x1, – целые. (73)
Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (71) при вы полнении условий (70), (72) и (73). Так как
неизвестные могут принимать только целые значения, то задача (70) – (73) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум,
решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого прежде всего построим
многоугольник решений задачи, состоящей в определении
максимального значения линейной функции (71) при выполнении условий (70) и (72) (рис. 11). Координаты всех точек
построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (70) и условию неотрицательности переменных (72). Вместе с тем условию (73), т. е.
условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы
найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоуголь-
ником OKEMNF, содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой
из вершин являются целыми числами. Значит, если найти
точку максимума функции (71) на многоугольнике OKEMNF,
то координаты этой точки и определят оптимальный план задачи.
125
Для
этого построим вектор
и прямую
проходящую через многоугольник решений
OKEMNF (число 12 взято произвольно). Построенную прямую передвигаем в направлении вектора до тех пор, пока
она не пройдет через последнюю общую точку ее с данным
многоугольником. Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является
максимальным.
В данном случае искомой является точка E(1; 3), в
которой целевая функция принимает максимальное значение
Следовательно, координаты точки Е определяют оптимальный план задачи (70) – (73). В соответствии
с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования
II вида. Это обеспечит предприятию при имеющихся у него
ограничениях на производственные площади и денежные
средства максимальное увеличение выпуск продукции,
равное 14 ед. в смену.
Пример 21.
Для выполнения работ могут быть использованы п механизмов. Производительность i–го механизма
при
выполнении j–й работы
равна . Предполагая, что
каждый механизм может быть использован только на одной
работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами,
обеспечивающее максимальную производительность. Построить математическую модель задачи.
Решение. Введем переменную xij, значение которой
равно 1, если при выполнении i–й работы используется j–й
механизм, и равно 0 в противном случае. Тогда условия ис-
пользования каждого механизма только на одной работе выражаются равенствами
(74)
а условия выполнения работы только одним механизмом – равенствами
(75)
(76)
Таким образом, задача состоит в определении таких
значений неизвестных
, удовлетворяющих
системам уравнений (74) и (75) и условию (76), при которых
достигается максимальное значение функции
(77)
Сформулированная задача является задачей целочисленного программирования.
5.1 Определение оптимального плана задачи целочисленного программирования.
Рассмотрим задачи целочисленного программирования,
в которых как целевая функция, так и функции в системе
ограничений являются линейными. В связи с этим сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения.
127
В общем виде эту задачу можно записать так: найти максимум функции
(78)
при условиях
(79)
(80)
– целые
(81)
Если найти решение задачи (78) – (81) симплексным
методом, то оно может оказаться как целочисленным, так и
нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (78) – (81) требуются специальные
методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит описанный выше симплексный метод.
5.2 Метод Гомори
Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без
учета целочисленности переменных. После того как этот
план найден, просматривают его компоненты. Если среди
компонент нет дробных чисел, то найденный план является
оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) –
(80) переменная принимает дробное значение, то к системе
уравнений (79) добавляют неравенство
(82)
и находят решение задачи (78) – (80), (82).
В неравенстве (82)
величины
и
и
– преобразованные исходные
значения которых взяты из последней сим-
плекс–таблицы, а
и
– дробные части чисел (под
дробной частью некоторого числа а понимается наименьшее
неотрицательное число b такое, что разность между а и b есть
целое). Если в оптимальном плане задачи (78) – (80) дробные
значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной
частью.
Если в найденном плане задачи (78) – (80), (82) переменные принимают дробные значения, то снова добавляют
одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают
оптимальный план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.
Если требование целочисленности (81) относится лишь
к некоторым переменным, то такие задачи называются частично целочисленными. Их решение также находят последовательным решением задач, каждая из которых получается из
предыдущей с помощью введения дополнительного ограничения. В этом случае такое ограничение имеет вид
(83)
где
1) для
значения,
определяются из следующих соотношений:
, которые могут принимать нецелочисленные
129
(84)
2) для , которые могут принимать только целочисленные значения,
(85)
Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные
этапы:
1. Используя симплексный метод, находят решение задачи (78) – (80) без учета требования целочисленности переменных.
2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане
задачи (78) – (81) должна быть целочисленной.
3. Используя двойственный симплекс–метод, находят
решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.
4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный
процесс до получения оптимального плана задачи (78) – (81)
или установления ее неразрешимости.
Пример 22.
Методом Гомори найти максимальное значение функции
(86)
при условии
(87)
(88)
– целые
(89)
Дать геометрическую интерпретацию решения задачи.
Решение. Для определения оптимального плана задачи
(86) – (89) сначала находим оптимальный план задачи (86) –
(88) (табл. 22).
Таблица 22
i
1
2
3
4
1
2
3
4
1
2
3
4
Базис Сб
p3
P4
p5
p3
P1
p5
p2
P1
p5
0
0
0
0
3
0
2
3
0
Р0
13
6
9
0
7
6
27
18
7/2
19/2
34
71/2
Как видно из табл.
3
2
0
0
0
P1
P2
P3
p4
p5
1
1
3
–3
0
1
0
0
0
1
0
0
22,
1
1
0
0
–1
0
1
0
1
0
0
1
–2
0
0
0
2
1
–1
0
–1
0
1
0
–2
0
3
1
–5
0
3
0
1
1/2
–1/2 0
0
1/2
1/2
0
0
1
2
1
0
5/2
1/2
0
найденный оптимальный план
задачи (86) – (88) не является оптимальным
131
планом задачи (86) – (89), поскольку две компоненты и
имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из
этих переменных составляется дополнительное ограничение.
Составим, например, такое ограничение для переменной
Из последней симплекс–таблицы (табл. 22) имеем
Таким образом, к системе ограничений задачи (86) –
(89) добавляем неравенство
или
т.е.
(90)
Таблица 23
i
1
2
3
4
5
1
2
3
4
5
Базис Сб
p2
P1
p5
p6
p2
P1
p5
p4
2
3
0
0
2
3
0
0
Р0
7/2
19/2
34
–1
71/2
4
9
32
1
35
3
2
0
0
0
0
P1
P2
P3
p4
p5
P6
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1/2
1/2
1
–1
5/2
1
0
–1
1
2
–
1/2
1/2
2
–1
1/2
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
–1/2
1/2
2
–1
1/2
Находим теперь максимальное значение функции (86)
при выполнении условий (87), (88) и (90) (табл. 23).
Из таблицы 23 видно, что исходная задача целочисленного программирования имеет оптимальный план
При этом плане значение целевой функции
равно
. Дадим геометрическую интерпретацию решения задачи. Областью допустимых решений задачи (86) –
(88) является многоугольник OABCD (рис. 12). Из рис. 12
видно, что максимальное значение целевая функция принимает в точке С (19/2; 7/2), т. e. что Х = (19/2; 7/2; 0; 0; 34) является оптимальным планом. Это непосредственно видно и
из таблицы 22. Так как Х = (19/2; 7/2; 0; 0; 34) не является оптимальным планом задачи (86) – (89) (числа
и – дробные), то вводится дополнительное ограничение
.
Исключая из него и подстановкой вместо них соответствующих значений из уравнений системы ограничений (87),
получим
отсекающий от многоугольника OABCD треугольник EFC.
Как видно из рис. 12, областью допустимых решений
полученной задачи является многоугольник OABEFD. В точке Е(9; 4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты
точки Е – целые числа и неизвестные , и принимают
целочисленные значения при подстановке в уравнение (87)
значений
и
, то
является оптимальным планом задачи (86) – (89). Это следует и из таблицы
23.
133
Пример 23.
Методом Гомори найти решение задачи, состоящей в
определении максимального значения функции
(91)
при условиях
(92)
(93)
– целые. (94)
Дать геометрическую интерпретацию решения задачи.
Решение. Сформулированную задачу перепишем так:
найти максимальное значение функции
(95)
при условиях
(96)
(97)
– целые. (98)
Задача (95) – (98) является частично целочисленной, так
как переменные и
могут принимать нецелочисленные
значения.
Находим симплексным методом решение задаяи (95) –
(97) (таблица 24).
135
i
1
2
3
1
2
3
Базис Сб
p3
P4
p3
P2
0
0
0
4
Р0
19/3
4
0
5
4/3
16/3
1
4
0
Таблица 24
0
P1
P2
P3
p4
2
1
–1
5/3
1/3
1/3
1
3
–4
0
1
0
1
0
0
1
0
0
0
1
0
–1/3
1/3
4/3
После II итерации получаем оптимальный план данной
задачи
При этом плане переменная приняла
нецелочисленное значение. Поэтому необходимо перейти к
новой задаче, добавив к системе ограничений (95) – (97) еще
одно ограничение
или
(99)
Находим теперь решение задачи, состоящей в определении максимального значения функции (95) при условиях
(96), (97) и (99). Данную задачу решаем двойственным симплекс–методом (таблица 25).
i
1
2
3
4
1
2
3
4
Базис Сб
p3
P2
p5
p3
P2
p1
0
4
0
0
4
1
Р0
5
4/3
–1
16/3
10/3
1
1
5
1
4
0
Таблица 25
0
0
P1
P2
P3
p4
p5
5/3
1/3
–1
1/3
0
0
1
0
1
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
–1/3
1/3
–1
4/3
–2
0
1
1
0
0
1
0
5/3
1/3
–1
1/3
Из таблицы 25 видно, что
является оптимальным планом построенной задачи. Так как при этом
плане переменные и принимают целые значения, то он
также является оптимальным планом исходной задачи (95) –
(98).
137
Дадим геометрическую интерпретацию решения задачи. На рис. 13 показана область допустимых решений задачи
(95) – (97). Из рисунка видно, что максимальное значение целевая функция принимает в точке
, т.е. что
является оптимальным планом задачи (95) –
(97). В то же время
(95) – (98), так как переменная
не является планом задачи
принимает дробное значе-
ние.
Поэтому вводим дополнительное ограничение
откуда, подставляя вместо его значение из второго уравнения системы уравнений (96), получаем
. Этому
неравенству на рис. 13 соответствует полуплоскость, ограниченная прямой
, отсекающей от многоугольника ОАВС
треугольник ADE. В области ODEBC находим точку Е(1; 1), в
которой функция (95) принимает максимальное значение.
Так как координаты точки Е – целые числа, то
является оптимальным планом задачи (95) –
(97). Это видно и из таблицы 25.
139
6. Статистический анализ
6.1 Шкалы измерения
Измерение в терминах производимых операций – это
приписывание объекту числа/значения по определенному
правилу. Это правило устанавливает соответствие между измеряемым свойством объекта и результатом измерения признака.
Важно, что точность, с которой признак отражает исследуемое свойство, зависит от процедуры измерения.
Традиционно различают четыре типа шкал измерения:
Номинативная, или номинальная, или шкала наименований.
Порядковая или ординальная шкала.
Интервальная или шкала равных интервалов.
Шкала равных отношений.
Номинативная шкала (неметрическая) – это шкала,
классифицирующая по названию. Название не измеряется
количественно. Оно лишь позволяет отличить один объект от
другого. Это способ классификации объектов, основанный на
распределении их по ячейкам классификации. В ее основе
лежит процедура обычно не ассоциируемая с измерением.
Пользуясь определенным правилом, объекты группируются
по различным классам так, чтобы внутри определенного
класса они были идентичны по измеряемому свойству. Каждому классу дается наименование (обычно числовое). Затем
каждому объекту присваивается соответствующее обозначение.
Простейший случай номинативной шкалы – дихотомическая шкала, состоящая из двух ячеек. Признак, который
измеряют по дихотомической шкале, называют альтернативным.
Расклассифицировав все объекты по ячейкам классификации, мы получаем возможность от наименований перейти к числам, подсчитав количество наблюдений в каждой
ячейке.
В случае такой шкалы учитывается только одно свойство чисел – то, что это разные символы. Остальные свойства
не учитываются: операции с числами, упорядочивание. При
сравнении объектов можно делать вывод о том, принадлежат
ли они к одному классу, тождественны или нет по измеренному признаку.
Таким образом, номинативная шкала позволяет нам
подсчитывать частоты встречаемости разных наименований,
или значений признака, и затем работать с этими частотами
математическими методами.
Единица измерений, которой мы при этом оперируем –
количество наблюдений или частота. Точнее, единица измерения – это одно наблюдение. Такие данные могут быть об-

работаны с помощью метода
2
, биномиального критерия m

и углового преобразования Фишера

.
Порядковая шкала – это шкала классифицирующая
по принципу «больше – меньше». Если в шкале наименований было безразлично, в каком порядке расположены классифицирующие ячейки, то в порядковой шкале они образуют
последовательность от ячейки «самое малое значение» к
ячейке «самое большое значение» (или наоборот). Измерение
в этой шкале предполагает приписывание объектам чисел в
зависимости от степени выраженности измеряемого свойства.
141
Кроме того, желательно соблюдать правило ранжирования для связанных рангов. Если два и более объектов имеют одинаковую выраженность измеряемого свойства, то объектам присваивается один и тот же средний ранг. Следующему объекту присваивается ранг, как если бы все предшествующие объекты различались. Это правило основано на соглашении соблюдения одинаковой суммы для связанных и
несвязанных рангов. В соответствии с этим правилом сумма
всех рангов для группы численностью N должна равняться
N ( N  1)
2
вне зависимости от наличия или отсутствия связей
в рангах.
Ячейки в порядковых шкалах часто называют классами
(«низкий», «большой» и т.п.). В порядковой шкале должно
быть не менее трех классов. В порядковой шкале мы не знаем
расстояний между классами, а знаем лишь, что они образуют
последовательность. От классов легко перейти к числам, просто пронумеровав классы.
Итак, единица измерения в шкале порядка – расстояние
в 1 класс или 1 ранг, при расстояние (реальное) между классами м рангами может быть разным (оно нам неизвестно).
Суть методов получения измерения в порядковой шкале: при сравнении объектов друг с другом можно сказать,
больше или меньше выражено свойство, но нельзя определить – на сколько больше или меньше. Таким образом, при
измерениях в ранговых шкалах из свойств чисел учитывается
то, что они разные, и то, что одно число больше, чем другое.
Интервальная шкала – это шкала, классифицирующая по принципу «больше на определенное количество единиц – меньше на определенное количество единиц». Каждое
значение признака отстоит от другого на равном расстоянии.
Равным разностям между числами в этой шкале соответствуют равные разности в уровне выраженности измеренного
свойства. Иначе говоря, измерения в этой шкале предполагает возможность применения единицы измерения (метрики).
Объекту присваивается число единиц измерения, пропорциональное выраженности измеряемого свойства. Важное
свойство такой шкалы – произвольность выбора нулевой
точки. Ноль не соответствует полному отсутствию свойства.
Произвольность выбора нулевой точки означает, что измерение в этой шкале не соответствует абсолютному значению
измеряемого свойства. Следовательно, применяя эту шкалу,
можно судить насколько больше или меньше выражено свойство при сравнении объектов, но не можем судить, во сколько раз больше или меньше выражено свойство.
Типичный пример: измерение температуры по шкале
Цельсия. 0 – точка замерзания воды, но не отсутствие температуры. Если сегодня +5, а завтра - +10, нельзя сказать, что
сегодня в два раза холоднее, чем завтра.
На самом деле равноинтервальными можно считать
лишь шкалы в единицах стандартного отклонения и процентильные шкалы, и то лишь при условии, что распределение
значений в стандартизирующей выборке было нормальным.
Шкала равных отношений или абсолютная шкала –
это шкала, классифицирующая объекты пропорционально
степени выраженности измеряемого свойства. В шкалах отношений классы обозначаются числами, которые пропорциональны друг другу. Это предполагает наличие абсолютной
нулевой точки отсчета. По отношению к показателю частот
можно применять все арифметические операции.
В силу абсолютности нулевой точки в этой шкале можно определять во сколько раз больше или меньше выражено
то или иное свойство.
143
Перечисленные шкалы полезно характеризовать по
принципу дифференцирующей способности (мощности). В
этом отношении шкалы располагаются в том порядке, в котором они приведены.
6.2 Меры центральной тенденции
Мера центральной тенденции – это число характеризующее выборку по уровню выраженности измеренного признака.
Существует три способа определения центральной тенденции, каждому из которых соответствует своя мера: мода,
медиана и выборочное среднее.
Мода – это такое значение из множества измерений, которое встречается наиболее часто. Моде, или модальному интервалу, соответствует наибольший подъем графика распределения частот. Если график распределения частот имеет одну вершину, то такое распределение называется унимодальным.
Когда два соседних значения встречаются одинаково
часто и чаще, чем любые другие, мода есть среднее этих двух
частот.
Распределение может иметь и не одну моду. Если все
значения встречаются одинаково часто, то принято считать,
что такое распределение не имеет моды.
Бимодальное распределение имеет на графике две вершины, даже если частоты для двух вершин не строго равны.
В этом случае выделяют большую и меньшую моды. Может
быть и большее число вершин. Тогда выделяют наибольшую
и локальные моды. При этом отметим, что мода это значение
признака, а не частота.
Медиана – это такое значение признака, которое делит
упорядоченное (ранжированное) множество данных пополам,
так что одна половина всех значений оказывается меньше
медианы, а другая – больше.
Алгоритм получения медианы:
Упорядочивание всех значений по убыванию или возрастанию.
Если данные содержат нечетное число значений N, то
медианой будет ее центральное значение, то есть значение с
N 1
номером 2
Если данные содержат четное число значений, то медиана точка, лежащая между двумя центральными значениями:
x N 2  x N 21
Md 
2
Выборочное среднее – это оценка математического
ожидания, которая вычисляется по формуле:
X M 
x
i
n
Здесь x i - i  е наблюдаемое значение признака x, n –
количество наблюдений.
Выбор меры
Каждая мера центральной тенденции обладает характеристиками, которые делают ее ценной в определенных условиях.
Оценка дисперсии проводится по формуле:
145
S
2
 ( xi  M )

2
n 1
Однако, чаще используется стандартное отклонение в
генеральной выборке:
 
 ( xi  M )
2
n 1
В тех случаях, когда какие-нибудь причины благоприятствуют более частому появлению значений, которые выше
или, наоборот, ниже среднего образуется асимметричное
распределение.
Показатель асимметрии (A) вычисляется по формуле:
 ( xi  M )
A
2
n 
В тех случаях, когда какие-либо причины способствуют
преимущественному появлению средних или близких к ним
значений, образуется распределение с положительным эксцессом. Если же в распределении преобладают крайние значения, причем одновременно и более низкие и более высокие,
то такое распределение характеризуется отрицательным эксцессом и в центре распределения может образоваться впадина, превращая его в двувершинное.
Показатель эксцесса (E) определяется по формуле:
3
 ( xi  M )
E
n 
4
4
3
Принцип построения большинства интервальных шкал
основан на известном правиле «трех сигм». Примерно 98%
всех значений признака при нормальном распределении
укладывается в диапазон M  3. Можно построить шкалу в
единицах долей стандартного отклонения, которая будет
охватывать весь возможный диапазон изменения признака,
если крайний слева крайний справа интервалы останутся открытыми.
Например, Кенделл предложил шкалу стенов («стандартной десятки»). Среднее арифметическое значение в «сырых» баллах принимается за точку отсчета. Влево и вправо
отмеряются интервалы равные ½ стандартного отклонения.
Очень часто этот подход применяется в психологии.
M=10.2
=2.4
М
5.4 6.6 7.8 9.0 10.2 11.4 12.6 13.8 15.0
0-5 6
7
8 9-10 11 12
13 14-15 16-20
1
3
4
8
2
5
6
7
-2 -1.5 - -0.5 М 0.5 
9
10
1.5 2
Границы интервалов в «сырых
баллах».
«Сырые баллы» на шкале
Стены
Интервалы
в 0.5 
147
Справа от среднего значения будут располагаться интервалы, равные 6 – 10 стенам, причем последний из интервалов открыт. Слева от среднего значения будут располагаться интервалы, соответствующие с 5 по 1 стен, и крайний левый будет открыт. Теперь мы поднимаемся вверх, к оси «сырых баллов», и размечаем границы интервалов в единицах
«сырых баллов». Поскольку М = 10.2,  = 2.4, вправо мы отложим 1/2, то есть 1.2 «сырых балла». Таким образом, граница интервала составит 11.4 «сырых балла». Итак, граница
интервала, соответствующего 6 стену, будут простираться от
10.2 до 11.4 баллов. В этот интервал попадет одно «сырое»
значение – 11.
Влево от среднего значения получаем интервал 9 – 10.2,
соответствующий 5 стену. В него входит 2 «сырых» величины: 9 и 10. Отсюда мы видим, что в шкале стенов иногда на
разное количество «сырых» баллов будет приходиться одинаковое количество стенов.
В принципе шкалу стенов можно построить по любым
данным, измеренным по крайней мере в порядковой шкале,
при объеме выборки n > 200 и нормальном распределении
признака.
Другой способ построения равноинтервальной шкалы –
группировка интервалов по принципу равенства накопленных частот. При нормальном распределении признак в
окрестностях среднего значения группируется большая часть
всех наблюдений, поэтому в этой области среднего значения
интервалы оказываются уже, а по мере удаления от центра
распределения они увеличиваются. Следовательно, такая
процентильная шкала является равноинтервальной только
относительно накопленной частоты.
6.3 Статистические гипотезы
Статистические гипотезы подразделяются на нулевые и
альтернативные, направленные и ненаправленные.
Нулевая гипотеза – это гипотеза об отсутствии различий. Она обозначается как
H и называется нулевой потоX  X  0 , где X , X - со0
1
2
1
2
му, что содержит число 0.
поставляемые значения признаков. Нулевая гипотеза – это то
что мы пытаемся опровергнуть, если перед нами стоит задача
доказать значимость различий.
Альтернативная гипотеза – это гипотеза о значимости
различий. Она обозначается как H 1 . Альтернативная гипотеза – это то, что мы хотим доказать. Поэтому иногда ее
называют экспериментальной гипотезой.
Бывают задачи, когда необходимо доказать как раз не
значимость различий, то есть подтвердить нулевую гипотезу.
Например, если нам надо убедиться, что разные испытуемые
получили хотя и различные, но уравновешенные по значимости задания, или что экспериментальная и контрольная выборки не различаются между собой по каким-то значимым
характеристикам. Нулевая и альтернативная гипотезы могут
быть направленными и ненаправленными.
Направленные гипотезы:
H 0 : X 1 не превышает X 2
H :X
превышает X 2
Ненаправленные гипотезы
H 0 : X 1 не отличается от X 2
1
1
149
H :X
отличается от X 2
Например, если замечено, что в одной из групп изделий
проверяемых по какому-либо признаку значения выше, чем в
другой группе, то для проверки значимости этих различий
необходимо сформировать направленную гипотезу.
Если же мы захотим доказать, что в группе А под влиянием каких-то экспериментальных воздействий произошли
более выраженные изменения, чем в группе Б, то нам тоже
надо сформулировать направленные гипотезы.
Если же мы хотим доказать, что различается форма
распределения в группах А и Б, то формулируется ненаправленная гипотеза.
Проверка гипотез проводится с помощью критериев
статистической оценки различий.
1
1
6.4 Статистический критерий
Статистический критерий – это решающее правило,
обеспечивающее надежное поведение, то есть принятие истинной и отклонение ложной гипотезы с высокой вероятностью.
Статистические критерии обозначают также метод расчета определенного числа и само это число.
Когда, мы говорим, что достоверность различий определяется по критерию


2
, то имеем в виду, что использова-
2
ли метод
для расчета определенного числа.
По соотношению эмпирического и критического значений критериев судят о том, подтверждается или опровергает-

ся гипотеза. Например, если
2
эмп


2
кр
,
H
0
отвергается.
В большинстве случаев для того, чтобы признать различия значимыми, необходимо, чтобы эмпирическое значение критерия превышало критическое, хотя есть критерии
(например, критерий знаков), в которых надо придерживаться противоположного правила.
Эти правила должны оговариваться в руководстве по
использованию критерия.
В некоторых случаях расчетная формула критерия
включает в себя количество наблюдений в исследуемой выборке n. В этом случае эмпирическое значение критерия одновременно является тестом для проверки статистических
гипотез. По специальной таблице определяется, какому уровню статистической значимости различий соответствует данная эмпирическая величина. Примером такого критерия является критерий 
*
, вычисляемый на основе углового преобразования Фишера.
В большинстве случаев одно и то же эмпирическое значение критерия может оказаться значимым или незначимым
в зависимости от количества наблюдений в исследуемой выборке n или от количества степеней свободы v.
Число степеней свободы v равно числу классов вариационного ряда минус число условий, при которых он был
сформирован. К числу таких условий относится объем выборки, среднее и дисперсия.
Если наблюдения расклассифицированы по классам какой-либо номинативной шкалы и подсчитано количество
наблюдений в каждой ячейке классификации, то получается
частотный вариационный ряд. Единственное условие, которое соблюдается при таком формирование – объем выборки
n. Поэтому, если классификация проводится по трем классам,
151
а число испытаний равно 50, мы свободны только в определении количества наблюдений только в двух классах, количество наблюдений в третьем классе будет определяться первыми двумя. Следовательно, здесь имеем v = c – 1 = 3.
Существуют и более сложные способы подсчета степеней свободы, которые будут рассмотрены далее.
Зная n и/или число степеней свободы, по специальным
таблицам можно определить критическое значение критерия
и сопоставить с ним эмпирическое значение.
Критерии делятся на параметрические и непараметрические.
Параметрические критерии включают в формулу расчета параметры распределения, то есть, чаще всего, среднее и
дисперсию (t – критерий Стьюдента, критерий F и др.).
Непараметрические критерии не включают в формулу
расчета параметры распределения и основаны на оперировании частотами или рангами (критерий Q Розенбаума, критерий Т. Вилкоксона и др.).
Возможности и ограничения параметрических и непараметрических критериев
№
1
Параметрические
критерии
Позволяют
прямо
оценить различия в средних, полученные в двух выборках (t – критерий Стьюдента)
Непараметрические критерии
Позволяют оценить
лишь средние тенденции,
например, ответить на вопрос, чаще ли в выборке
А встречаются более высокие, а в выборке Б – более низкие значения признака (критерии Q, U и
др.)
№
2
Параметрические
Непараметричекритерии
ские критерии
Позволяют
прямо
Позволяют оценить
определить различия в дис- лишь различия в диапазоперсиях (критерий Фишера) нах вариативности признака (критерий 
*
)
3
Позволяют выявить
тенденции изменения признака при переходе от условия к условию (дисперсионный
однофакторный
план), но лишь при условии
нормального распределения
признака
Позволяют выявить
тенденции
изменения
признака при переходе от
условия к условию при
любом
распределении
признака (критерии тенденций L и Q)
4
Позволяет оценивать
Эта
возможность
взаимодействие двух и бо- отсутствует
лее факторов и их влияние
на изменение признака
(двухфакторный дисперсионный анализ)
153
№
5
6
Параметрические
критерии
Экспериментальные
данные должны отвечать
двум, а иногда трем, условиям:
А) значения признака
измерены по интервальной
шкале
Б) распределение признака является нормальным
В) в дисперсионном
анализе должно соблюдаться требование равенства
дисперсий в ячейке комплекса
Непараметрические критерии
Экспериментальные
данные могут не отвечать
ни одному из этих условий:
А) значения признаков могут быть представлены в любой шкале,
начиная от шкалы наименований
Б)
распределение
признака может быть любым и совпадение его с
каким-либо
теоретическим законом распределения необязательно и не
нуждается в проверке
В) требование равенства дисперсий отсутствует
Математические расМатематические
четы достаточно сложны
расчеты по большей части
просты и занимают мало
времени (за исключением

критериев
7
2
и )
Если условие 5 выЕсли условия 5 не
полняется,
параметриче- выполняются, непараметские критерии оказываются рические критерии оказыболее мощными
ваются более мощными
6.5 Уровни значимости
Уровень значимости – это вероятность того, что мы сочли различия существенными, а они на самом деле случайны.
Таким образом, уровень значимости – это вероятность отклонения нулевой гипотезы, в то время как она верна. Ошибка,
состоящая в том, что мы отклонили нулевую гипотезу, в то
время как она верна, называется ошибкой 1 рода и обозначается . Если вероятность ошибки – это , то вероятность правильного решения 1 - . Чем меньше , тем больше вероятность правильного решения.
Будем обозначать гипотезу об отсутствии различий -
H
0
, а о статистической достоверности различий -
H
1
.
Правило отклонения H 0 и принятия H 1 .
Если эмпирическое значение критерия равняется критическому значению, соответствующему   0.05 (например,
так исторически сложилось в психологии) или превышает
H
принять H
его, то
отвергается, но мы еще не можем определенно
0
.
Если эмпирическое значение критерия равняется критическому значению, соответствующему   0.01 или пре1
вышает его, то H 0 отклоняется и принимается H 1 .
Исключение: критерий знаков G, критерий Т. Вилкоксона, критерий U Манна – Уитни. Для них установлено обратное соотношение.
Для иллюстрации правила иногда используют «ось значимости».
155
Зона незначимости

Q
Зона неопределенности
0.05
?
Q
6
8
Q
0.01
Зона значимости
эмп
9
Пример «оси значимости» для критерия Q Розенбаума
Критические
значения
критерия
обозначим
Q0.05,Q0.01 , эмпирическое значение критерия как Q эмп .
Уровень статистической значимости или критические
значения критериев определяются по-разному при проверке
направленных и ненаправленных статистических гипотез.
При направленной статистической гипотезе используется односторонний критерий, при ненаправленной гипотезе
– двусторонний критерий.
6.6 Мощность критерия
Мощность критерия – это его способность выявлять
различия, если они есть. Иными словами, это его способность
отклонить нулевую гипотезу об отсутствии различий, если
она неверна.
Ошибка, состоящая в том, что мы приняли нулевую гипотезу, в то время как она неверна, называется ошибкой второго рода.
Вероятность такой ошибки обозначается . Мощность
критерия – это его способность не допустить ошибку второго
рода. Поэтому:
«Мощность» = 1 - 
Мощность критерия определяется эмпирическим путем. Одни и те же задачи могут быть решены разным путем.
При этом обнаруживается, что некоторые критерии позволяют выявит различия там, где другие оказываются неспособны
это сделать, или выявляют более высокий уровень значимости различий. Тогда возникает вопрос, зачем использовать
менее мощные критерии? Дело в том, что основанием для
выбора критерия может быть не только мощность критерия,
но и другие его характеристики, а именно:
Простота;
Более широкий диапазон использования (например, по
отношению к данным, определенным по номинативной шкале, или по отношению к большим n)
Применимость по отношению к неравным по размеру
выборкам
Большая информативность результатов.
157
7. Классификация задач и методов их решения
Множество задач, связанных с объектным анализом,
предполагают сопоставление объектов. Мы сопоставляем
группы объектов по какому-либо признаку, чтобы выявить
различия между ними по этому признаку. Мы сопоставляем
то, что было «до» с тем, что было «после» наших экспериментальных или любых иных воздействий, чтобы определить
эффективность этих воздействий. Мы сопоставляем эмпирическое распределение значений признака с каким-либо теоретическим законом распределения или два эмрирических распределения между собой, с тем, чтобы доказать неслучайность выбора альтернатив или различий в форме распределений.
Мы, даже, можем сопоставить два правила, измеренные
на одной и той же выборке объектов, чтобы установить степень согласованности их изменений, их сопряженность, корреляцию между ними.
Наконец, мы можем сопоставить индивидуальные значения, полученные при разных комбинациях каких-либо существенных условий, с тем чтобы выявить характер взаимодействия этих условий и их влияния на индивидуальные значения признака.
Приведем классификацию задач и методов их решения.
7.1 Классификация задач и методов их решения
№
1
Задача
Условие
Методы
Выявление
А) 2 выQ – критеразличий
в борки объектов рий Розенбаума
уровне исследуеU – критемого признака
рий Манна –
Уитни

*

критерий
(угловое
преобразование
Фишера)
Б) 3 и боS – крителее
выборок рий Джонкира
объектов
H – критерий Крунскала Уоллиса
159
№
2
Задача
Условие
Методы
Оценка
А) 2 заT – критесдвига значений мера на одной и рий Вилкоксона
исследуемого
той же выборке
G – критепризнака
объектов
рий знаков

*

критерий
(угловое
преобразование
Фишера)
2
Б) 3 и бо
x - крилее замеров на
одной выборке терий Фридмана
объектов
L – критерий
тенденций
Пейджа
№
3
Задача
Условие
Методы
2
Выявление
А)
При

различий в рас- сопоставлении
- крипределении при- эмпирического терий Пирсона
знака
распределения с
 -критерий
теоретическим
Колмогорова –
Смирнова
m – биноминальный критерий
2
Б)
При

сопоставлении
- кридвух эмпириче- терий Пирсона
ских распреде -критерий
лений
Колмогорова –
Смирнова

*

критерий
(угловое
преобразование
Фишера)
161
№
Задача
Условие
Методы
4
Выявление
А) Двух
r s - коэфстепени согласо- признаков
фициент рангованности изменевой корреляции
ний
Спирмена
Б) Двух
r s - коэфиерархий или
фициент рангопрофилей
вой корреляции
Спирмена
5
Анализ изА)
Под
S – критеменений признака влиянием одно- рий
тенденций
под
влиянием го фактора
Джонкира
контролируемых
L – критеусловий
рий
тенденций
Пейджа
Однофакторный дисперсионный анализ
Фишера
Б)
Под
Двухфаквлиянием двух торный дисперфакторов одно- сионный анализ
временно
Фишера
7.2 Принятие решения о выборе метода математической обработки
Алгоритм 1. Принятие решения о задаче и методе обработке, на стадии, когда данные уже получены.
По второму столбцу таблицы, какая задача стоит в вашем исследовании.
По третьему столбцу определить, каковы условия решения задачи, например, сколько выборок обследовано или
на какое количество групп можно разделить обследованную
выборку.
Обратиться к алгоритму принятия решения о выборе
критерия (приведены ниже) и определить, какой именно метод или критерий целесообразно применять.
Алгоритм 2. Принятие решения о задаче и методе обработки на стадии планирования исследования.
Определить, какая модель кажется наиболее подходящей для проведения исследований.
Ознакомьтесь с описанием метода.
Проверьте ограничения критерия и решите, сможете ли
вы собрать данные, которые будут отвечать этим ограничениям (объемы выборки, наличие нескольких выборок, монотонность по какому-либо признаку и т.д.).
Провести исследование, а затем обработать данные по
заранее выбранному алгоритму, если удалось выполнить
ограничения.
Если ограничения выполнить не удалось, обратитесь к
алгоритму 1.
Желательно анализировать критерии в следующем порядке:
Назначение критерия
Описание критерия
Гипотезы, которые он позволяет проверить
Графическое представление критерия
Ограничения критерия
Пример или примеры
163
Федеральное государственное образовательное бюджетное
учреждение высшего профессионального образования
“Поволжский государственный университет
телекоммуникаций и информатики»
443010, г. Самара, ул. Льва Толстого 23
________________________________________________________
Подписано в печать 8.05.18г. Формат 60 x 84/16
Бумага офсетная №1. Гарнитура Таймс.
Заказ 1000751. Печать оперативная. Усл. печ. л. 9,53. Тираж 100 экз.
________________________________________________________
Отпечатано в издательстве учебной и научной литературы
Поволжского государственного университета
телекоммуникаций и информатики
443090, г. Самара, Московское шоссе 77, т. (846) 228-00-44
Документ
Категория
Без категории
Просмотров
13
Размер файла
1 762 Кб
Теги
posobie, zaharova, osnovy, bednyak, teoria, uchebnoy, 2018, prinyatie, reshenie
1/--страниц
Пожаловаться на содержимое документа