2.1. Модуль 1. Оптимизационные методы и модели

Практическое занятие 1

Цель: освоить симплекс-метод, приобрести навыки использования информационных систем управления и управленческого учета для решения задач оптимизации

Задача 1 (Ассортиментная задача)

Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные M₁, М₂, М3 /в ед./.

Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П₁, П₂, П₃ /в ед./.

Расход каждого ресурса на производство единицы продукции является заданной величиной, определяется по рецептуре и обозначается символами а₁₁, a₁₂..., а₃₃, где а - норма расхода, первая подстрочная 1 - номер ресурса, вторая подстрочная 1, 2, 3 - номер ассортиментной группы кон­фет.

Наличие каждого ресурса для производства всех, групп конфет прини­мается как известная величина и обозначается символами в₁, в₂, в₃.

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

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

Поскольку решение задачи заключается в поиске такого плана производ­ства, который обеспечивал бы в принятых условиях наибольший доход, при­нимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: х₁ для M₁; х₂ для М₂; х₃ для М₃.

Экономико-математическая модель в символическом виде.

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

Целевая функция /суммарный доход/ F = = мах

Условия неотрицательности неизвестных

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

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

Решение задачи.

Для решения задачи симплексным методом неравенства преобра­зуются в эквивалентные равенства путем добавления в каждое нера­венство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:

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

Исходная таблица.

сj	p0	x0	28	49	9	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	700	14	28	5	1	0	0
0	x5	630	21	21	5	0	1	0
0	x6	162	6	6	1	0	0	1
Zj - Cj		0	-28	-49	-9	0	0	0

В столбцах таблицы записывают: в первом (С_j) - прибыль единицы продукции, которая вводится в план выпуска; во втором (Р₀) – неизвестные, включаемые в план; в третьем (Х₀) - – свободные величины; в остальных - коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

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

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

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

1-ая итерация

сj	p1	x0	x1	x2	x3	x4	x5	x6
49	x2	25	1/2	1	5/28	1/25	0	0
0	x5	105	21/2	0	5/4	-3/4	1	0
0	x6	12	3	0	-1/14	-3/14	0	1
Zj - Cj		1225	-7/2	0	-1/4	7/4	0	0

Затем элементы столбца x₀ (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отно­шением принимается за ключевую и также для удобства выделяется. В нашем случае 700/I4 = 25, 630/21= 30, 162/6 = 27. Наимень­шее отношение 25 имеет срока х₄, она и будет ключевой. Ключевой элемент 28.

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

В столбцах Р₀ и С_j занимают место вводимая в план неиз­вестная x₂ с прибылью 49 (итерация 1-я). Остальные элемен­ты преобразуются по следующему правилу:

• для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столб­ца;

- соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключе­вой момент;

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

Следуя этому правилу, преобразование элементов столбца х₀ будет:

630 -

162 -

0 -

Включение на первой итерации в план неизвестной х₂ (выпуска продукции П вида) обеспечит сумму прибыли 1225 руб.

Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент - 7/2. Он находится в столбце х₁, который принимается за ключевой, а ключевой строкой будет х₆ (25:1/2=50; 105:21/2=10; 12:3=4). Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу.

2-я итерация

сj	p2	x0	x1	x2	x3	x4	x5	x6
49	x2	23	0	1	4/21	1/14	0	-1/6
0	x5	63	0	0	3/2	0	1	-7/2
28	x1	4	1	0	-1/42	-1/14	0	1/3
Zj - Cj		1239	0	0	-1/3	3/2	0	7/6

В полученном на 2-й итерации плане ключевым столбцом будет х₃, ключевой строкой х₅ (23:4/21=121; 63:3/2=42, при отрицательном элементе отношение не определяется), ключевым элементом 3/2. Элементы ключевой строки преобразуются деле­нием их на ключевой элемент. Остальные элементы преобразуются рассмотренным выше или более упрощенным способом, смысл которого заключается в следующем:

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

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

3-я итерация

сj	p2	x0	x1	x2	x3	x4	x5	x6
49	x2	15	0	1	0	1/14	-8/23	5/18
9	x5	42	0	0	1	0	2/3	-7/3
28	x1	5	1	0	0	-1/14	1/63	5/18
Zj - Cj		1253	0	0	0	3/2	2/9	7/18

Этот новый результат является преобразованным элементом и записывается в новой таблице в том же самом месте. По этому правилу преобразуем элементы столбца х₆. Дня элемента -1/6 в его столбце уже преобразованный элемент ключевой строки в новой таблице -7/3. Этот элемент умножается на еще не преобразованный элемент ключевого столбца 4/21. Полученный результат вычитается из преобразуемого элемента и записывается в новой таблице:

-1/6 - (-7/3 * 4/21) = 5/18

Так же и для двух других элементов:

1/3 – [(-7/3) - (-1/42)] = 5/18; 7/6 – [(-7/3) * (-1/3)] = 7/18

Остальные элементы преобразованы в таком же порядке и записаны в таблицу 3.

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

Как видно из таблицы, оптимальный план предусматривает выпуск продукции П₁ 5 ед. (х₁ = 5), П₂ вида 15 ед. (х₂ = 15), П₁ вида 42 ед. (х₃ = 42). Дополнительные неизвестные в план не вошли, следовательно, х₄ = 0, х₅ = 0, х₆= 0. Подставив значе­ния неизвестных в уравнения, получим:

14*5 + 28*15 + 5*42 + 0 = 700

21*5 + 21*15 + 6*42 + 0 = 630

6*6+ 6*15 + 1*42 + 0 = 162

F = 28*5 + 49*15 + 9*42 = 1253

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

Эта система преобразуется в симплексные уравнения и ре­шается по изложенным правилам.

Проведем анализ оптимального плана.

а) Запасы сырья трех видов используются полностью без остатка, так как х₄ = х₅ = х₆ = 0.

б) Рассмотрим элементы матрицы.

Элементы столбца х₁ свидетельствуют: если запасы муки будут увеличены на I ед. (х₄ = 1), то выпуск продукции II вида увели­чится на 1/14 ед. (х₄ = 15 + 1/14), выпуск продукции III вида не изменится, выпуск продукции I вида уменьшится на 1/14 ед. (5 - 1/14). Сумма прибыли увеличится на 1,5 руб.

Элементы столбца х₅ показывают, что увеличение запасов сахара на I ед. (х₅ = I) позволит увеличить выпуск продукции III вида на 2/3 ед., I вида на 1/63 ед., прибыль на 2/9 руб. и снизить выпуск продукции II вида на 8/23 ед. Изменения объемов производства и суммы прибыли вызовет и увеличение запасов жира (см.столбец х₆). Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.

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

Практическое занятие 2

Цель: освоить методику расчета транспортных задач, научиться решать транспортную задачу в среде Excel

Задача 2 (Транспортная задача)

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

Таблица 2.1

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	4	7	2	3	30
П2	3	1	2	4	190
П3	5	6	3	7	250
Объемы завоза, т	70	120	150	130

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

Для получения исходного плaнa имеющиеся у постaвщи­ков зaпaсы рaспределяются между потребителями с учетом их потребностей.

Способ северо-зaпaдного углa (диaгонaльный). Этот способ состоит в том, что исходный плaн получaется путем рaспреде­ления зaпaсов, нaчинaя с верхнего левого (северо-зaпaдного) углa тaблицы и кончaя прaвым нижним углом ее. Результaты рaспределения покaзaны в тaбл. 2.1.

Первой зaполняется клеткa П₁M₁ . Зaполнение производится с учетом имеющихся зaпaсов у П₁ и потребностей у M₁ . Зaпи­сaв в этой клетке 30 т и удовлетворив этой зaписью часть потребности потребителя М₁ , переходим к следующей клетке П₂М₁. В ней зaписывaется остaток зaвоза 70—30 = 40 т. Тaк кaк зaпaсы у постaвщикa П₂ не кончились, переходим к зaполнению клетки П₂М₂ . Зaпись в этой клетке позволяет зa счет зaпaсов постaвщикa П₂ удовлетворить потребность потребителя М₂ , рaвную 120 т.

После удовлетворения потребностей потребителя М₂ зa счет зaпaсов постaвщикa П₂ полностью частично удовлетворяем потребности потребителя М₃ (зaпись в клетке П₂ Мз – 30 т). Зaпaсы у постaвщикa П₃ позволяют произвести зaписи в клеткaх П₃М₃ (недостaющие у потребителя М₃ - 120 т) и П₃М₄ (полную потребность потребителя М₄ - 130 т). Нa этом рaспределение зaкончено. Оно произведено формaльно с учетом зaпaсов постaвщиков и потребностей потребителей, но без учетa рaсстояний между постaвщикaми и потребителями.

Таблица 2.2

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	30 4	7	2	3	30
П2	40 3	120 1	30 2	4	190
П3	5	6	120 3	130 7	250
Объемы завоза, т	70	120	150	130

Это приводит к тому, что плaны, полученные при тaком рaс­пределении, удовлетворяют всем формaльным требовaниям, но, кaк прaвило, очень дaлеки от оптимaльных. В полученном плaне

F = 30х4 + 40х3 + 120х1 + 30х2 + 120х3 + 130х7 = 1690 т-км

Рaспределение зaпaсов, производимое с учетом рaсстояний между постaвщикaми и потребителями, позволяет получить другие ис­ходные плaны.

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

При рaспределении зaпaсов этим способом исходный плaн, состaвленный по условиям предыдущего примерa, будет иметь уже другой вид (тaбл. 2.3).

Первой рaссмaтривaется строкa П₁. Минимальное рaсстояние по этой строке в клетке П₁М₃. В эту клетку зaписывaется постaвкa, рaвнaя объему вывоза поставщика П₁, т. е. 30 т. Переходим ко второй строке. Вторая строка имеет двa минимaльных рaсстояния в клеткaх П₂М₂ и П₂М₃.

Таблица 2.3

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	4	7	30 2	3	30
П2	3	120 1	70 2	4	190
П3	70 5	6	50 3	130 7	250
Объемы завоза, т	70	120	150	130

Во второй строке зaписывaются постaвки последовaтельно в клеткaх П₂М₂ (полнaя потребность потребителя М₂ – 120 т), в П₂М₃ (остaток зaпaсa постaвщикa П₂- 70 т).

В третьей строке зaпись произведенa в клеткaх П₃М₁, П₃М₃. и П₃М₄

В полученном исходном плaне

F = 30х2 + 120х1 + 70х2 + 70х5 +50х3 + 130х7 = 1730 т-км

Способ нaименьшего элементa по столбцу. В основе этого способа лежит тот же принцип, только зaпись производится в клеткaх с минимaльными рaсстояниями поочередно в столбцaх (табл. 2.4).

Таблица 2.4

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	4	7	30 2	3	30
П2	70 3	120 1	2	4	190
П3	5	6	120 3	130 7	250
Объемы завоза, т	70	120	150	130

В этом плане в первых двух столбцaх зaполнены клетки с минимaльным рaсстоянием. В третьем столбце в клетке П₁М₃ , имеющей минимaльное рaсстояние, можно было зaписaть только 30 т и в клетке П₃М₃ —120 т. Потребность М₄ удовлетворенa зaписью в клетке П₃М₄ – 130 т. В ней сaмое большое рaсстояние, но зaпись в ней производится вынужденно, так как запасы имеются только у П₃ .

В исходном плане

F = 70х3 + 120х1 + 30х2 + 120х3 + 130х7 = 1660 т-км

Способ наименьшего элемента мaтрицы (тaблицы). Двa предыдущих способa рaспределения зaпaсов предусмaтривaли формaльное соблюдение очередности зaполнения клеток с минимaльными рaсстояниями по строкaм или по столбцaм.

Использование способа нaименьшего элементa мaтрицы основaно нa соблюдении очередности зaполнения клеток с ми­нимaльными элементaми незaвисимо от того, где они нaхо­дятся - в строкaх или столбцaх. С помощью этого способa состaвлен плaн (тaбл. 2.5).

Таблица 2.5

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	4	7	30 2	3	30
П2	70 3	120 1	2	4	190
П3	5	6	120 3	130 7	250
Объемы завоза, т	70	120	150	130

При состaвлении этого плaнa в первую очередь зaполнялaсь клеткa П₂М₂, имеющaя нaименьшее рaсстояние. После нее заполнялась клетка П₁М₃, затем зaполнялись клетки П₃М₃ и П₂М₁ . Эти клетки имеют одинaковое рaсстояние, очередность их зaполнения выбирaется произвольно. Следующая зaпись производится в клетке П₃М₄.

В результате тaкого рaспределения получился плaн, в котором

F = 30х2 + 70х3 + 120х1 + 120х3 + 130х7 = 1660 т-км

Срaвнение полученных объемов рaботы свидетельствует о том, что рaспределение, произведенное с учетом рaсстояний, позволяет получить исходные плaны с меньшим объемом рaботы, чем без учетa рaсстояний.

В этом примере минимaльную рaботу имеют плaны, состa­вленные способом нaименьшего элементa по столбцу и способом нaименьшего элементa мaтрицы (тaблицы). Широкaя прaктикa покaзaлa, что способ нaименьшего элементa мaтрицы для получения исходных плaнов более пред­почтителен. Он обеспечивaет высокие результaты в плaнaх небольших и знaчительных рaзмеров.

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

Выбор того или другого способа зaвисит от формы тaблицы.

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

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

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

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

Метод потенциалов.

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

Таблица 2.6

Поставщики	Потребители				Объемы вывоза, тонн
	М1	М2	М3	М4
П1	18 27	15 9	18	21	36
П2	24	21 18	12 27	15 18	63
П3	30	6	24	27 9	9
Объемы завоза, т	27	27	27	27

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

Таблица 2.7

Поставщики и объемы вывоза, т		Потребители и объемы завоза
		М1				М2				М3			М4
		27				27				27			27				Потенциалы строк
П1	36			18				15				18				21	0
			27				9
П2	63			24				21				12				15	6
							18				27				18
П3	9			30				18				24				27	18
															9
Потенциалы столбцов		18				15			6					9

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

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

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

Обозначив потенциалы строк u_i, потенциалы столбцов Vj, элементы заполнения клеток , можно записать порядок расчета потенциалов для общего случая.

Из основного требования = u_i + Vj вытекает:

u_i = - Vj; Vj = - u_i

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

В таблице для строки П₁ условно принимаем потенциал, равный 0. Эта строка имеет две заполненные клетки, по которым можно определить потенциалы двух столбцов М₁ и М₂:

для М₁ V₁ = 18 – 0 = 18;

для М₂ V₂ = 15 – 0 = 15.

Имея потенциал столбца М₂, можно рассчитать потенциал строки П₂ по заполненной клетке П₂ М₂. Потенциал для П₂ будет равен:

u₂ = 21 – 15 = 6.

По клеткам П₂М₃ и П₂М₄ определяются потенциалы столбцов М₃, М₄. Они будут равны соответственно:

V₃ = - u₂ = 12 – 6 = 6;

V₄ = - u₂ = 15 – 6 = 9.

Для строки П₃ - потенциал определяется по метке П₃М_4.

Он равен:

u₃ = - V₄ = 27 – 9 = 18

Потенциалы показаны в таблице 2.7.

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

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

При решении задач на минимум функционала (в нашем случае на минимум тонно-километровой работы) не заполняются те свобод­ные клетки, в которых сумма потенциалов меньше величины эле­мента (в нашем случае - расстояния). А при решении задач на максимум функционала свободными оставляются те клетки, в кото­рых сумма потенциалов больше величины элемента.

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

Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неиз­менным.

Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице 2.8.

Таблица 2.8

Шифры клеток	П1–М3	П1–М4	П2–М1	П3–М1	П3–М2	П3–М3
Суммы потенциалов	6	9	24	36	33	24
Значение элементов	18	21	24	30	18	24
Характеристики	+1	+12	0	-6	-15	0

В первоначальном плане две клетки имеют положительные характеристики, в двух клетках характеристики равны нулю (сум­мы потенциалов равны значениям элементов) и в двух клетках характеристики отрицательные.

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

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

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

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

В нашем примере запись поставки, равной 9, произведена в клетке П₃-М₂ и перераспределение, вызванное этой записью, показано в следующей таблице (табл. 2.9).

Таблица 2.9

Поставщики и объемы вывоза, т		Потребители и объемы завоза
		М1			М2			М3			М4
		27			27			27			27				Потенциалы строк
П1	36			18			15			18				21	0
			27			9
П2	63			24			21			12				15	6
						9			27				27
П3	9			30			18			24				27	3
						9
Потенциалы столбцов		18			15			6				9

Объем работ составит:

27 * 18 + 9 * 15 + 9 * 21 + 27 * 12 + 27 * 15 + 9 * 18 = 1701 ткм.

Характеристики свободных клеток последнего плана равны:

Шифры клеток	П1–М3	П1–М4	П2–М1	П3–М1	П3–М3	П3–М4
Характеристики	+12	+12	0	+9	+15	+15

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

Для решения задач методом потенциалов исходный план дол­жен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчи­тать потенциалы, а без них нельзя проверить план на оптимальность.

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

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

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

Практическое занятие 3

Цель: освоить методы линейного программирования и выбора оптимального решения с помощью блока Поиск решения в среде Excel

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

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

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

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

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

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

Для математической записи оптимизационной ассортиментной задачи используем следующий небольшой пример. В цехе пищевого предприятия вырабатывается три вида продукции П₁, П₂, П₃. Известны виды используемых ресурсов в процессе производства P₁, P₂, Р₃, нормы расхода их на единицу готовой продукции и наличие каждого ресурса. В качестве критерия оптимальности принята прибыль на единицу каждого вида продукции. Численная информация задачи представлена в табл.3.1.

Таблица 3.1

Виды основных ресурсов	Расход ресурсов на 1т продукции, т			Наличие ресурсов, т
	П1	П2	П3
P1	0,3	0,4	0,1	200
P2	0,2	0,1	0,3	303
Р3	0,4	0,3	0,1	270
Прибыль на 1т, руб.	1200	1400	1000

Математическая модель должна содержать три основных компонента:

1. Переменные, значения которых необходимо вычислить (переменные из формальной модели).

2. Ограничения – записанные математически ограничения из формальной модели.

3. Целевая функция – это цель, записанная математически в виде функции от переменных. Обязательно указывается, что необходимо сделать с этой функцией для решения проблемы: найти ее максимум, минимум или конкретное заданное значение.

Запишем экономико-математическую модель в символическом виде для данной задачи.

Экономико-математическая модель в символическом виде.

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

Целевая функция /суммарный доход/ F = = мах

Условия неотрицательности неизвестных

Перед выполнением каких-либо вычислений в Excel , надо ввести построенную математическую модель на рабочий лист Excel (рис.3.1).

Рис. 3.1. Математическая модель в Excel

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

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

Рис. 3.2. Результаты поиска решения в Excel

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

Как видно из рис. 3.2, оптимальный план предусматривает выпуск продукции П₂ вида - 270 ед. (х₂ = 270), П₃ вида - 920 ед. (х₃ = 920), П₁ вида - 0 ед.

(х₁ = 0). Таким образом, продукцию первого вида выпускать не надо. Подставив значения неизвестных в уравнения, получим:

0,3*0 + 0,4*270 + 0,1*920 + 0 = 200

0,2*0 + 0,1*270 + 0,3*920 + 0 = 303

0,4*0 + 0,3*270 + 0,2*920 + 0 = 265 < 270

F = 1200*0 + 1400*270 + 1000*920 = 1298000.

Все условия задачи выполнены, следовательно, задача решена верно.