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

Пример.

Найти максимальное значение функции при условиях

Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

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

(50)

при условиях

(51)

(52)

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

(53)

при условиях

(54)

(55)

Выбрав в качестве базиса векторы и, составим симплексную таблицу (табл. 16) для исходной задачи (50) – (52).

Таблица 16

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–4 –6	–1 –1	–2

Из этой таблицы видим, что планом двойственной задачи (50) – (52) является. При этом плане Так как в столбце вектора Р ₀ таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р ₄и Р ₅ имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р ₀. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р ₅. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

Значит, в базис вводим вектор P ₂. Переходим к новой симплекс–таблице (табл. 17).

Таблица 17

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 2		–7	1/2 –3/2 1/2 1/2				1/2 1/2 –1/2 1/2

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

Так как в столбце вектора Р ₀ таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).

Таблица 18

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 1 p 2		8/3 14/3 2/3 32/3				1/3 –2/3 1/3 1/3	2/3 –1/3 –1/3 2/3

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

Найти максимальное значение функции при условиях

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

Взяв в качестве базиса векторы Р ₃, Р ₄ и Р ₅, составляем симплекс-таблицу (табл. 19).

Таблица 19

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–12 –18	–3	–1

В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р ₀ не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р ₅и введем в базис вектор Р ₁. В результате получим псевдоплан X=(6;0;-24;4)

Таблица 20

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 1		–24		1/3 8/3 –2/3			2/3 1/3 –1/3

Так как в строке вектора Р ₃ нет отрицательных чисел, то исходная задача не имеет решения.

ТЕМА 1.4 ТРАНСПОРТНАЯ ЗАДАЧА.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j– м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(56)

при условиях

(57)

(58)

(59)

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

Определение 1.15 Всякое неотрицательное решение систем линейных уравнений (57) и (58), определяемое матрицей, называется планом транспортной задачи.

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

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

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

(60)

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

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

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (60).

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

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (57) и (58) равно п+т. Так как мы предполагаем, что выполняется условие (60), то число линейно независимых уравнений равно п+т– 1. Следовательно, опорный план транспортной задачи может иметь не более п + т– 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п+т– 1, то план является невырожденным, а если меньше – то вырожденным.

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

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

Дата добавления: 2014-01-15