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

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

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

Оформим исходные данные в виде таблицы – см. табл.1

Таблица 1

Сырьевые базы	Предприятия	Возможности сырьевых баз
	…		…
		…		…
…	…	…	…	…	…	…
		…		…
…	…	…	…	…	…	…
		…		…
Потребности предприятий в сырье		…		…

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

. (1)

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

(2)

и, кроме того, имеются ограничения на возможности сырьевых баз:

. (3)

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

Таким образом, получим следующую математическую модель

(4)

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

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

Различные случаи могут возникнуть в зависимости от соотношения требуемого и добываемого количества сырья.

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

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

Случай 2. Суммарные возможности сырьевых баз в точности совпадают с суммарными потребностями предприятий: . В этом случае говорят, что транспортная задача сбалансирована. Специальные методы решения транспортных задач ориентированы именно на этот случай. В этом случае, как нетрудно видеть, задача (4) имеет решение и неравенства (3) должны выполняться как равенства: , иначе предприятия недополучат сырья. Заметим, что в системе уравнений сбалансированной модели одно из уравнений (любое) «лишнее» – оно линейно зависит от остальных, ранг системы равен . (Убедитесь в этом самостоятельно).

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

Решение транспортной задачи, также как и решение задачи симплекс-методом, состоит из двух этапов: 1) определение начального (допустимого) плана и 2) нахождение оптимального плана путем последовательного улучшения текущих планов. Рассмотрим эти этапы на примере решения конкретной транспортной задачи.

Пример

Песок для двух домостроительных комбинатов А и В берется из трех карьеров. Первому комбинату требуется 40 тонн песка в день, второму - 30 тонн. В карьерах №№1, 2, 3 добывается соответственно 20т, 30т и 20т песка в день. Расстояния от карьеров до ДСК А и В равны соответственно (в км): 10, 20, 8 и 15, 17, 12. Затраты на перевозку песка пропорциональны расстоянию и массе груза. Найти наиболее дешевый способ перевозки песка.

Решение

Представим исходные данные в табличной форме – см. табл.2.

Таблица 2

Очевидно, данная задача сбалансирована: 40+30 = 20+20+30. Обозначим через массу перевозимого песка из карьера с номером на комбинат А (при ) или на комбинат В (при ). Поскольку затраты на перевозку песка пропорциональны расстоянию и массе песка, то они пропорциональны произведению расстояния на массу. Таким образом, целевая функция будет иметь вид:

.

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

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

(5)

4.8.2. Определение начального плана. Итак, займемся нахождением какого-нибудь допустимого плана перевозок. Разработано несколько методов определения начального плана: метод «северо-западного» угла, минимального элемента, Фогеля и др. (см., например, [Хазанова], [ ]). Все они основаны на определенном способе последовательного заполнения таблицы типа 1 (2) начальными данными – количеством перевозимого сырья из соответствующей сырьевой базы в соответствующее предприятие. Различаются они способом определения начальной клетки, с которой начинается заполнение таблицы. Более сложные методы определения начального заполнения, как правило, сокращают число итераций на втором шаге – нахождения оптимального решения. Поскольку в настоящее время любые задачи линейного программирования легко решаются на компьютере, целью нашего рассмотрения является показ принципов отыскания решения задачи. Поэтому остановимся на простейшем методе – методе «северо-западного угла».

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

Принцип заполнения клеток простой и естественный. В первую заполняемую клетку () заносим минимум из двух значений: , т.е. пытаемся максимально удовлетворить нужды первого ДСК за счет первого карьера (больше, чем нужно первому ДСК, мы брать не будем, а больше, чем добывается в первом карьере, мы взять не сможем). Итак, в клетку следует поставить т - см. табл.3.

Таблица 3

Как видно из таблицы, в данном случае возможности карьера №1 исчерпаны. Поэтому недостаток сырья нужно взять из другого карьера – возьмем из первого попавшегося при движении по таблице вниз, т.е. из второго. Недостаток песка составляет 40–20 = 20т. Все это количество можно получить из второго карьера. Ставим в клетку число, равное минимуму из недостающего количества сырья и возможности сырьевой базы: т – см. табл.4.

Таблица 4

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
Потребности комбинатов

Как мы видим, потребности ДСК А удовлетворены, а возможности карьера №2 еще не исчерпаны. Используем оставшийся в карьере №2 песок для нужд следующего по порядку ДСК – ДСК В. Опять же мы можем взять минимум из оставшегося в карьере песка (30–20 = 10т) и потребностей комбината, т.е. . Поместим это число в клетку – см. табл.5.

Таблица 5

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
	20
Потребности комбинатов

Мы видим, что возможности карьера №2 исчерпаны, а потребности ДСК В – нет, не хватает еще 30–10 = 20т песка. Возьмем требуемый песок в карьере №3, т.е. поместим число 20 в клетку - см. табл.6.

Таблица 6

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
	20	10
Потребности комбинатов

Тем самым построение начального (допустимого) плана закончено. В обозначениях задачи (5) имеем: Значение целевой функции при таком начальном плане равно: .

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

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

Таблица 7

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
	20	0
Потребности комбинатов

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

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

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

и . (6)

Величина называется псевдостоимостью перевозки единицы груза [Вентцель] (косвенными затратами [Хазанова]). Из (6) следует, что и суммарная псевдостоимость всех перевозок не зависит от плана перевозок:

(7)

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

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

В то же время, если во всех незаполненных клетках имеют место неравенства , то данный план перевозок является оптимальным (см., например, [Вентцель]).

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

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

Таблица 8

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
	20
Потребности комбинатов

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

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

Таблица 9

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20	– 8
	20
Потребности комбинатов

Как видно из табл.9, только одна незаполненная клетка имеет положительную разность . Это клетка (). Если клеток с одинаковой максимальной разностью несколько, можно выбирать любую.

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

Таблица 10

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	– 20	+ – 8
	20	10
	+	– 20
Потребности комбинатов

По этому циклу будем осуществлять перераспределение груза, предназначенного для перевозки. В незаполненную клетку ставим знак «+», а в остальные узлы цикла поочередно ставим знаки «–» и «+». Знак «+» означает, что в клетку будет добавлено некоторое количество груза, а «–» – что убавлено.

Из клеток со знаком «–» выбираем ту, в которой записано наименьшее количество груза (большее количество перераспределить мы не можем, поскольку в некоторых клетках оказалось бы отрицательное количество груза, что невозможно перевезти). В нашем случае обе клетки и имеют одинаковое значение 20. Это количество груза перераспределяем по циклу. Тем самым мы добиваемся того, что груз перемещается из «более дорогой» клетки в «более дешевую». Например, в клетке перевозка единицы груза стоит 20, а в клетке – стоит 17.

Итак, из клеток со знаком «–» вычтем 20 единиц груза, а в клетки со знаком «+» добавим такое же количество. Баланс (выполнение ограничений задачи) при этом, очевидно, сохранится – см. табл.11. При этом клетки и становятся пустыми, а клетка – заполненной. Однако мы должны сохранить количество незаполненных клеток. Поэтому одну из пустых клеток заполним нулем. Проверим, действительно ли значение целевой функции уменьшилось: , что меньше первоначального значения.

Таблица 11

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20
	0
Потребности комбинатов

Далее нужно повторить все шаги с новым заполнением таблицы: пересчитать потенциалы, оценить оптимальность плана перевозок и, в случае неоптимальности, сделать перераспределение перевозок.

Итак, пересчитаем потенциалы и разности – см. табл.12.

Таблица 12

Карьеры	Домостроительные комбинаты	Объемы добычи
А	В
	20	–8
	0	30
		–7		–2
Потребности комбинатов

Из табл.12 видно, что во всех пустых клетках значение разностей отрицательны. Значит найденный план перевозок оптимальный.

Таким образом, решение имеет вид:

4.9. Компьютерная реализация решения задач линейного программирования. Как уже отмечалось,в настоящее время методы решения задач линейного программирования имеют компьютерную реализацию, включенную во многие широко распространенные стандартные и специальные программные системы, в частности в состав программы Microsoft Excel. Для решения задачи линейного программирования с помощью Microsoft Excel она может быть записана в любом виде: стандартном, каноническом, общем. Достаточно лишь задать исходные данные: формулу для вычисления целевой функции и ограничения. Система выдает результат в виде оптимального набора значений переменных и оптимального значения целевой функции, а также некоторые данные о чувствительности решения к изменениям параметров.

Рассмотрим, как это делается в системе Microsoft Excel 2000 на примере следующей задачи:

Имеется 3 вида продуктов питания А, В и С, которые можно купить по ценам $8, $10 и $10 за килограмм. В одном килограмме продукта А содержится 50 г питательного вещества М и 100 г питательного вещества N. Для продукта В соответствующие цифры составляют 100 и 50, для продукта С – 100 и 100. Сколько требуется закупить продуктов А, В и С, чтобы общее количество питательных веществ М и N составляло не менее 4 кг и 5 кг соответственно, а расходы были минимальны? Вычислить также минимальные расходы.

Математическая модель задачи имеет следующий вид:

Программа Microsoft Excel 2000 допускает множество вариантов оформления и манипулирования в процессе решения подобного рода задач. Для решения рассматриваемой задачи можно предложить, например, следующую последовательность действий.

4.9.1. Загрузка программы Microsoft Excel 2000. После загрузки программы на экране монитора появится диалоговое окно, рабочее поле которого представлено в виде таблицы – см. рис.1.

4.9.2. Запись исходных данные задачи. Для удобства ориентации в том, какие данные хранятся в ячейках таблицы, целесообразно в соседних ячейках таблицы (например, сверху) записать условные наименования вводимых данных. Исходные данные задачи можно, например, оформить так, как это показано на рис.2

Рис.2. Оформление исходных данных задачи

В ячейках A1 – D1 записано наименование задачи.

Замечание 1

Для лучшего восприятия текста эти ячейки объединены в одну (последовательность действий: выделить группу объединяемых ячеек, затем выбрать последовательно пункты меню Формат → Ячейки…→ Выравнивание → Объединение ячеек → ОК) и текст выровнен по центру объединенной ячейки (последовательность действий: выделить ячейку, затем выбрать последовательно пункты меню Формат → Ячейки…→ Выравнивание → по горизонтали → по центру → ОК).

В ячейках A2 – D2 записан заголовок «Целевая функция».

В ячейках A3 – D3 записаны имена (обозначения) коэффициентов целевой функции и имя самой целевой функции.

Замечание 2

Нижний индекс можно записать, выбрав перед его записью пункты меню Формат → Ячейки…→ нижний индекс → ОК или проделав те же манипуляции после его записи в строку и выделения с помощью «мыши».

В ячейках A4 – С4 записаны коэффициенты целевой функции.

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

В ячейках A5 – С5 записан заголовок «Коэффициенты ограничений», а в ячейках A6 – С7 – сами коэффициенты ограничений.

В ячейке D5 записано имя функций, описывающих функциональные ограничения. Ячейки D6 и D7 пока оставляем пустыми. В них впоследствии запишем формулы для вычисления значения функций, описывающих функциональные ограничения.

В ячейке E5 записано имя констант ограничений , а в ячейках E6 и E7 – сами эти константы.

В ячейках А8 – С8 после их объединения записано наименование «Переменные», в ячейках А9 – С9 – их имена: .

Ячейки А10 – С10 (ограничены жирной линией) предназначены для записи значений переменных. Эти значения вводить не нужно – их будет записывать программа. После отработки программы в них будут содержаться оптимальные значения этих переменных, а пока они используются как текущие. Начальное значение по умолчанию считается нулевым.

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

В ячейку D4 записывается формула для вычисления значения целевой функции:

=A4*A10+B4*B10+C4*C10

Здесь «=» – обязательный атрибут языка Excel при вводе формулы, «*» – знак умножения в языке Excel, «A4», «A10», «B4», «B10», «C4», «C10» – индексы соответствующих ячеек (буквы можно писать большие или малые – безразлично), воспринимаемые в формуле как содержащиеся в них текущие значения.

Замечание 3

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

·

· установить курсор на пиктограмму и нажать левую клавишу «мыши»; при этом появится диалоговое окно «Мастер функций» - рис.3;

· в левой части окна выделить позицию «Полный алфавитный перечень», а в правой – найти и выделить функцию СУММПРОИЗВ, после чего нажать кнопку ОК1; после этого появится диалоговое окно «СУММПРОИЗВ»; курсор будет находиться в окошке «Массив1» - рис.4.

Рис.3. Диалоговое окно «Мастер функций»

Рис.4. Окно функции СУММПРОИЗВ

· выделить курсором «мыши» ячейки А4 – С4 с коэффициентами целевой функции1 (они окажутся обрамленными штриховой линией, а в окошке «Массив1» появится запись А4:С4;

· поместить курсор в окошко «Массив2» и выделить ячейки А10 – С10 со значениями переменных (по умолчанию вначале эти значения равны нулю); при этом в окошке «Массив2» появится запись А10:С10 – рис.5.

Рис.5. Окно функции СУММПРОИЗВ после выполнения операции умножения векторов

· нажать кнопку ОК; после этого произойдет суммирование произведений коэффициентов целевой функции на соответствующие значения переменных , а в ячейку D4 запишется 0 – значение целевой функции при нулевых значениях аргументов.

В ячейку D6 аналогичным образом запишем формулу, по которой будет вычисляться значение левой части ограничения (2.1):

=A6*A10+B6*B10+C6*C10, (*)

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

=A7*A10+B7*B10+C7*C10,

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

4.9.4. Запуск программы поиска решения. Для запуска программы следует поместить курсор в позицию Сервис строки меню Excel, после чего в выпадающем меню выбрать позицию Поиск решения… - см. рис.6.

После нажатия на левую клавишу «мыши» на экране появится основное диалоговое окно для решения задачи (см. рис.7).

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

1) указание ячейки, содержащей формулу для расчета значения целевой функции;

2) указание направления оптимизации (максимизация или минимизация);

3) указание ячеек, содержащих значения переменных:

4) указание ячеек, содержащих ограничения и связывающих их условий;

5) указание на линейность задачи и неотрицательность переменных.

1. Для указания ячейки с формулой для целевой функции нужно установить курсор «мыши» в поле «Установить целевую ячейку» основного диалогового окна, а затем установить курсор «мыши» в поле D4, где записана формула для вычисления значения целевой функции. При этом в поле «Установить целевую ячейку» появится запись $D$4.

2. Для указания направления оптимизации следует в поле «Равной:» основного диалогового окна установить с помощью «мыши» значение «Минимальному значению».

3. Для указания ячеек, отведенных под значения переменных, следует установить курсор в поле «Изменяя значения», после чего курсором выделить ячейки А10 – С10. При этом в поле «Изменяя значения» появится запись $A$10:$C$10.

4. Для ввода ограничений в поле «Ограничения» нужно нажать клавишу «Добавить» справа от этого поля. Появится диалоговое окно «Добавление ограничения» - см. рис.8.

Затем нужно выделить ячейку D6 с записью левой части ограничения (2.1). В поле «Ссылка на ячейку» появится запись $D$6. В следующем справа поле нужно выбрать из предлагаемого меню (путем нажатия на стрелочку, расположенную справа от поля, и выделения нужной позиции с помощью «мыши») правильный знак (в нашем случае >=). В последнем поле – записать константу ограничения (в нашем случае 4000). Для этого достаточно выделить курсором ячейку с записью константы ограничения (Е6). В соответствующем поле появится запись =$Е$6.

Затем в окне «Добавление ограничения» следует нажать клавишу «Добавить» (при этом все поля в окне очистятся, но введенные ранее значения сохранятся в памяти компьютера) и записать следующее функциональное ограничение (в нашем случае это ограничение (2.2)): выделить ячейку D7 с записью левой части ограничения (2.2). В поле «Ссылка на ячейку» появится новая запись: $FD$7, в следующем справа поле выбрать из предлагаемого меню правильный знак (в нашем случае >=), в последнем поле – записать константу ограничения (в нашем случае 5000) – выделить ячейку с записью константы ограничения (E7).

После этого следует нажать клавишу «ОК» - появится основное диалоговое окно со всеми записанными ограничениями – рис.9.

Замечание. Если необходимо получить решение задачи в целых числах следует добавить соответствующее ограничение. Для этого нужно выделить ячейки для записи переменных (в нашем примере А9 – С9), а во втором поле выбрать условие «цел» (рис.10). Однако в этом случае отчеты по устойчивости и пределам (см. п.4.9.7) получены быть не могут.

5. После описанных в п.п. 1 – 4 действий следует указать на линейность решаемой задачи (это может понадобиться для получения данных для анализа чувствительности к изменению констант ограничений – см. 4.9.7) и на неотрицательность переменных. Для этого в основном диалоговом окне следует нажать на клавишу «Параметры». При этом на экране появится диалоговое окно «Параметры поиска решения», в котором нужно установить галочки («мышью») в полях «Линейная модель» и «Неотрицательные значения» (если они уже не установлены) – рис.11.

После выполнения указанных действий следует нажать клавишу «ОК». При этом вновь появится основное диалоговое окно задачи (рис.7).

4.9.6. Запуск процедуры решения задачи. Для получения решения задачи следует нажать клавишу «Выполнить». Появится исходная таблица, в которой в ячейках А10, В10, С10 будут записаны оптимальные значения переменных соответственно, а в ячейке D4 – оптимальное значение целевой функции и новое диалоговое окно «результаты поиска решения» – рис.12.

4.9.7. Анализ результатов. Если необходимо произвести анализ чувствительности оптимального решения к изменению констант ограничений, следует в основном диалоговом окне в поле «Тип отчета» выделить с помощью «мыши», нажимая и отпуская ее левую клавишу, необходимые позиции, например, все три: «Результаты», «Устойчивость», «Пределы» и нажать клавишу «ОК». При этом диалоговое окно пропадет, а внизу экрана появятся три закладки с надписями «Отчет по результатам 1», «Отчет по устойчивости 1» и «Отчет по пределам 1» – рис.13.

Для ознакомления с указанными отчетами достаточно нажать на соответствующие закладки – см. рис. 14 – 16.

1) Отчет по результатам (рис.14)

Отчет по результатам содержит три таблицы: «Целевая ячейка», «Изменяемые ячейки», «Ограничения».

В заголовке таблицы «Целевая ячейка» в скобках указано направление оптимизации – в данном случае «(Минимум)».

В столбцах таблиц с наименованием «Ячейка» указан адрес ячейки, например $D$4 означает, что ячейка имеет адрес D4.

В столбцах «Имя» занесен текст, записанный над ячейкой, адрес которой указан в данной строке в столбце «Ячейка». Например, в таблице «Целевая ячейка» в столбце «Имя» указан текст «f», записанный в ячейке D3, которая расположена над ячейкой D4, адрес которой указан в первом столбце таблицы. Этот текст интерпретируется как наименование данных, занесенных в ячейку D3, т.е. как значение целевой функции f.

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

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

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

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

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

В столбце «Разница» таблицы «Ограничения» записана разность между константой ограничения и значением функции, описывающей функциональное ограничение, в оптимальной точке, т.е. . Если ограничение активно, то это значение равно нулю, если не активно – положительно.

2) Отчет по устойчивости (рис.15)

Отчет по устойчивости содержит две таблицы: «Изменяемые ячейки» и «Ограничения».

Столбцы «Ячейка» и «Имя» совпадают с соответствующими столбцами таблиц Отчета по результатам.

Таблица «Изменяемые ячейки»

Столбец «Результ. значение» совпадает со столбцом «Результат» аналогичной таблицы Отчета по результатам.

Значения, содержащиеся в столбце «Нормир. стоимость», равны множителю Лагранжа в разложении градиента целевой функции по градиентам функций, описывающих функциональные ограничения, в оптимальной точке, если прямые ограничения записать как функциональные: . Если в найденной оптимальной точке соответствующее значение , значение нормированной стоимости равно нулю. Если же , то указанное значение может быть положительным. Запись «1Е+30»означает (точнее, 10³⁰ – предел возможностей компьютера).

В столбце «Целевой коэффициент» записаны значения заданных коэффициентов целевой функции .

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

Таблица «Ограничения»

Столбец «Результ. значение» совпадает со столбцом «Значение» аналогичной таблицы Отчета по результатам.

В столбце «Теневая цена» указаны значения двойственных переменных – множителей Лагранжа в разложении градиента целевой функции по градиентам функций, описывающих функциональные ограничения, в оптимальной точке. Если ограничение не активно, соответствующий множитель равен нулю.

В столбце «Ограничение Правая часть» указаны константы функциональных ограничений.

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

Замечание. Если в процессе ввода исходных данных задачи в программу поиска решения не сделать отметки о линейности задачи, как указано в 4.9.6 (п.5), вид отчета по устойчивости будет иным: будут отсутствовать столбцы «Допустимое увеличение» и «Допустимое уменьшение», а название столбцов «Нормир. стоимость» и «Теневая цена» заменятся соответственно на «Нормир. градиент» и «Множитель Лагранжа».

2) Отчет по пределам (рис.16)

Отчет по пределам содержит две таблицы: «Целевое» и «Изменяемое».

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

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

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

.

В столбце «Целевое результат» указано значение целевой функции в точке .

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

.

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