Задание 4. Исходные данные транспортной задачи о перевозках однородных грузов представлены по вариантам в соответствующих таблицах 4 и 5

Исходные данные транспортной задачи о перевозках однородных грузов представлены по вариантам в соответствующих таблицах 4 и 5. В них указаны запасы грузов a_i на станциях отправления, отправители A_i (i= ) и потребности в грузах b_j на станциях назначения, потребители B_j (j= ), а также тариф, то есть стоимость перевозки единицы груза C_ij из i -го пункта отправления в j -ый пункт назначения. Требуется спланировать перевозки так, чтобы общая сумма транспортных расходов была минимальной. Решение задачи провести в матричной постановке. Для этого необходимо:

1. Построить опорное (базисное) решение «диагональным» методом (методом «северо-западного угла») и методом «минимальной стоимости» («минимального тарифа»);

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

3. Сделать соответствующие выводы.

Таблица 4

Таблица 5

Вариант	4.1	4.2	4.3	4.4	4.5	4.6	4.7	4.8	4.9	4.10	4.11	4.12	4.13	4.14	4.15

Вариант	4.16	4.17	4.18	4.19	4.20	4.21	4.22	4.23	4.24	4.25	4.26	4.27	4.28	4.29	4.30

РЕШЕНИЕ ТИПОВОГО ВАРИАНТА КОНТРОЛЬНОЙ РАБОТЫ № 7

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

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

1.

-

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

I. ; V.

II. ; VI.

III. ;

IV. ;

В качестве контрольной точки для установления положения соответствующих полуплоскостей удобно взять точку 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

Ресурсы	Расходы сырья на единицу продукции	Запасы сырья
Цена единицы продукции

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

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

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

, ; .

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

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

.

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

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

,

.

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

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

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

Таблица 7

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

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

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

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

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

Таблица 8

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

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

Таблица 9

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

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

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

Выводы:

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
А2
А3
Потребности bj

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
A2		60	30
A3			30
bj

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

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

Невырожденный опорный план рассматриваемой задачи должен содержать (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
A2	7	801	102	5
A3	4	8	4	701
bj

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

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

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

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

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

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

v_j u_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) получим: