Табличный вид ЗЛП. Симплекс - таблицы.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика и основные этапы симплекс – метода

Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.

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

Опишем общую идею симплекс-метода.

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

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение ЗЛП к каноническому виду;

2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;

3) исследование опорного плана на оптимальность;

4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;

5) переход к новому, "лучшему" опорному плану.

Для сокращения и упорядочения записей при решении ЗЛП симплекс-методом используются так называемые симплекс-таблицы. Чтобы воспользоваться симплекс-таблицей, ЗЛП нужно привести к табличному виду. Делается это так.

Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:

Подставив в целевую функцию (2.3) вместо базисных переменных их выражения через свободные переменные по формулам (3.1), исключим тем самым из целевой функции базисные переменные. Целевая функция примет вид:

В табличном виде целевая функция записывается так:

где .

Отметим следующие особенности табличного вида ЗЛП:

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

б) из целевой функции исключены базисные переменные и она записана в форме (3.3).

Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:

(3.4)

Тогда заполненная симплекс-таблица выглядит так.

ПРАКТИКУМ

ПО РЕШЕНИЮ ЛИНЕЙНЫХ ЗАДАЧ

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

Введение

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

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

Постановка задачи линейного программирования и формы ее записи

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

Пусть дана система m линейных уравнений и неравенств сn переменными (система ограничений):

и линейная функция

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

В общем случае ЗЛП может иметь бесконечное множество решений. Часто решение , удовлетворяющее ограничениям (1), называют планом . Если все компоненты (3) для , то называют допустимым решением .

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

Каноническая	Стандартная	Общая
1) Ограничения
Уравнения	Неравенства	Уравнения и неравенства
2) Условия неотрицательности
Все переменные	Все переменные	Часть переменных
3) Целевая функция
(max илиmin )

Здесь: – переменные задачи; – коэффициенты при переменных в целевой функции; – коэффициенты при переменных в основных ограничениях задачи; – правые части ограничений.

Пример. Составить экономико-математическую модель задачи: Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.

Решение.Достаточно часто при составлении математической модели экономической задачи бывает удобно данные условия представить в виде таблицы:

Пусть – количество изделий типа А и В соответственно, планируемое к выпуску (, ).

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

Составим систему ограничений, используя заданную ограниченность сырья. При планируемых объемах производства расходуется сырья Iвида: (ед.), что не должно превышать запас 21 ед. Т.о. получим неравенство: . Составляя неравенства по каждому виду сырья, получим систему:

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

Пример. Составить математическую модель задачи: На четырех станках (I, II, III, IV) обрабатываются два вида деталей (А и В). Каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, полученная от выпуска одной детали. Данные приведены в таблице:

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

Решение.Пусть – количество деталей вида А и В соответственно, планируемое к выпуску (, ). Задача аналогична предыдущей, но при составлении модели не следует выпускать из поля зрения фразу: количество деталей вида В не должно быть меньше количества деталей вида А, что математически представимо в виде неравенства: .

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

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

Приведение задач к каноническому виду

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

Примечание : 1) В канонической форме равенства принято записывать так, чтобы правые части ограничений были неотрицательными. Если какое-либо отрицательное, то умножив i -е ограничение на (–1), получим в правой части положительное число. При этом знак неравенства нужно изменить на противоположный.

2) Если ограничение содержит знак «=», то дополнительную переменную вводить не нужно.

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

max (min )

Решение. Второе ограничение системы содержит в правой части отрицательное число –2. Умножим второе ограничение на (–1), при этом знак неравенства изменится на противоположный . Задача примет вид:

max (min )

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

max (min )

.

Составить экономико-математические модели следующих задач:

1. Для изготовления двух видов продукции P 1 и Р 2 используют четыре вида ресурсов S 1 , S 2 , S 3 и S 4 . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице:

Прибыль, получаемая от единицы продукции Р 1 и Р 2 , – соответственно 2 грн. и 3 грн.

3. На приобретение оборудования для нового производственного участка общей площадью 375 м 2 предприятие обладает необходимым количеством денежных средств. Предприятие может заказать оборудование двух видов: машины первого типа стоимостью 10000 грн., требующие производительную площадь 6 м 2 (с учетом проходов), производящие 4000 единиц продукции за смену, и машины второго типа стоимостью 20000 грн., занимающие 10 м 2 площади, производящие 5000 единиц продукции за смену. Общая производительность данного производственного участка должна быть не менее 221000 единиц продукции за смену. Построить модель задачи при условии, что оптимальным для предприятия вариантом приобретения оборудования считается тот, который обеспечивает наименьшие общие затраты.

4. Фермер планирует произвести не менее 120 тонн пшеницы, 70 тонн кукурузы и 15 тонн гречихи. Для этого можно использовать два массива сельскохозяйственных угодий в 1000 и 800 га. В таблице приведены урожайность каждой культуры на различных участках (верхний показатель) и затраты на 1 га сельскохозяйственных угодий при производстве различных культур (нижний показатель). Требуется составить такой план засева, чтобы валовой сбор зерна удовлетворял плановому заданию, а стоимость затрат была наименьшей.

5. Фирма имеет возможность рекламировать свою продукцию, используя для этого телевидение, радио и газеты. Затраты на рекламу в бюджете фирмы ограничены суммой 8000 грн. в месяц. Опыт прошлых лет показал, что 1 грн., потраченная на телерекламу, дает фирме прибыль в размере 10 грн., а потраченная на рекламу по радио и в газетах – соответственно 4 и 8 грн.

Фирма намерена затратить на теле- и радиорекламу не более 70% рекламного бюджета, а затраты на газетную рекламу не должны больше чем вдвое превышать затраты на радиорекламу.

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

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

Графический метод решения задач линейного программирования

1. Область решений линейных неравенств.

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

(1)

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

Пример 1.

Решение. Строим прямую по двум точкам, например, по точкам пересечения с осями координат (0; 4) и (6; 0). Эта линия делит плоскость на две части, т.е. на две полуплоскости. Берем любую точку плоскости, не лежащую на построенной прямой. Если координаты точки удовлетворяют заданному неравенству, то областью решений является та полуплоскость, в которой находится эта точка. Если же получаем неверное числовое неравенство, то областью решений является та полуплоскость, которой эта точка не принадлежит. Обычно для контроля берут точку (0; 0).

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

Пример 2. Найти полуплоскость, определяемую неравенством

Решение. Строим прямую , например, по точкам (0; 0) и (1; 3). Т.к. прямая проходит через начало координат, точку (0; 0), то нельзя брать ее для контроля. Возьмем, например, точку (– 2; 0) и подставим ее координаты в заданное неравенство. Получим . Это неверно. Значит, областью решений данного неравенства будет та полуплоскость, которой не принадлежит контрольная точка (заштрихованная часть рис. 2).

2. Область решений системы линейных неравенств.

Пример. Найти область решений системы неравенств:

Решение. Находим область решений I-го неравенства (рис. 1) и II-го неравенства (рис. 2).

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

Если к заданной системе неравенств добавить условия и , то область решений системы неравенств будет находиться только в I координатной четверти (рис. 4).

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

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

3. Алгоритм графического метода решения ЗЛП

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

1) Строим все полуплоскости, соответствующие ограничениям системы.

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

3) Строим вектор , выходящий из начала координат, где и – это коэффициенты при неизвестных в целевой функции . Этот вектор указывает направление возрастания целевой функции.

4) Перпендикулярно вектору проводим так называемую линию уровня (т.е. прямую , проходящую через начало координат).

5) Перемещаем линию уровня параллельно самой себе в направлении вектора (если задача на максимум (max )) или в противоположном направлении (если задача на минимум (min )) до тех пор, пока линия уровня имеет хотя бы одну общую точку с ОДР.

6) Находим координаты этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.

7) Подставляем эти координаты в целевую функцию и находим ее max (или min ).

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

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

Т.о. задача примет вид

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

Областью решений неравенств является пятиугольник ABCDE .

Построим вектор .Через начало координат перпендикулярно вектору проведем линию уровня . И затем будем перемещать ее параллельно самой себе в направлении вектора до точки выхода из области допустимых решений. Это будет точка С . Найдем координаты этой точки, решив систему, состоящую из уравнений первой и четвертой прямых:

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

max (min )

Решение. Область допустимых решений – открытая область (рис. 6). Линия уровня проходит через точку В . Функция Z имеет минимум в этой точке. Линию уровня построить нельзя, так как нет точки выхода из области допустимых решений, это значит, что .

Задания для самостоятельной работы .

1. Найти область решений системы неравенств:

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

3. Составить экономико-математическую модель и решить графически задачу линейного программирования

Фирма выпускает изделия двух видов А и В. Изделия каждого вида обрабатывают на двух станках (I и II). Время обработки одного изделия каждого вида на станках, время работы станков за рабочую смену, прибыль фирмы от реализации одного изделия вида А и вида В занесены в таблицу:

Изучение рынка сбыта показало, что ежедневный спрос на изделия вида В никогда не превышает спрос на изделия вида А более чем на 40 единиц, а спрос на изделия вида А не превышает 90 единиц в день.

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

Симплексный метод решения задач линейного программирования

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

Этот метод включает в себя три основные этапа:

2) Правило перехода к лучшему (точнее, нехудшему) решению.

3) Критерий проверки найденного решения на оптимальность.

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

1) Построение начального опорного плана.

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

Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной.

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

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

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

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

В каждом ограничении слева добавим положительную переменную , соответственно запишем канонический вид задачи:

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

Запишем теперь начальный опорный план

(0; 0; 0; 0; 16; 4; 0).

2) Составление симплексных таблиц. Критерий оптимальности.

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

Базис		В			…
					…
					…
					…
…	…	…	…	…	…	…
					…
					…

Здесь приняты следующие обозначения.

Столбец «Базис» – это базисные переменные.

Столбец «» – это коэффициенты при базисных переменных в целевой функции.

Столбец «В» – правые части ограничений;

– коэффициенты при переменных в ограничениях;

– коэффициенты при переменных в целевой функции.

Последняя строка в таблице () – это проверочная или оценочная строка.

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

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

Например,

Оценки () базисных переменных всегда равны нулю.

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

Опорный план будет оптимальным тогда и только тогда, когда все оценки

Для задачи на max и

Для задачи на min .

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

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

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

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент .

Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.

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

Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.

2) Определяем базисные переменные – это .

3) Заполняем первую таблицу

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0
	0	16	2	1	0	1	0	0
	0	5	0	1	0	0	1	0
	0	21	3	0	0	0	0	1	–

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

Находим : ; ;

Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной . Значит, строка базисной переменной – разрешающая, следовательно, из базиса нужно вывести переменную . Элемент =1 – разрешающий. Новый базис: .

Заполнение следующей таблицы начинаем со столбцов «Базис» и «». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы под переписываем без изменения, т. к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элемент найдем из прямоугольника

Или элемент = из прямоугольника

Оценки для новой таблицы можно находить по этому же правилу.

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

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0	6
	0	16	2	1	0	1	0	0	16
	0	5	0	1	0	0	1	0	5
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0	таб. 1
	0	3	1	0	1	0	–3	0	3
	0	11	2	0	0	1	–1	0	5,5
	3	5	0	1	0	0	1	0	–
	0	21	3	0	0	0	0	1	7
		15	–2	0	0	0	3	0	таб. 2

Базис		В	2	3	0	0	0	0
	2	3	1	0	1	0	–3	0	–
	0	5	0	0	–2	1	5	0	1
	3	5	0	1	0	0	1	0	5
	0	12	0	0	–3	0	9	1
		21	0	0	2	0	–3	0	таб. 3
	2	6	1	0	–0,2	0,6	0	0
	0	1	0	0	–0,4	0,2	1	0
	3	4	0	1	0,4	–0,2	0	0
	0	3	0	0	0,6	–1,8	0	1
		24	0	0	0,8	0,6	0	0	таб. 4

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

– это значения из столбца В, т.е. , , , .

Свободные (небазисные) переменные .

Итак, = (6; 4; 0; 0; 1; 3),

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

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

1) Если в оценочной строке симплекс-таблицы оценка = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план.

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

Задания для самостоятельной работы .

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

а)

б)

m in

Понятие двойственности

1) Симметричные двойственные задачи

Рассмотрим задачу производственного планирования. Пусть предприятие имеет m видов ресурсов объемом единиц. Эти ресурсы должны быть использованы для выпуска n видов продукции. Пусть – норма потребления i -го вида ресурса на производство единицы j -ой продукции; – цена реализации j -ой продукции; – объем производства j -ой продукции, обеспечивающий предприятию максимальную выручку.

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

Или в краткой форме записи математическая модель задачи имеет вид:

(1)

Задачу (1) – (3) называют исходной.

По исходным данным задачи (1) – (3) сформируем другую экономическую задачу.

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

– покупатель стремится минимизировать их общую стоимость;

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

Эти требования можно записать в виде следующей ЗЛП:

Или в краткой форме записи:

(4)

Полученную задачу (4) – (6) называют двойственной. Переменные называются двойственными оценками, или теневыми ценами.

Задачи (1) – (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т. к. они обладают следующими свойствами:

1. Если в одной задаче ищется максимум целевой функции, то в другой – минимум.

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

3. В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла: если задача на max , то все неравенства содержат знаки «», если на min , то все неравенства содержат знаки «».

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

5. Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Примечание: Понятие «прямой» и «двойственной» задач условно.

2) Построение модели двойственной задачи

Используя свойства (1–6), покажем на конкретном примере построение двойственной задачи.

Пример. Пусть исходная задача имеет вид:

Нужно составить к ней двойственную.

Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.

1	–1	2	2	1	2	5	11	2
2	1	–3	4	А Т =	–1	1	–1	1	3
А =	5	–1	1		3	2	–3	1	2	1
11	1	2	1	2	4	3	1	min
2	3	1	max

Теперь запишем двойственную задачу по А Т с переменными , .

Пример. К заданной задаче записать двойственную:

Решение. Так как задача на min , то все неравенства должны иметь знаки «». С этой целью второе ограничение умножим на (–1); при этом знак неравенства изменится на противоположный. Теперь задача будет иметь вид:

Запишем матрицы А и А Т .

1	1	1	1	–2	5
А =	–2	–3	–5	А Т =	1	–3	2
5	2	min	1	–5	max

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

3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач

Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П 1 , П 2 , П 3 . Для этого оно располагает объемами ресурсов 3-х видов Р 1 , Р 2 , Р 3 . Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:

	П 1	П 2	П 3
Р 1	4	2	1	180
Р 2	3	1	1	210
Р 3	1	2	5	244
	10	14	12

Требуется:

1) построить модель исходной и двойственной задач;

2) решить исходную задачу симплексным методом;

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

4) дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач;

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

Решение. 1. Построим модель исходной задачи

Здесь х 1 , х 2 , х 3 – план выпуска продукции.

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

2. Решим исходную задачу симплексным методом.

Запишем ее канонический вид:

х 4 , х 5 , х 6 – дополнительные и они же базисные переменные. Начальный опорный план (0; 0; 0; 180; 210; 244).

Базис		В	10	14	12	0	0	0
	0	180	4	2	1	1	0	0	90
	0	210	3	1	1	0	1	0	210
	0	244	1	2	5	0	0	1	122
		0	–10	–14	–12	0	0	0	таб. 1

Базис		В	10	14	12	0	0	0
	14	90	2	1	0,5	0,5	0	0	180
	0	120	1	0	0,5	–0,5	1	0	240
	0	64	–3	0	4	–1	0	1	16
		1260	18	0	–5	7	0	0	таб. 2
	14	82	2,375	1	0	0,625	0	–0,125
	0	80	1,375	0	0	0,125	1	–0,625
	12	16	–0,75	0	1	–0,25	0	0,25
		1340	14,25	0	0	5,75	0	1,25	таб. 3

Так как все оценки , то получен оптимальный план:

= (0; 82; 16; 0; 80; 0); = 1340.

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

основные переменные			дополнительные переменные
дополнительные переменные			основные переменные

Откуда: 5,75; 0; 1,25; 14,25; 0; 0.

= (5,75; 0; 1,25; 14,25; 0; 0); 1340.

Таким образом получили =1340.

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

Продукцию І-го вида к выпуску не планируют, ІІ-го вида – в количестве 82 ед. и ІІІ-го вида – в количестве 16 ед.

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

Сырье І и ІІІ видов израсходовано полностью. А сырье ІІ вида осталось в количестве 80 ед.

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

Таким образом, сырье І и ІІІ видов дефицитное, причем наиболее дефицитное сырье І-го вида. Сырье ІІ вида недефицитное.

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

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

Ответ: = (0; 82; 16; 0; 80; 0); = 1340;

= (5,75; 0; 1,25; 14,25; 0; 0); 1340

Наиболее дефицитное сырье І вида. Наиболее убыточный І вид продукции.

Задания для самостоятельной работы .

Для производства четырех видов продукции (П 1 , П 2 , П 3 , П 4) используются три вида ресурсов. Норма затрат ресурсов, использованных для выпуска единицы продукции каждого вида, цена единицы продукции и запасы ресурсов приведены в таблице.

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

Ресурсы Продукция	Затраты ресурсов на единицу продукции				ресурсов
	П 1	П 2	П 3	П 4
Р 1	2	3	4	4	2100
Р 2	5	5	0	7	2800
Р 3	8	7	10	9	3000
	60	65	55	62

Транспортная задача (ТЗ)

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

max (1)

(2)

Здесь: – запасы поставщиков;

– спрос потребителей;

– тарифы, т.е. стоимости перевозки единицы груза от -го поставщика к -му потребителю;

Z – транспортные расходы;

Количество продукта, перевозимого от -го поставщика к -му потребителю.

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

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

Любая транспортная задача имеет допустимое решение (матрицу перевозок ), если

Если условие (4) выполняется, то транспортную задачу называют транспортной задачей закрытого типа .

Допустимое решение транспортной задачи часто называют планом перевозок.

1) Построение начального опорного плана. Его вырожденность или невырожденность. Ранг матрицы системы.

а) Метод северо-западного угла.

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

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

Найти стоимость перевозок.

Решение. Строим распределительную таблицу и находим груз х 11 = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2):

х 12 = min (а 1 – х 11 ; b 2) = min (5; 35) = 5.

Теперь переходим по ІІ столбцу в клетку (2; 2):

х 22 = min (30; b 2 – х 12) = min (30; 30) = 30.

Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3):

х 33 = min (40; 20) = 20.

х 34 = min (а 3 – х 33 ; b 4) = min (20; 20) = 20.

Таким образом, получен план перевозок:

	15		35		20		20
20	4	6	12	5
	15		5
30	2	7	8	10
	30
40	5	3	4	6
	20		20

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

б) Метод минимального элемента (наименьшей стоимости).

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

Пример. Построить начальный опорный план методом минимальной стоимости и найти транспортные расходы для транспортной задачи: поставщики а = (20; 30; 40); потребители = (15; 35; 20; 20); тарифы перевозок

Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т. к. в ней наименьший тариф х 21 = min (30; 15) = 15.

	15		35		20		20
20	4	6	12	5
	20
30	2	7	8	10
	15		15
40	5	3	4	6
	35		5

Потом заполняем клетку (3; 2) с тарифом с 32 = 3;

х 32 = min (40; 35) = 35.

х 14 = min (20; 20) = 20;

х 23 = min (а 2 – х 21 ; b 3 – х 33) = min (15; 15) = 15.

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

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

В пунктах а) и б) , а число заполненных клеток 5. Следовательно, полученные планы – вырожденные.

2) Метод потенциалов. Признак оптимальности опорного плана.

Допустимое решение транспортной задачи является оптимальным тогда и только тогда, когда можно найти такие числа – потенциалы , и , , которые удовлетворяют следующим условиям:

II. для всех заполненных клеток; (5)

III. для всех пустых клеток. (6)

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

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

3) Переход к нехудшему опорному плану.

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

Приведем примеры разновидностей форм циклов:

В каждом случае только одна вершина цикла находится в незаполненной клетке. Ее называют началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е. по максимальной оценке . Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–», «+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Z min .

Транспортная задача открытого типа

Если для транспортной задачи выполняется одно из условий

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

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

Запишем алгоритм решения транспортной задачи :

1) Проверка типа модели ТЗ.

2) Построение начального опорного плана (любым способом).

3) Проверка плана на вырожденность.

4) Проверка плана на оптимальность методом потенциалов:

а) нахождение потенциалов из системы

(для всех заполненных клеток);

б)проверка второго условия оптимальности

(для всех пустых клеток).

5) Переход к нехудшему опорному плану (если это необходимо).

Пример. На складах имеются запасы однотипного товара в количестве а (35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52; 17; 20). Матрица затрат на доставку единицы товара от i -го поставщика j -му потребителю:

.

Решение. Определим тип модели транспортной задачи. Суммарная мощность поставщиков: 35+40+40+50=165 (единиц товара); Суммарный спрос потребителей: 31+52+17+20=120 (единиц товара).

Т.к. , то имеем модель открытого типа.

Введем фиктивного потребителя, спрос которого равен

165 –120 =45 (единиц товара).

Тарифы 0. Т.о. получаем модель закрытого типа, m = 4 – число поставщиков, n = 5 – число потребителей. Ранг матрицы задачи . Построим начальный опорный план методом минимального элемента (наименьшей стоимости).

	31		52		17		20		45
35	5	4	3	1	0	0
	15		20
40	2	3	5	8	0	1
	31		9
40	6	8	7	10	0	4
	40
50	5	6	7	2	0	4
	43		2		5
	1		2		3		1		– 4		Таб.1

r = 8, следовательно, опорный план является невырожденным.

(ден. ед.).

Исследуем опорный план на оптимальность, используя метод потенциалов.

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

Из записанной системы находим: , , ,, , , , , .

.

(1; 1) 0 + 1 – 5 = –40;

(1; 2) 0 + 2 – 4 = –20;

(1; 5) 0 – 4 – 0 = –40;

(2; 3) 1 + 3 – 5 = –10;

(2; 4) 1 + 1 – 8 = –60;

(2; 5) 1 – 4 – 0 = –40;

(3; 1) 4 + 1 – 6 = –10;

(3; 2) 4 + 2 – 8 = –20;

(3; 3) 4 + 3 – 7 = 00;

(3; 4) 4 + 1 – 10 = –50;

(4; 1) 4 + 1 – 5 = 00;

(4; 4) 4 + 1 – 2 = 30.

Т.к. среди свободных клеток есть такие, в которых второе условие оптимальности не выполняется, то план не оптимален.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка

4 + 1 – 2 = 3.

Найдем цикл перераспределения груза для этой клетки.

Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.

– объем перепоставки.

Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.

	31		52		17		20		45
35	5	4	3	1	0	0
	17		18
40	2	3	5	8	0	–2
	31		9
40	6	8	7	10	0	1
	40
50	5	6	7	2	0	1
	43		2		5
	4		5		3		1		–1		Таб.2

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

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

, , , , , , , , .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: .

Выпишем клетки, в которых условие нарушено:

(1; 2) 0 + 5 – 4 = 10.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (1; 2), т. к. ей соответствует положительная оценка 1. Найдем цикл перераспределения груза для этой клетки.

– объем перепоставки.

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

	31		52		17		20		45
35	5	4	3	1	0	0
	18		17
40	2	3	5	8	0	–1
	31		9
40	6	8	7	10	0	2
	40
50	5	6	7	2	0	2
	25		20		5
	3		4		3		0		–2		Таб.3

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

Исследуем опорный план на оптимальность.

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

, , ,, , , , , .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: .

Второе условие оптимальности выполняется для всех свободных клеток, следовательно, план оптимален.

Наименьшие транспортные затраты .

Ответ: ; оптимальный план распределения поставок расположен в таб. 3.

Задания для самостоятельной работы .

Составить план перевозок с минимальными транспортными затратами.

а)

б)

Решение оптимизационных задач с помощью Excel

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

· Составить математическую модель экономической задачи;

· Решить полученную экстремальную математическую задачу;

· Дать экономическую интерпретацию ответу.

Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.

Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.

· Составление математической модели.

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

Так как необходимо определить количество изделий А и В, то введем следующие обозначения:

– количество изделий А, планируемое к выпуску;

– количество изделий В, планируемое к выпуску;

Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая» , связанное с экстремумом, соответствует прибыли).

– математическая модель задачи.

· Решение полученной экстремальной задачи:

Для решения задачи воспользуемся возможностями MicrosoftExcel.

Откройте MicrosoftExcel.

В ячейки первой строки (в данном случае А1 и В1) введите обозначения имеющихся в задаче переменных , (язык и шрифт значения не имеют, т. к. обозначения необходимы для понимания смыслов соответствующих им чисел).

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

В ячейку А4 введите обозначение целевой функции Z=.

В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи

(), подставляя вместо и , соответствующие им значения из ячеек А2 и В2. (Вспомните, что введение формулы начинается со знака =)

После нажатия кнопки Enter на экране монитора должно быть следующее. (Продумайте, как изменится картинка, если ввести иные значения и , к примеру, не 1, а 2. А теперь поэкспериментируйте. Оправдался ваш прогноз?)

В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения.

В ячейку А6 введите формулу вычисления левой части первого ограничения , подставляя вместо и , соответствующие им значения из ячеек А2 и В2.

В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее.

Аналогично в ячейку А7 введите формулу вычисления левой части второго ограничения , а в В7 его свободный член – 8; в ячейку А8 введите формулу вычисления левой части третьего ограничения , а в В8 его свободный член – 12; в ячейку А9 введите формулу вычисления левой части четвертого ограничения , а в В9 его свободный член – 5;

После нажатия кнопки Enter на экране монитора должно быть следующее.

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

В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации)

В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите:

Т.к. в данной задаче функция Z исследуется на максимум, то оставляем Равной: максимальному значению .

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

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

Т.е. заполненная ячейка должна принять вид:

После этого заполняют пространство ячейки Ограничения: Для чего нужно щелкнуть по кнопке Добавить , в результате чего на экране появится новое окно:

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

В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6).

Т.о. перед вами на экране должна быть следующая картинка:

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

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

Поэтому после введения последнего ограничения вновь нажмите кнопку Добавить и в Ссылка на ячейку: введите номер ячейки, содержащей числовое значение ; выберите знак >=; а в Ограничение: введите 0.

Еще раз нажмите Добавить и аналогичным образом создайте условие неотрицательности для .

Таким образом, компьютер получил все те ограничения, которые есть в условии задачи, поэтому теперь можно нажать ОК . В результате на экране появится следующее:

Появилось? Если ДА, то нажимайте Выполнить .

Обратите внимание на то, какие теперь значения принимают , и Z.

4; = 4; Z = 20 – Это и есть найденное оптимальное решение задачи () и соответствующее

экстремальное значение целевой функции ().

Математически задача решена. Осталось дать экономическую

интерпретацию полученному.

· Дадим экономическую интерпретацию ответу.

Для достижения наибольшей прибыли 20 грн. необходимо производить 4 изделия А и 4 изделия В.

Литература

1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. – К.: КНЕУ, 2001.

2. Исследование операций в экономике/ Под ред. проф. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 2000.

3. Конюховский П.В. Математические методы исследования операций в экономике: учебное пособие. – СПб. – Москва – Харьков – Минск, 2005.

4. Кулян В.Р. и др. Математическое программирование. – К.: МАУП, 2005.

5. Таха, Хемди. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001.

Симплексный метод. Алгоритм. Признак оптимальности опорного плана.

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

Рис. Геометрическая интерпретация идеи симплекс-метода

в случае двух (рис а) и трех (рис б) переменных.

Симплекс – это выпуклый многоугольник в n – мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на 2 полупространства).

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

Базисное решение – это одно из допустимых решений, находящихся в ОДР.

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

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

Алгоритм симплексного метода:

1. Построить математическую модель задачи.

1. Преобразовать полученную математическую модель в каноническую форму, у которой: правые части условий неотрицательны; условия являются равенствами (при необходимости ввести искусственные переменные).
2. Построить симплекс таблицу и найти начальный опорный план решения задачи. Множество переменных, которые являются базисными , принимаются за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные переменные равны нулю.
3. Проверка базисного решения на оптимальность осуществляется с помощью специальных оценок коэффициентов целевой функции (смотреть последнюю строку таблицы). Если задача решается на max, то все оценки должны быть неотрицательными, если на min, то все оценки должны быть неположительные.
4. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличит целевую функцию. При решении задач на max в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по max положительному значению оценки коэффициентов целевой функции. Столбец таблицы, который содержит эту оценку, называется генеральным столбцом. Если хотя бы один элемент столбца положительный, то отыскивается генеральная строка (в противном случае задача не имеет оптимального решения). Если в этом столбце есть нули, то нужно брать другой столбец. Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший, соответствующая строка называется генеральной. Она соответствует ресурсу, который ограничивает производство на данном шаге. Элемент симплекс таблицы, находящийся на пересечении генеральной строки и столбца, называется генеральный элемент. Все элементы генеральной строки, включая свободный член, делятся на генеральный элемент. В результате генеральный элемент становится равным 1. Далее необходимо чтобы все другие элементы генерального столбца стали равными 0. генеральный столбец должен стать единичным. Все строки кроме генеральной преобразуют следующим образом: полученные элементы новой строки умножим на соответствующие элементы генерального столбца, и полученное произведение вычитаем из элементов старой строки. Значение новых базисных переменных получим в соответствующих ячейках столбца свободных членов (правило прямоугольников).
5. Полученное базисное решение проверяется на оптимальность (шаг №4). Если оно оптимально, то вычисления прекращаются, в противном случае находится новое базисное решение (шаг №5).

Признак оптимальности опорного плана

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

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

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

— Θ (столбец симплекс-отношений) не рисуется для строчек с отрицательными и нулевыми значениями. Из всех θ выбираем наименьшее, так делается всегда неважно на min или на max исходная задача.

— Разрешающая строка всегда показывает, какой элемент надо вывести из базиса, а разрешающий столбец – какой элемент надо ввести в базис.

Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b 0j > (i=1, ..., n m). В опорном плане х 0 , содержащемся в этой таблице, значения всех свободных переменных x m+j равны нулю и f(х 0) =b 00 . Если же увеличивать какую-либо из свободных переменных x m+ j, то, как видно из равенства (2.5), в силу неотрицательности b 0j значение f(х) начнет уменьшаться. Следовательно, при x о функция f(х) достигает наибольшей величины, а значит, х 0 действительно является оптимальным опорным планом.

Возможность переход от одного опорного плана к другому

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Б о с опорным планом х 0 в новый базис Б 1 с опорным планом х 1 при котором; значение функции f увеличивается, т. е. f(x i)>f(x 0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b 0s <0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной x m+s ;

2) какое значение должна принимать новая базисная переменная x m+s в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2.4) все x m+j , кроме x m+s , равны нулю. Тогда

x i = b io -b is x m+s (i=l, ..., m)

Из этих равенств видно, что с возрастанием x m+s значения тех базисных переменных х i для которых коэффициенты b is <0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. С увеличением x m+s значения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать x m+s , не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых b is >0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Базисные переменные х d , ..., x k , ..., x p будут оставаться неотрицательными до тех пор, пока x m+s удовлетворяет системе неравенств

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 или x m+s < b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s < b po /b ps

т. е. при x m+s

Пусть наименьшая из дробей b io /b is соответствует i = k, т.е.

min { b io /b is }= b k0 /b ks .

Тогда можно сказать, что пока x m+s не превышает величины b k0 /b ks , т. е. x m+s 0, то переменная х k станет равной пулю: x k = b k0 -- b ks b ko /b ks =0, и тем самым будет произведено преобразование базиса Б о = {х 1 ; ...; x k ; ...; х m } в новый базис, при котором переменная x m+s из группы свободных переходит в базисные, а переменная х k занимает место x m+s в группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х 1 в новом базисе Б 1 ={х 1 ; ...; x m+s ; ...; x m } будет иметь m положительных компонент и m-n нулевых. В плане x 1 некоторые базисные переменные могут принять нулевые значения в двух случаях:

1) когда в плане х 0 имеются базисные переменные, равные нулю;

2) когда наименьшая из дробей b io /b is будет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =b oo - b os x m+s ясно, что при b 0s <0 и фиксированном x m+s >0, значение f(х) зависит от абсолютной величины коэффициента b 0s: чем больше |b 0s |, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной x m+s . Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную x m+j ,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

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

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

Отметим, что нам уже известно значение новой базисной переменной x m+s в новом опорном плане: оно равно b ko /b ks . Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х 1 ;..., x m+s ; ...,х m будет выражена через измененную систему свободных переменных x m+1 ,…,x k ,…, х n . Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

Коэффициент b ks = 0 при x m+s в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная x m+s выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная х k . Таким образом, переменные x m+s и x k поменялись ролями.

Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение x m+s из подставим в остальные равенств (обозначим f через x 0 ,тогда равенство будет входить в систему при i= 0)

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

Симплекс-метод решения задач линейного программирования

Симплексный метод – это аналитический метод решения ЗЛП, реализующий алгоритм графического метода аналитически, без построения чертежа.

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

Симплекс метод может использоваться для решения ЗЛП с любым количеством неизвестных.

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

Симплекс-метод с естественным базисом применяется, если ЗЛП задана в канонической форме записи, и матрица в КЗЛП содержит единичную подматрицу размером m´m . Для определённости положим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный план выбирается следующим образом:

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

Математический признак оптимальности состоит из следующих двух теорем:

1. Если для всех векторов A 1 , A 2 , … , A n выполняется условие , где , то полученный опорный план является оптимальным. В сумме для определения Z j участвуют m слагаемых, то есть в ней участвуют не все коэффициенты целевой функции c j , а лишь с номерами соответствующими номерам текущих базисных векторов A i , количество которых равно m .

2. Если для некоторого вектора, не входящего в базис, выполняется условие , то следует искать новый опорный план, для которого значение ЦФ больше, чем для текущего. При этом возможны два случая:

а) если все компоненты вектора A k , подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

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

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

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор A r , который даёт минимальное положительное оценочное отношение

Строка A r , в которой находился старый базисный вектор, называется направляющей, столбец A k и элемент a rk - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i -й строки - по формулам:

Значения нового опорного плана рассчитываются по аналогичным формулам:

,

Процесс продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди разностей Δ j , j=1, 2, … , n оптимального плана нулевыми являются только разности, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.

Пример. Решить ЗЛП по модели:

найти ,

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

Эта ЗЛП сводится к каноническому виду путём введения дополнительных переменных x 3 и x 4 :

КЗЛП имеет необходимое количество (два) нулевых столбцов при x 3 и x 4 , то есть обладает очевидным начальным опорным планом (0,0,300,150).

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

Номер симплекс-таблицы	Базис	с j	с j					Q
B	A 1	A 2	A 3	A 4
	← A 3
A 4
Δ	-		-2	-3			-
I	→ A 2			1/3		1/3
← A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→ A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Остановимся подробнее на заполнении симплекс-таблиц и, соответственно, получении решения КЗЛП.

В верхнюю строку общей таблицы внесены коэффициенты c j , j=1, 2, 3, 4 при переменных в ЦФ. В первые две строки нулевой симплекс-таблицы внесены вектор-столбцы B, A 1 , A 2 , A 3 , A 4 , соответствующие векторной форме записи КЗЛП. Поскольку исходным базисом является пара векторов A 3 , A 4 , они внесены в колонку под названием “Базис” нулевой симплекс-таблицы. При этом, A 3 внесён в первую строку, что определяется единицей, являющейся первым элементов этого вектора, а вектор A 4 - во вторую строку, у этого вектора единица находится во второй строке. В столбец под названием “ c i ” внесены коэффициенты целевой функции, соответствующие базисным векторам A 3 , A 4 , то есть c 3 , c 4 . Они оба равны нулю. Далее вычисляются значения разностей Δ для векторов B, A 1 , A 2 , A 3 , A 4 и заносятся в третью строку нулевой таблицы. Для вектора A 1 :

для вектора :

Аналогично , .

Для вектора B вычисление разности несколько упрощается, поскольку ему нет соответствующего коэффициента c j , j=1, 2, 3, 4 в ЦФ:

Не для всех векторов A 1 , A 2 , A 3 , A 4 полученные разности являются неотрицательными, поэтому выбранный нами опорный план не является оптимальным. Нам необходимо искать новый опорный план, а для этого нужно заменить один из входящих в базис векторов A 3 , A 4 .

Для определения вектора, который мы должны ввести, ищем вектор, для которого значение разности получилось минимальным. Таким является вектор, A 2 , ему соответствует минимальное значение разности: -3. То есть индекс k из формулы (8.4) равен 2. Для определения вектора, который мы должны будем вывести из базиса, вычисляем значения Q для каждой строки по формуле (8.5) и вносим их в последнюю колонку. В данном случае в каждой строке мы должны величину элемента вектора B разделить на величину элемента вектора A 2 . В первой строке получим 300/3=100, во второй: 150/1=150. Меньше получилось отношение в первой строке, ей соответствовал базисный вектор A 3 , следовательно, индекс r в формуле (8.5) равен 1, a rk =3 (выделен в таблице рамкой), а выводить из базиса мы будем вектор A 3 (обозначено в таблице стрелкой).

Поскольку среди элементов вектора A 2 , который должен быть введён в базис, имеются положительные, то можно получить новый опорный план и решение следует продолжить.

После этого заполняется вторая симплекс-таблица. Для перерасчёта элементов векторов B, A 1 , A 2 , A 3 , A 4 используются формулы (8.6)-(8.8). Они несколько отличаются для определения элементов направляющей строки (в нашем случае первая) и для определения элементов прочих строк. Распишем вычисления нескольких элементов:

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

Как мы видим, в результате расчётов во второй симплекс-таблице с базисными векторами A 2 , A 1 все разности получились неотрицательные, что означает достижение оптимального плана (75; 75; 0; 0). Симплекс-разность для вектора В равна искомому максимальному значению ЦФ - 375.

Теорема (о конечности симплекс-алгоритма). Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода, причём начинать можно с любого исходного базиса.