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

Камский Государственный Политехнический Институт

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ и МЕТОДЫ

Линейное программирование

Учебное пособие

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

Набережные Челны

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

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

Составители: Смирнов Ю.Н., Шибанова Е.В.

Набережные Челны: Изд-во КамПИ, 2004, 81 с.

Рецензент: доцент, кандидат физико-математических наук Углов А.Н.

Печатается по решению научно-методического совета Камского государственного политехнического института от 24.03.03 г.

Камский Государственный

Политехнический Институт,

Содержание

Содержание. 3

Введение. 4

1. Примеры задач линейного программирования. 5

2. Общая, стандартная и основная задачи линейного программирования 8

3. Геометрическая интерпретация задачи линейного программирования 11

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

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

6. Двойственные задачи линейного программирования. 32

7. Двойственный симплекс-метод. 42

8. Задача целочисленного линейного программирования. 45

9. Транспортная задача. 51

10. Задачи производственного менеджмента. 69

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

Варианты задач для самостоятельной работы.. 74

Литература. 81

Введение

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

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

В зависимости от свойств функции f и задачи математического программирования делятся на ряд классов задач. Далеко неполная схема задач математического программирования приведена на рис.1.

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

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

Выпуклое программирование – если отыскивается минимум выпуклой (максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

Целочисленное программирование – если проектные параметры могут принимать лишь целочисленные значения.

Дробно-линейное программирование – если целевая функция f – квадратичная, - линейные.

Параметрическое программирование – если функции f и зависят от некоторых параметров.

Стохастическое программирование – если в функциях f и содержаться случайные величины.

Динамическое программирование – если процесс нахождения решения является многоэтапным.

Рассмотрим задачи, сводящиеся к задачам линейного программирования.

1. Примеры задач линейного программирования

Задача использования ресурсов.

Для производства n видов продукции предприятие использует m видов ресурсов (сырья). Известны нормы затрат ресурсов для производства единицы продукции каждого вида: - норма затрат i – ого ресурса для производства единицы продукции j – ого вида.

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

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

Обозначим через план производства каждого вида продукции.

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

при линейных ограничениях

(ограничения на ресурсы);

(условие неотрицательности плана производства).

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

Замечания:

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

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

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

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

Таким образом, процесс математического моделирования реальных задач сводится к все большему учету реальных факторов. Эти факторы оказываются связывающими различные деловые процессы предприятия. В нашем случае оказались связанными задачи таких деловых процессов, как, ПРОИЗВОДСТВО, МАРКЕТИНГ, МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ, СБЫТ, ФИНАНСЫ.

Банковская задача

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

Предположим, банк имеет свободных средств в размере 120 млн. рублей. Выданные кредиты или обязательства банка по кредитам составляют не менее 30 млн. рублей. Исходя из стратегии (безопасности) банка, не менее чем 40% всех используемых средств должны находиться в ценных бумагах (в ликвидных ресурсах, для выполнения возможных непрогнозируемых обязательств). Определить оптимальный план использования средств, если доход от выданных кредитов составляет в среднем - 20%, а от ценных бумаг – 10%.

Экономико-математическая модель задачи:

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

Найти максимум линейной целевой функции – функции дохода

при заданных ограничениях по свободным средствам, по объему выдаваемых кредитов и по стратегии банка

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

2. Общая, стандартная и основная задачи линейного программирования

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

(1) при условиях

, (2)

, (3)

, , (4),

где , , - заданные постоянные величины и .

Определение.2. Функция Z называется целевой функцией задачи (1 - 4), - проектными параметрами задачи, а условия (2 - 4) ограничениями данной задачи.

Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m, l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют:

,

, .

Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n, m<n,т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют:

,

, , .

Определение 5. Совокупность значений проектных параметров , удовлетворяющих ограничениям задачи (2-4), называется допустимым решением, или планом.

Определение 6. План , при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называется оптимальным, т.е. .

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

1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку .

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

Ограничение-неравенство вида преобразуется в ограничение-равенство , , а ограничение-неравенство вида - в ограничение-равенство , .

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

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

4. Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .

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

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

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

(5) при условиях

, (6)

, (7).

Эта задача ЛП в стандартной форме с двумя переменными.

Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми

(8).

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

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

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

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

Рассмотрим градиент функции цели . Это будет вектор (см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую - const, то её движение параллельно самой себе в направлении вектора приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямой на рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

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

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

,

, .

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

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

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

3. Находят многоугольник решений как пересечение всех полуплоскостей

4. Строят начальную прямую (линию уровня целевой функции), проходящую через начало координат .

5. Строят вектор , представляемый градиент целевой функции (5).

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

7. Определяют координаты точки максимума (минимума) целевой функции и вычисляют ее значение в этих точках.

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

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

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

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

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

5. Движением прямой параллельно самой себе в направлении вектора находим два крайних положения. Первое соответствует минимуму целевой функции (точка А), второе - максимуму (точка С).

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

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

- Точка минимума лежит на пересечении прямых и :

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

Максимальное значение целевой функции .

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

Действительно, пусть поставлена каноническая задача ЛП: найти наибольшее значение

(12) при условиях

, (13),

, (14),

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

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

,

, . (15)

Учитывая неравенства (14), эту систему уравнений можно записать в виде системы неравенств , , , . Исключая из (12) при помощи уравнений (15), получим , т.е. задачу вида (5-7).

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

Введение.

Предположим, что поставлена стандартная задача ЛП:

,

, , (16)

, .

Каждое из условий типа неравенства определяет полупространство, ограниченное гиперплоскостью (плоскостью в k -мерном пространстве). Пересечение соответствующих полупространств образует выпуклый многогранник (область допустимых решений - ОДР), в котором необходимо найти максимум (минимум) целевой функции. Внутри многогранника условий в силу его выпуклости линейная функция z не может достигать максимума (минимума). Её максимум (минимум), если он существует, достигается обязательно в какой-нибудь вершине многогранника или на одном из его граней.

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

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

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

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

, , , (17)

, .

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

Определение 7. Решение, при котором все свободные переменные равны нулю, называются базисным решением.

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

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

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

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

Алгоритм симплекс-метода.

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

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

Алгоритм симплекс-метода представлен при помощи блочных структур на рис.7.

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

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

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

,

, , (18)

, .

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

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

,

, , (19)

, , где , , .

Из такой записи канонической задачи ЛП составляют симплекс-таблицу (см. Таб.1).

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

Таб.1. Составление первой симплекс-таблицы

Базисные переменные	Свободные члены	Свободные переменные
	…		…
			…		…
…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…
			…		…
Целевая функция Z			…		…

Нахождение базисного решения. В базисном решении все свободные переменные равны нулю, и поэтому базисные переменные равны свободным членам (см. (19) и Таб.1): .

Проверка допустимости базисного решения.

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

Проверка совместности ограничений. Если базисное решение недопустимо, то необходимое проверить совместность ограничений, т.е. наличие ОДР. Геометрическая интерпретация несовместности ограничений показана на рис.5.

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

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

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

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

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

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

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

Проверка неединственности решения.

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

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

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

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

Шаг 1. Нахождение разрешающего столбца.

ü базисное решение недопустимое, ограничения совместны.

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

ü базисное решение допустимое, неоптимальное.

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

Шаг 2. Нахождение разрешающей строки.

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

Разрешающие строка и столбец в Таб.1 помечены стрелками, разрешающий элемент выделен рамкой.

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

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

Шаг 1. Ячейка разрешающего элемента заполняется значением , обратным значению разрешающего элемента.

Шаг 2. Ячейки разрешающей строки заполняются элементами, стоящими в этих ячейках, деленными на разрешающий элемент, т.е.

, , , . (20)

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

, , , . (21)

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

,

, (22)

, ,

, , , .

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

В результате преобразования получим новую симплекс-таблицу (Таб.2).

Таб.2. Преобразование симплекс-таблицы

Базисные переменные	Свободные члены	Свободные переменные
	…		…
			…		…
…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…
			…		…
Целевая функция Z			…		…

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

Исходную стандартную задачу линейного программирования (СЗЛП) приведем к каноническому виду (КЗЛП). Для этого введем дополнительные переменные, учитывая знаки неравенств-ограничений. Если ограничение-неравенство имеет знак «≥», то дополнительную переменную вводим со знаком «-», в противном случае – со знаком «+».

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

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

Базисные переменные	Свободные члены	Свободные переменные
x1	x2
x3	-9	-3
x4
x5	-18		-4
Z		-6	-1

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

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

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

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

Преобразуем симплекс-таблицу, используя правила преобразования:

1. Ячейку разрешающего элемента, равного «-4», заполняем значением, обратным значению разрешающего элемента (-1/4=-0,25).

2. Ячейки разрешающей строки заполняем элементами, стоящими в этих ячейках, деленными на разрешающий элемент «-4». Например, элемент, находящийся на пересечении столбца свободных членов и строки , будет равен .

3. Ячейки разрешающего столбца заполняем элементами, стоящими в этих ячейках, деленными на разрешающий элемент с обратным знаком «4». В частности, элемент, находящийся на пересечении столбца и строки , будет равен .

4. Остальные ячейки заполняем значениями, стоящими в этих ячейках, минус произведение элементов, стоящих в соответствующем разрешающем столбце и в соответствующей разрешающей строке, деленное на разрешающий элемент «-4». Например, элемент, находящийся на пересечении столбца свободных членов и строки , будет равен .

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

Базисные переменные	Свободные члены	Свободные переменные
x1	x5
x3
x4
x2
Z

Базисное решение - недопустимое, т.к. есть отрицательный элемент (). Ограничения совместны, т.к. в строке с отрицательным свободным членом имеется ещё отрицательный элемент.

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

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

Базисные переменные	Свободные члены	Свободные переменные
x3	x5
x1
x4			1
x2
Z

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

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

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

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

Таб.3. Симплекс-таблица оптимального решения

Базисные переменные	Свободные члены	Свободные переменные
x4	x5
x1
x3
x2
Z

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

Таким образом, наибольшее значение целевая функция имеет при .

6. Двойственные задачи линейного программирования

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

1. Симметричная пара взаимно двойственных задач:

Рассматривается стандартная задача линейного программирования (СЗЛП):

Тогда двойственная ей задача (ДЗЛП) будет иметь вид:

Поиск по сайту: