Решение типового варианта контрольной работы № 7

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

Система ограничений:

1. П

   -

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

1. ;V.

2. ;VI.

3. ;

4. ;

В качестве контрольной точки для установления положения соответствующих полуплоскостей удобно взять точку O(0, 0) – начало координат. Если координаты этой точки удовлетворяют данному неравенству, то и все точки полуплоскости, в которой находится точка О, будут удовлетворять этому неравенству.

Положение прямых и полуплоскостей, а также область допустимых решений Ω (заштрихованная область ABCDEF) представлены на рис. 1.

Рис. 1

2. Построим направление вектора – градиента целевой функции, определяющего направление наискорейшего возрастания целевой функции Z(X):

N=

3. Проведём линию уровня Z₀=C, где С=const. Получим уравнение прямой – множества точек, в которых целевая функцияZ=f() принимает постоянное значение равное С. Сама линия уровня перпендикулярна направлению вектора-градиента.

Пусть С=9, тогда получим линию уровня Z_c=9:

На рис. 1 линия уровня Z_cпоказана пунктирной линией.

4. Для отыскания точки, соответствующей максимальному значению целевой функции, перемещаем линию уровня Z_cпараллельно самой себе в направлении вектора-градиента до тех пор, пока она не будет иметь с областью Ω единственную общую точку или не совпадет с прямой, содержащей одну из сторон многоугольникаABCDEF. В данном случае такой точкой является вершинаD. Найдём координаты точкиDиз системы линейных уравнений как точки пересечения прямыхIиII.

Максимальное значение целевой функции при этом равно:

5. Для отыскания точки, соответствующей минимальному значению целевой функции, перемещаем линию уровня Z_cв направлении, противоположном направлению вектора-градиента. Наиболее удалённой точкой в этом направлении, принадлежащей области Ω, является точка А, координаты которой определяют минимальное значениеZ.

Найдём координаты точки А из системы линейных уравнений как точки пересечения прямых IVиV():A(0; 2).

Выводы.

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

Таблица 6

Ресурсы	Расходы сырья на единицу продукции		Запасы сырья
	2	4	12
	7	2	18
	5	8	48
Цена единицы продукции	3	4

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

Обозначим и– количество единиц продукциии, запланированных к производству.

Система ограничений по запасам сырья будет

, ;.

Целевая функция (прибыль): .

2. Симплексный табличный метод применим только к канонической (основной) форме задачи линейного программирования, поэтому от системы ограничений – неравенств, перейдем к системе ограничений – равенств, введя дополнительные переменные :

.

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

Каноническая форма задачи принимает вид:

,

.

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

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

3. Составим первую симплексную таблицу (табл. 7), внеся в первые три строки коэффициенты перед переменными и свободные члены системы ограничений. Элементами последней (четвертой) строки будут коэффициенты перед переменными целевой функции , представленной в виде равенства .

Таблица 7

Переменные	Основные		Дополнительные			Свободные члены
Базис
	2	4	1	0	0	12
	7	2	0	1	0	18
	5	8	0	0	1	48
Оценки	-3	-4	0	0	0	0

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

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

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

Разделим все элементы разрешающей (первой) строки на 4, чтобы разрешающий элемент столбца был равным 1, а затем исключим переменную из ниже лежащих строк второго столбца. Для этого новые элементы первой строки умножим на –2, –8, +4 и сложим с элементами второй, третьей и четвертой строк соответственно. Получим новую симплексную таблицу 8, в которой переменнаяиз свободных переходит в базисные, а переменнаяиз базисных в свободные.

Таблица 8

Переменные	Основные		Дополнительные			Свободные члены
Базис
		1		0	0	3
	6	0		1	0	12
	1	0	-2	0	1	24
Оценки	-1	0	1	0	0

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

Таблица 9

Переменные	Основные		Дополнительные			Свободные члены
Базис
	0	1			0	2
	1	0			0	2
	0	0	-2		1	22
Оценки	0	0	1		0

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

Оптимальное решение будет иметь видпри этомед.

Выводы:

1. Так как в последней оценочной строке оценки свободных переменных иположительные, то полученное оптимальное решение единственно.

2. Ресурсы вида будут использованы не полностью, и остатоксоставит 22 ед.

3. Доход предприятия при реализации полученного решения составит 14 ед.

Задание 3. По исходным данным рассмотренной ранее задачи (задание 2) и ее оптимальному решению сформулировать двойственную ей задачу, используя основные теоремы двойственности. Найти оптимальное решение двойственной задачи.

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

,

, .

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

,

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

Эта новая задача называется двойственной по отношению к исходной и ее математическая модель имеет вид:

,

2. Используя оптимальное решение исходной задачи, найдем оптимальное решение двойственной.

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

.

Убедимся в этом, найдя оптимальный вектор оценки ресурсов .

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

и по формулам :;.

Исходная задача:

(1)

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

(2)

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

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

Таблица 10

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

Учитывая данные таблицы 10 для оптимального решения двойственной задачи, систему (2) запишем в виде:

, .

Решая эту систему, найдем .

Таким образом, вектор оценки ресурсов .

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

Убеждаемся, что условных единиц.

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

Установим, как меняется функция оценки ресурсов при увеличении расхода сырья на единицу. Если сырья видавзять не 12, а 13=12+1, то, т. е. оценка ресурсов увеличивается на величину двойственной оценки этого ресурса. Аналогично, увеличение на единицу количества сырья видаприведет к увеличениюна. Увеличение же на единицу количества сырьяне отразиться на значении этой функции, т. к. согласно полученного решения.

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

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

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

Замечание : Более общий пример планирования производства изложен в методических указаниях №2343.

Задание 4. Исходные данные транспортной задачи в матричной постановке представлены в табл. 11. В ней приведены станции отправленияА_i() и имеющиеся на них однородные запасы грузаа_i, потребности в грузеb_jна станциях назначенияB_j, а также стоимость перевозки единицы грузаc_ij(тариф). Необходимо спланировать матрицу перевозок Х так, чтобы общая сумма транспортных расходовZ(X) была минимальной.

Таблица 11

Станции назн. Станции отпр.		Потребители				Запасы аi
		B1	B2	B3	B4
Отправи- тели	А1	10	3	6	8	130
	А2	7	1	2	5	90
	А3	4	8	4	1	100
Потребности bj		110	80	60	70

1. Построение допустимого плана перевозок

диагональным методом

Составить план перевозок (построить опорное решение) означает найти количество груза x_ij , отправляемого со станции отправленияА_iк потребителю на станцию назначенияB_j.

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

1. Распределительную таблицу (табл. 12) начинаем заполнять с левой верхней клетки (11). Потребности В₁удовлетворены полностью, поэтому оставшиеся клетки первого столбца (21) и (31) больше не заполняются, т.е. остаются свободными. Эти клетки можно прочеркнуть (проставить в них черточки).

2. Заполняем клетку (12), т. к. у А₂имеется остаток груза в количестве 20 ед.запас продукта у А₂исчерпан, прочёркиваем оставшиеся клетки (13) и (14) первой строки.

3. Заполняем клетку (22). . Потребности в грузе В₂удовлетворены полностью, прочёркиваем клетку (32). Переходим к заполнению соседней клетки.

4. Клетка (23), Возможности отправителя А₂использованы полностью, прочёркиваем оставшуюся свободную клетку этой строки (24).

5. Клетка (33), .

6. Последней заполняется клетка (34).

Последовательность ходов в табл. 12 показана стрелками.

Таблица 12

	B1	B2	B3	B4	ai
A1	110	20			130
A2		60	30		90
A3			30	70	100
bj	110	80	60	70

Матрица перевозок (опорный план) имеет вид:

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

Невырожденный опорный план рассматриваемой задачи должен содержать (m + n – 1) положительных компонент x_ij (базисных переменных), а остальные равны нулю.

Имеем m+n– 1 = 3 + 4 – 1 = 6. Число занятых клеток (элементов, отличных от нуля, матрицы перевозок) равно 6. Следовательно, полученный план перевозокявляется невырожденным.

Может оказаться, что в опорном плане число занятых клеток в распределительной таблице будет меньше, чем (m+n-1). Такая задача называетсявырожденной. Тогда в свободную клетку (которой обычно соответствует наименьший тариф) заноситсябазисный нульи клетка считаетсязанятой нулевой нагрузкой.Однако, занятые клетки не должны между собой образовыватьциклы.

Общая стоимость по этому плану

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

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

1) Заполним клетки (22) и (34), имеющие наименьший тариф, равный единице: Потребности в грузе потребителей В₂и В₄удовлетворены полностью, прочеркиваем оставшиеся свободные клетки второго и четвёртого столбцов распределительной таблицы (табл. 13).

2) Клетка (23), С₂₃=2.. Возможности отправителя А₂исчерпаны, прочёркиваем свободные клетки второй строки.

3) Клетка (31), С₃₁=4.. Возможности поставщика А₃исчерпаны, прочёркиваем клетку (33).

4) Заполняем клетку (13). . Потребности В₃полностью удовлетворены.

5) Последней заполняем клетку (11) с наибольшим тарифом С₁₁=10.

Таблица 13

B Aij	B1	B2	B3	B4	ai
A1	8010	3	6	8	130
A2	7	801	102	5	90
A3	4	8	4	701	100
bj	110	80	60	70

Матрица перевозок этого опорного плана:

Полученный план перевозок является невырожденным, т. к. число занятых клеток совпадает с числом m+n– 1 = 6.

Общая стоимость перевозок

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

3. Проверка опорного плана на оптимальность методом потенциалов

1. Каждому поставщику А_i(i=) ставим в соответствие потенциалu_i , а каждому получателю В_j(j=) – потенциалv_j(табл. 14). Каждой занятой клетке в распределительной таблице соответствует разность потенциаловv_ju_i, равная тарифу этой клетки, т. е.

v_ju_i=c_ij(дляx_ij).

Таблица 14

	v1	v2	v3	v4
u1	8010	3	506	8
u2	7	801	102	5
u3	304	8	4	701

Для занятых клеток составляем систему равенств:

Полагая один из потенциалов равным нулю, например = 0, получим:

.

2. После нахождения потенциалов для каждой свободной клетки (x_ij ) находим оценки= c_ij.

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

Для свободных клеток (табл. 11) получим:

Оценка , следовательно допустимый план перевозок Х₂, полученный методом минимальной стоимости (минимального тарифа) табл. 14, не является оптимальным.

Для клетки (12) строим цикл с загруженными клетками (13), (22) и (23). Вершинам этого цикла условно приписываем знаки: свободной клетке +, следующей по часовой или против часовой занятой клетке – (минус), следующей снова +, затем –. Из поставок в клетках с отрицательными вершинами выбираем наименьшее количество груза , которое прибавляем к поставкам с положительными вершинами и вычитаем из поставок в клетках с отрицательными вершинами. Баланс цикла при этом не нарушается (см. приведенную схему).

(12) (13) (12) (13)

⁺

^-50

^-80

⁺10

30

50

60

(22) (23) (22) (23)

Свободной незагруженной клеткой становится клетка (13). Полученный новый план Х₃ вновь проверяем на оптимальность (табл. 15).

Таблица 15

	v1	v2	v3	v4
u1	8010	3	6	8
u2	7	301	602	5
u3	304	8	4	701

Для занятых клеток имеем:

.

Примем =0, тогда получим следующие значения потенциалов:

Для свободных клеток таблицы находим оценки

Полученный план перевозок Х₃вновь оказался неоптимальным, т. к. оценка клетки (21) оказалась отрицательной.

По этому плану Z(X₃)=10∙80+3∙50+1∙30+2∙60+4∙30+1∙70=1290 у.ед.

Загружаем эту клетку, создав цикл с занятыми клетками (11), (12) и (22). Клетка (22) становится свободной.

(11) (12) (11) (12)

⁺50

⁺

^-30

30

80

50

(21) (22) (21) (22)

Таблица 16

	v1	v2	v3	v4
u1	5010	3	6	8
u2	7	1	602	5
u3	304	8	4	701

Проверяем полученный план Х₄на оптимальность. Для занятых клеток (табл. 16) получим:

Полагая получим:

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

Матрица перевозок этого плана имеет вид:

Х₄=

Выводы:Путём улучшения опорного плана, полученного методом минимальной стоимости, найден оптимальный план Х₄ , стоимость затрат на перевозки при котором является наименьшей и составитZ(X₄)=10∙50+3∙80+7∙30+2∙60+4∙30+1∙70=1260 у.ед.