Глава 1. Линейное программирование

Содержание

Введение
Глава 1 Линейное программирование
Глава 2 Транспортная задача
Глава 3 Специальные разделы математического программирования
Целочисленное програмирование
Параметрическое программирование
Нелинейное программирование
Глава 4 Динамическое программирование
Задача оптимального распраделения инвестиций
Задача выбора оптимальной стратегии эксплуатации оборудования
Задача выбора оптимального маршрута перевозки грузов
Задача построения оптимальной последовательности операций в коммерческой деятельности
Задача о прокладке пути между двумя пунктами
Задача о выборе траектории движения
Литература

Введение

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

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

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

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

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

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

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

Глава 1. Линейное программирование

Упражнение 1.Составьте математическую модель исходной задачи и найдите ее оптимальный план графическим методом. Составьте экономико-математическую модель двойственной задачи и найдите ее оптимальный план, воспользовавшись формулой .

Малое предприятие в течение планового периода выпускает два вида продукции: табуретки и стулья. При их производстве используются три вида ресурсов. Данные по их расходу на выпуск одного изделия и запасы ресурсов приведены в таблице 1.

Таблица 1

Ресурсы	Изделия	Запас ресурса
табуретка	стул
дерево, м3	0,02	0,1	4
гвозди, кг	0,1	0,05	7
обивка, м2	0,3	0,3	24

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

Решение. Выберем в качестве параметров, характеризующих процесс планирования производства продукции, число выпускаемых табуреток (переменная x₁) и выпускаемых стульев (переменная x₂). Выразим через выбранные неизвестные суммарную прибыль от реализации всей продукции. Она включает в себя прибыль от реализации всех табуреток (40x₁) и выпускаемых стульев (50x₂). Тогда цель задачи (максимизация прибыли) запишется в виде:

F = 40x₁ + 50x₂ ® max.

Перейдем к формулировке ограничений. Структура всех трех ограничений одинакова:

£

запас ресурса

расход ресурса

Теперь остается выразить полный расход ресурса через выбранные неизвестные x₁ и x₂. Так, расход дерева на выпуск всех табуреток составит 0,02 x₁ м³, а на выпуск всех стульев – 0,1 x₂ м³ (см. первую строку таблицы). В сумме это даст полный расход дерева и ограничение примет вид линейного неравенства: 0,02 x₁ + 0,1 x₂ £ 4. Аналогично запишутся ограничения для остальных видов ресурсов

0,1 x₁ + 0,05 x₂ £ 7,

0,3 x₁ + 0,3 x₂ £ 24.

Объединяя их в систему, получим

Далее, исходя из смысла введенных переменных (число производимых изделий не может быть отрицательным), на них необходимо наложить условия неотрицательности: x₁ ³ 0 и x₂³ 0.

Окончательно выпишем математическую модель задачи в форме задачи линейного программирования (ЗЛП)

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

Рассмотрим неравенство 0,02 x₁ + 0,1 x₂ £ 4. Оно определяет полуплоскость, лежащую по одну сторону от прямой линии 0,02 x₁ + 0,1 x₂ = 4. Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости и подставить в неравенство её координаты. Если неравенство верно, то полуплоскость, в которой лежит данная точка, – искомая. В противном случае нужная полуплоскость лежит по другую сторону от прямой 0,02 x₁ + 0,1 x₂ = 4. Например, возьмём точку (0:0), тогда 0,02·0 + 0,1·0£ 4 – верно.

Аналогичные исследования можно провести и для неравенств 0,1 x₁ + 0,05 x₂ £ 7 и 0,3 x₁ + 0,3 x₂ £ 24. Тогда, с учётом неотрицательности переменных x₁, x₂, получаем заштрихованную область (рис.1).

X*

(1)

(2)

(3)

0 10 20 30 40 50 60 70 x2

x2

Рисунок 1

Известно, что значения целевой функции F = 40x₁ + 50x₂ неограниченно возрастают, если перемещать прямую 40x₁ + 50x₂ = a в направлении её вектора нормали – градиента , и убывают, если перемещать эту прямую в направлении вектора ( ). Оптимальное решение состоит из точек касания последней линии уровня с допустимой областью, то есть X* = (50;30) – оптимальное решение, F_max = 40·50+50·30 = 3500(у.е.).

Итак, для получения прибыли в размере 3500 у.е. необходимо производить 50 табуреток и 30 стульев.

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

Предположим, некоторая организация решила закупить ресурсы (дерево, гвозди и обивку) у малого предприятия, и необходимо установить оптимальные цены на эти ресурсы y₁, y₂, y₃.

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах 4, 7 и 24 единиц по ценам соответственно y₁, y₂, y₃ были минимальны, т. е.

Z = 4y₁ + 7y₂ + 24y₃®min.

С другой стороны, малое предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление одной табуретки расходуется 0,02 м³ дерева, 0,1 кг гвоздей и 0,3 м² обивки по ценам соответственно y₁, y₂, y₃. Поэтому для удовлетворения требования продавца затраты на ресурсы, потребляемые при изготовлении одной табуретки, должны быть не меньше ее цены 40 у.е., т.е.

.

Аналогично, на изготовление одного стула расходуется 0,1 м³ дерева, 0,05 кг гвоздей и 0,3 м² обивки по ценам соответственно . Поэтому для удовлетворения требования продавца затраты на ресурсы, потребляемые при изготовлении одного стула должны быть не менее его цены 50 у.е., т.е.

.

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

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

Найдите такой набор цен (оценок) ресурсов Y = (y₁, y₂, y₃), при котором общие затраты на все ресурсы будут минимальными (целевая функция) при условии, что суммарная цена ресурсов, используемых при производстве одной табуретки и одного стула, будут не меньше прибыли от их реализации (система ограничений).

Оптимальное решение двойственной задачи может быть получено из равенства:

,

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

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

Подставляя найденные компоненты x₁ = 50, x₂ = 30 оптимального плана в систему, находим значения дополнительных переменных, которые выражают остатки ресурсов x₃ = 0, x₄ = 0,5, x₅ = 0. Тогда оптимальное решение примет вид X*(50; 30; 0; 0,5; 0). В этом решении базисными переменными оказались x₁, x₂, x₄, так как они отличны от нуля. Поэтому:

и .

Для матрицы А найдем обратную .

Определитель матрицы:

.

Алгебраические дополнения:

Тогда матрица алгебраических дополнений имеет вид

;

;

– обратная матрица.

Оптимальное решение

.

Y* = (125; 0; 125); Z_min = 3500 у.е.

Контроль: Z_min = 4·125+7·0+24·125 = 3500 (у.е.)

Ответ: X* = (50; 30; 0; 0,5; 0); F_max = 3500 у.е.

Y* = (125; 0; 125); Z_min = 3500 у.е.

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

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

Тип квартир	Тип дома
кирпичный	панельный
Однокомнатные
Двухкомнатные
Трехкомнатные

Плановая себестоимость кирпичного и панельного домов равна соответственно 300 и 500 млн. рублей. Годовой план ввода жилой площади составляет соответственно не менее 1600, 2400, 600 квартир указанных типов. Определите оптимальный план строительства на финансовый год с минимальной себестоимостью.

Упражнение 2. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

Решение.

Решим задачу симплекс-методом. Для этого приведем задачу к каноническому виду:

В каждом уравнении системы присутствует переменная, которая исключена из всех остальных уравнений. Эти переменные можно использовать в качестве базисных для построения I опорного плана. Отметим, что базисные переменные входят в своё уравнение с коэффициентом 1, а свободные члены уравнений системы неотрицательны. Таким образом, x₃, x₄, x₅, x₆ – базисные, x₁, x₂ – свободные переменные.

Внесём данные задачи в симплекс-таблицу. В верхней строке над переменными x₁, x₂, x₃, x₄, x₅, x₆ записаны соответствующие коэффициенты целевой функции; С_б – столбец коэффициентов перед базисными переменными, взятые из верхней строки таблицы; в столбце b_i – свободные члены, а в столбцах x₁, x₂, x₃, x₄, x₅, x₆ – коэффициенты перед этими переменными, взятые из уравнения системы ограничений, в которое входит соответствующая базисная переменная: в F-строку на первом шаге в столбец b_i поставлен «0», а в остальных столбцах – соответствующие коэффициенты целевой функции, взятые с противоположным знаком (табл.2).

Таблица 2

План	Базис	Сб	bi		–5					di
x1	x2	x3	x4	x5	x6
I	x3			–3						4
x4			–1						27/4
x5									31/2
x6				–1					¥
F	=		–1

Базисное решение получаем в виде X = (x₁, x₂, x₃, x₄, x₅, x₆) при свободных переменных равных нулю, а базисных – равных соответствующим свободным членам b_i.

Таким образом, базисным решением на первом шаге будет X₁ = (0; 0; 4; 27; 31; 2) (точка X₁(0; 0) рис. 2), при котором целевая функция будет F равна 0, то есть F₁= 0.

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

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

Чтобы перейти к построению плана II, нужно перевести переменную x₂ в базис. Тогда столбец x₂ – разрешающий столбец. Затем найдём оценочные отношения d_i, для чего поделим элементы столбца свободных членов на соответствующие элементы разрешающего столбца, результат занесём в столбец d_i, учитывая, что

.

В качестве разрешающей строки выбирается строка с наименьшим оценочным отношением d_i. В данном случае это строка, соответствующая базисной переменной x₃, значит именно её исключаем из базиса, то есть базисными во II плане будут x₂, x₄, x₅, x₆.

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

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

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

Разрешающая строка в новой таблице = Текущая разрешающая строка / Разрешающий элемент.

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

Новая строка = Текущая строка – Её коэффициент в разрешающем столбце ´ Разрешающая строка в новой таблице.

В нашем примере:

разрешающая строка в новой таблице:

Строка x₄

Текущая x₄-строка:

–4´Разрешающая строка в новой таблице:

Новая x₄-строка:

Строка x₅

Текущая x₅-строка:

–2´ Разрешающая строка в новой таблице:

Новая x₅-строка:

Строка x₆

Текущая x₆-строка:

–(–1)´ Разрешающая строка в новой таблице:

Новая x₆-строка:

Строка целевой функции F

Текущая F-строка:

–5´ Разрешающая строка в новой таблице:

Новая F-строка:

Новая симплекс-таблица 3, соответствующая плану II, имеет следующий вид.

Таблица 3

План	Базис	Сб	bi		–5					di
x1	x2	x3	x4	x5	x6
II	x2	–5		–3						¥
x4					–4
x5					–2				23/9
x6			–2						¥
F	=	–20			–5

Базисным решением на втором шаге будет X₂ = (0; 4; 0; 11; 23; 6) (точка X₂(0; 4) рис. 2), при котором целевая функция будет F равна –20, то есть F₂= –20.

Для базисного решения X₂ критерий оптимальности не выполнен, так как в столбце, соответствующем свободной переменной x₁, в целевой функции есть положительный элемент (+14).

Чтобы перейти к построению плана III, нужно перевести переменную x₁ в базис. Тогда столбец x₁ – разрешающий столбец. Для определения разрешающей строки заполняем столбец оценочных отношений d_i, и выбираем строку, соответствующую меньшему d_i, то есть строку, которой соответствует базисная переменная x₄. В результате базисными переменными в плане III будут x₁, x₂, x₅, x₆.

Вычисляем элементы новой симплекс-таблицы.

Разрешающая строка в новой таблице x₁ = Текущая разрешающая строка / 11.

Новая x₂-строка = Текущая x₂-строка – (–3) ´ Разр. строка в новой таблице.

Новая x₅-строка = Текущая x₅-строка – 9 ´ Разр. строка в новой таблице.

Новая x₆-строка = Текущая x₆-строка – (–2) ´ Разр. строка в новой таблице.

Новая F-строка = Текущая F-строка – 14 ´ Разр. строка в новой таблице.

Эти вычисления приводят к таблице 4.

Таблица 4

План	Базис	Сб	bi		–5					di
x1	x2	x3	x4	x5	x6
III	x2	–5				–1/11	3/11			¥
x1					–4/11	1/11			¥
x5					14/11	–9/11
x6					3/11	2/11			88/3
F	=	–34			1/11	–14/11

Базисным решением на третьем шаге будет X₃ = (1; 7; 0; 0; 14; 8) (точка X₃(1; 7) рис. 2), при котором целевая функция будет F равна (–34), то есть F₃= –34.

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

Чтобы перейти к построению плана IV, нужно перевести переменную x₃ в базис. Тогда столбец x₃ – разрешающий столбец. Заполняем столбец оценочных отношений d_i, и в качестве разрешающей строки выбираем ту, которой соответствует базисная переменная x₅ (с наименьшим элементом в столбце оценочных отношений), то есть базисными в IV плане будут x₁, x₂, x₃, x₆.

Вычисляем элементы новой симплекс-таблицы.

Разрешающая строка в новой таблице x₃ = Текущая разреш. строка / .

Новая x₂-строка = Текущая x₂-строка – ´ Разр. строка в новой таблице.

Новая x₁-строка = Текущая x₅-строка – ´ Разр. строка в новой таблице.

Новая x₆-строка = Текущая x₆-строка – ´ Разр. строка в новой таблице.

Новая F-строка = Текущая F-строка – ´ Разр. строка в новой таблице.

Эти вычисления приводят к таблице 5.

Таблица 5

План	Базис	Сб	bi		–5
x1	x2	x3	x4	x5	x6
IV	x2	–5					3/14	1/14
x1						–1/7	2/7
x3						–9/14	11/14
x6						5/14	–3/14
F	=	–35				–17/14	–1/14

Базисным решением на четвёртом шаге будет X₄ = (5; 8; 11; 0; 0; 5) (точка X₄(5; 8) рис. 2), при котором целевая функция будет F равна (–35), то есть F₄= –35.

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

Таким образом, X* = (5;8;11;0;0;5), F_min = –35.

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

x2                     X2

0 1 2 3 4 5 6 7 8 x1

X1

X3

X4

Рисунок 2

Рисунок 2

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

Составим расширенную матрицу системы и транспонируем ее.

.

Таким образом, получили двойственную задачу

Установим соответствие между переменными и найдем решение двойственной задачи (см. табл. 6).

Таблица 6

Абсолютные значения коэффициентов при переменных целевой функции исходной задачи, выраженной через свободные переменные её оптимального решения
основные переменные	дополнительные переменные
x1	x2	x3	x4	x5	x6
			17/14	1/14
y5	y6	y1	y2	y3	y4
дополнительные переменные	основные переменные
компоненты оптимального решения двойственной задачи

Y* = (0; 17/14; 1/14; 0; 0; 0); Z* = F* = –35.

Контроль: Z* = –4 · 0 – 27·17/14 – 31·1/14 – 2·0 = –35.

Ответ: X* = (5; 8; 11; 0; 0; 5); F_min = –35.

Y* = (0; 17/14; 1/14; 0; 0; 0 ); Z_max = –35.

Задача 2. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

2.7.

Упражнение 3. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

Решение.

Решим задачу симплекс-методом (подробно этот метод был описан в упражнении 2). Для этого приведем задачу к каноническому виду

Внесём данные задачи в симплекс-таблицу 7.

Таблица 7

План	Базис	Сб	bi					di
x1	x2	x3	x4
I	x3							18
x4
F	=		–2	–1

Базисным решением на первом шаге будет X₁ = (0; 0; 18; 16) (точка X₁(0; 0) рис. 3), при котором целевая функция будет F равна 0, то есть F₁= 0.

Для базисного решения X₁ критерий оптимальности не выполнен, так как в столбцах, соответствующих свободным переменным x₁ и x₂, в целевой функции есть отрицательные элементы (–2 и –1); выбираем из них наименьший.

Чтобы перейти к построению плана II, нужно перевести переменную x₁ в базис. Тогда столбец x₁ – разрешающий столбец. Заполняем столбец оценочных отношений d_i, и в качестве разрешающей строки выбираем ту, которой соответствует базисная переменная x₄ (с наименьшим элементом в столбце оценочных отношений), то есть базисными в плане II будут x₁, x₃.

Вычисляем элементы новой симплекс-таблицы 8.

Таблица 8

План	Базис	Сб	bi					di
x1	x2	x3	x4
II	x3				5/2		–1/2	4
x1				1/2		1/2
F	=

Базисным решением на втором шаге будет X₂ = (8; 0; 10; 0) (точка X₂(8; 0) рис. 3), при котором целевая функция будет F равна 16, то есть F₂= 16.

Так как в F-строке II-го плана симплекс-таблицы все элементы неотрицательны, то этот план является оптимальным. Но он не единственный, так как в F-строке существует нулевой элемент, соответствующий свободной переменной (в данном примере это x₂).

Чтобы найти второй оптимальный план, x₂-столбец примем за разрешающий и перейдем к следующему плану (табл. 9).

Таблица 9

План	Базис	Сб	bi					di
x1	x2	x3	x4
III	x2					2/5	–1/5
x1					–1/5	3/5
F	=

Базисным решением на третьем шаге будет X₃ = (6; 4; 0; 0) (точка X₃(6; 4) рис. 3), при котором целевая функция будет F равна 16, то есть F₃= 16.

Общее решение запишем в виде линейной комбинации оптимальных базисных решений и

.

.

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

X3

X2

0 1 2 3 4 5 6 7 8 x1

x2             X1

Рисунок 3

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

Составим расширенную матрицу системы и транспонируем ее

.

Таким образом, получили двойственную задачу

Таблица 10

Абсолютные значения коэффициентов при переменных целевой функции исходной задачи, выраженной через свободные переменные её оптимального решения
основные переменные	дополнительные переменные
x1	x2	x3	x4
y3	y4	y1	y2
дополнительные переменные	основные переменные
компоненты оптимального решения двойственной задачи

Установим соответствие между переменными и найдем решение двойственной задачи (см. табл. 10).

Y* = (0; 1; 0; 0); Z* = F* = 16.

Контроль: Z* = 18 · 0 + 16·1 = 16.

Ответ: .

Y* = (0; 1; 0; 0); Z_min = 16.

Задача 3. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

3.7.

Упражнение 4. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

Решение.

Решим задачу симплекс-методом (подробно этот метод был описан в упражнении 2). Для этого приведем задачу к каноническому виду

Внесём данные задачи в симплекс-таблицу11.

Таблица 11

План	Базис	Сб	bi					di
x1	x2	x3	x4
I	x3			–2				2
x4				–3			¥
F	=		–2	–3

Базисным решением на первом шаге будет X₁ = (0; 0; 2; 12) (точка X₁(0; 0) рис. 4), при котором целевая функция будет F равна 0, то есть F₁= 0.

Для базисного решения X₁ критерий оптимальности не выполнен, так как в столбцах, соответствующих свободным переменным x₁ и x₂, в целевой функции есть отрицательные элементы (–2 и –3); выбираем из них наименьший.

Чтобы перейти к построению плана II, нужно перевести переменную x₂ в базис. Тогда столбец x₂ – разрешающий столбец. Заполняем столбец оценочных отношений d_i, и в качестве разрешающей строки выбираем ту, которой соответствует базисная переменная x₃ (с наименьшим элементом в столбце оценочных отношений), то есть базисными в II плане будут x₂, x₄.

Вычисляем элементы новой симплекс-таблицы 12.

Таблица 12

План	Базис	Сб	bi					di
x1	x2	x3	x4
II	x2			–2				¥
x4			–2				¥
F	=		–8

Базисным решением на втором шаге будет X₂ = (0; 2; 0; 18) (точка X₂(0; 2) рис. 4), при котором целевая функция будет F равна 6, то есть F₂= 6.

Для базисного решения X₂ критерий оптимальности не выполнен, так как в столбце, соответствующем свободной переменной x₁, в целевой функции есть отрицательный элемент (–8).

Чтобы перейти к построению плана III, нужно перевести переменную x₁ в базис. Тогда столбец x₁ – разрешающий столбец. Заполняем столбец оценочных отношений d_i.

Так как все d_i = ∞, то переменная x₁ может расти неограниченно. А вместе с ней неограниченно возрастет и функция, то есть F* = ¥.

Проиллюстрируем графически процесс решения (рис. 4). Подробно этот метод был описан в упражнении 1.

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

x1

x2

X1

X2

(1)

(2)

Рисунок 4

Составим расширенную матрицу и транспонируем ее:

.

Таким образом, получили двойственную задачу:

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

Ответ: .

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

Задача 4. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

4.7.

Упражнение 5. Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении.

Решение.

Решим задачу симплекс-методом. Для этого приведем задачу к каноническому виду:

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

Поэтому введём в эти уравнения искусственные (не имеющие «экономического» смысла в данной задаче) неотрицательные переменные r₁, r₂, которые в оптимальном решении обязательно станут равными нулю. В целевую функцию добавляем «штраф» (–Mr₁ – Mr₂) за использование искусственных переменных (в случае минимизации целевой функции добавляется штраф Mr₁ + Mr₂), где M ³ 0.

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

Очевидно, что в такой задаче переменные r₁, x₄, r₂ можно использовать в качестве базисных.

Решим модифицированную задачу симплекс-методом (подробно этот метод был описан в задаче 2.31). Единственным отличием является наличие M-строки, которая вычисляется по формуле:

Новая (F+M)-строка = Исходная F-строка – M·r₁-строка – M r₂-строка.

Выполним операцию в данном примере:

Исходная F -строка:

M·r₁-строка:

M·r₂-строка:

Новая (F+M)-строка:

Внесём данные задачи в симплекс-таблицу 13.

Таблица 13

План	Базис	Сб	bi						–M	–M	di
x1	x2	x3	x4	x5	r1	r2
I	r1	–M				–1					2
x4
r2	–M		–1				–1			1/2
F	=		–1	–2
M	=	–3		–3

Базисным решением на первом шаге будет X₁ = (0; 0; 0; 2; 0) (точка X₁(0; 0) рис. 5), при котором целевая функция будет F равна 0, то есть F₁= 0.

Базисное решение X₁ не является допустимым, так как в базисе присутствуют искусственные переменные, поэтому критерий оптимальности для F-функции не выполнен. Сначала нужно оптимизировать M-функцию. В этой функции есть отрицательный элемент (–3), а значит M-функция не оптимальна.

Чтобы перейти к построению плана II, нужно перевести переменную x₂ в базис. Тогда столбец x₂ – разрешающий столбец. Заполняем столбец оценочных отношений d_i, и в качестве разрешающей строки выбираем ту, которой соответствует базисная переменная r₂ (с наименьшим элементом в столбце оценочных отношений), то есть базисными в II плане будут r₁, x₄, x₂.

Отметим, что уже первая итерация исключила из базисного решения искусственную переменную r₂, что является результатом частичного включения «штрафа» в целевую функцию. Это позволяет в дальнейшем не учитывать переменную r₂ в симплекс-таблице.

Вычисляем элементы новой симплекс-таблицы 14.

Таблица 14

План	Базис	Сб	bi						–M	–M	di
x1	x2	x3	x4	x5	r1	r2
II	r1	–M	3/2	3/2		–1		1/2		–1/2	1
x4		3/2	1/2				1/2		–1/2
x2		1/2	–1/2				–1/2		1/2	¥
F	=		–2				–1
M	=	–3/2	–3/2				–1/2		3/2

Базисным решением на втором шаге будет X₂ = (0; 1/2; 0; 3/2; 0) (точка X₂(0; 1/2) рис. 5), при котором целевая функция будет F равна 1, то есть F₂= 1.

Базисное решение X₂ всё ещё не является допустимым. Поэтому продолжаем оптимизировать M-функцию. В столбцах, соответствующих свободным переменным x₁ и x₅, в M-функции есть отрицательные элементы
(–3/2 и –1/2); выбираем из них наименьший.

Чтобы перейти к построению плана III, нужно перевести переменную x₁ в базис. Тогда столбец x₁ – разрешающий столбец. Заполняем столбец оценочных отношений d_i, и в качестве разрешающей строки выбираем ту, которой соответствует базисная переменная r₁ (с наименьшим элементом в столбце оценочных отношений), то есть базисными в плане III будут x₁, x₄, x₂.

Отметим, что вторая итерация исключила из базисного решения и вторую искусственную переменную r₁, что приводит к полному включению штрафа в целевую функцию и получению допустимого решения X₃. Это позволяет в дальнейшем не учитывать переменную r₁ и M-функцию в симплекс-таблице.

Вычисляем элементы новой симплекс-таблицы 15.

Таблица 15