1.1 Ситуационно (практическая) задача № 1

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

Таблица 1

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

Требуется:

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

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

3. Составив двойственную задачу, к задаче оптимизации выпуска продукции, найти ее оптимальное решение, используя условия «дополняющей нежесткости». Дать экономическую интерпретацию этого решения.

1.2 Ответ на задачу № 1

1. Составить модель расчета оптимальной производственной программы для этой фирмы на основе задачи линейного программирования.

Для построения экономико-математической модели заданной производственной ситуации обозначим через искомую программу выпуска изделий A, а через - искомую программу выпуска изделий B.

Тогда производственная программа полностью будет представлена вектором .

Эта программа должна выбираться с учетом объемов имеющихся ресурсов в рассматриваемом периоде.

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

Отсюда ограничение на расход сырья представится неравенством

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

Суммарные затраты труда на производственную программу рассчитываются по формуле , и эти затраты не должны превысить 471чел.ч. Отсюда получаем ограничение на затраты труда:

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

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

Искомая программа должна максимизировать сумму z, которая также называется целевой функцией, или критерием оптимизационной модели.

Символически требование максимизации отражается записью

Представим составленную модель в следующей компактной записи:

Найти ;

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

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

Запишем уравнения граничных прямых для этих полуплоскостей.

Построим прямые и отметим область допустимых значений.

Рис.1

Рис.2

ABCD - область допустимых значений.

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

Построим линию уровня Z = 0: 393х1 + 179х2 = 0

Таким образом, наибольшее значение Z достигается в вершине, через которую проходит линия уровня, соответствующая наибольшему значению Z.

Рис.3

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

Так как точка. С получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x1+ 3x2=153

7x1+x2=471

Решив систему уравнений, получим: x1 = 63, x2 = 30. Откуда найдем максимальное значение целевой функции:Zmax = 393*63 + 179*30 =30129.

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

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

Сформулируем двойственную задачу:

- величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 кг сырья к прежним 365 кг. Эту величину назовем предельной эффективностью 366-го кг сырья;

- величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 ст.-ч оборудования к прежним 153 ст.-ч. Эту величину назовем предельной эффективностью 154-го ст.-ч оборудования;

- величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 человеко-ч труда к прежним471 человеко-ч. Эту величину назовем предельной эффективностью 472-го человеко-ч труда.

Найти

3u1 + u2 +7u3? 393;

u1 + 3u2 +u3? 179;

u1 ? 0; u2 ? 0; u3 ? 0.

Условия «дополняющей не жесткости»:

1) u1 (365 - 3x1 - x2 ) = 0

u2 (153 - x1 - 3x2) = 0

u3 (471 - 7x1 - x2) = 0

2) x1 (3u1 + u2 + 7u3 - 393) = 0

x2 (u1 + 3u2 + u3 - 179) = 0

Подставив в условия «дополняющейнежесткости» оптимальную программу выпуска, найти предельную эффективность имеющихся у предприятия объемов ресурсов.

Подставим в УДН x1 = 63, x2 = 30:

u1 (365 - 3*63- 30) = 0

u2 (153 - 63- 3*30) = 0

u3 (471 - 7*63- 30) = 0

63* (3u1 + u2 + 7u3 - 393) = 0

30* (u1 + 3u2 + u3 - 179) = 0

Тогда,

u1 *146 = 0

u2 *0 = 0

u3 *0 = 0

3u1 + u2 + 7u3 - 393 = 0

u1 + 3u2 + u3 - 179 = 0

Произведение равно нулю тогда, когда один из множителей равен нулю, получим u1=0.

Решим систему

u2 + 7u3 - 393 = 0

3u2 + u3 - 179 = 0

Получим u2 =43, u3 = 50.

Для проверки вычислим wmin =

В соответствии с вышесказанным, найденное оптимальное решение двойственной задачи интерпретируется следующим образом:

= 0 р. - величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 кг сырья к прежним 365 кг.

= 43 р. - величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 ст.-ч оборудования к прежним 153 ст.-ч.

= 50 р. - величина ожидаемого прироста максимума выручки от дополнительного привлечения в производство 1 человеко-ч труда к прежним 471 человеко-ч.

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

Прямая задача:

Zmax = 393*63 + 179*30 =30129.

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

0+ 43 +7*50? 393; 393 ? 393 верно

0+ 3*43 +50? 179; 179 ? 179 верно

u1 ? 0; u2 ? 0;u3 ? 0.

wmin =

Расчеты верные. Решения являются оптимальными.

1.3 Ситуационно (практическая) задача № 2

Необходимо доставить однородный груз от трех филиалов фирмы пяти потребителям:

Известна матрица затрат на доставку единицы груза от каждого поставщика потребителю 7 (руб.).

1. Составить ЭММ расчета оптимального плана перевозок.

2. Определить исходный опорный план методом северо-западного угла.

3. Найти оптимальный план перевозок методом потенциалов и указать соответствующие ему минимальные транспортные затраты.

1.4 Ответ на задачу № 2

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

Таблица 2

Проверим необходимое и достаточное условие разрешимости задачи. Суммарный объем продукции у поставщиков равен:

?a = 61 + 36 + 99 = 196 ,

а суммарная потребность составляет величину:

?b = 38 + 41 + 64 + 65 + 2 = 270

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 74 (270 - 196). Тарифы перевозки единицы груза полагаем равными нулю.

Занесем исходные данные в распределительную таблицу.

Таблица 3

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

для которой выполняются ограничения по поставщикам:

ограничения по потребителям:

граничные условия:

? 0, i =1,..,4;j = 1,..,5;

минимизируются суммарные транспортные расходы:

S =

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

Построим опорныйплан Т-задачи по правилу северо-западного угла. Все исходные данные Т-задачи представляются в табличной форме:

Таблица 4

Берется северо-западный угол таблицы, клетка (1,1), и планируется поставка от первого поставщика к первому потребителю в объемеx11 = min {a1, b1} = min {61, 74} = 61.

Эта поставка записывается в правый нижний угол клетки. Величина запланированной поставки вычитается из запаса продукцииa1 и потребности b1. Неудовлетворенная потребность первого потребителя становится 74-61 = 13,а запас продукции у первого поставщика - полностью исчерпанным. Первая строка закрывается, т. е. она больше не участвует при построении начального опорного плана.

В оставшейся части таблицы снова берем северо-западный угол - клетку(2,1). Полагая, что x21 = min {36, 13} = 13, корректируем запас продукции у второго поставщика и потребность первого потребителя. Величина оставшегося запаса: 36 - 13 =23. Первый потребитель удовлетворен полностью, следовательно, первый столбец закрывается.

Берем клетку (2,2), полагаем x22 = min {23,23} = 23и вычитаем величину этой поставки из оставшегося объема продукции у второго поставщика и потребности второго потребителя.

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

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

Затем берем клетку (1,2), так как тариф наименьший в этой кетке, находим x12 = min {99, 0} = 0 и закрываем второй столбец. Клетку (1,2) будем считать клеткой, условно заполненной нулем.

В оставшейся части таблицы северо-западной клеткой будет клетка (3,3).Полагая x33 = min{85,99}=85, для клетки (3,4) находим величину поставки 99 - 85=14. После осуществления этой поставки одновременно удовлетворена потребность четвертого потребителя и полностью распределена продукция третьего поставщика. Закроем третью строку и перейдем к клетке (4,4).

Находим, что x44= min{74,30}= 30. После записи поставки в клетку (4.4) таблицы ее четвертый столбец автоматически закрывается.

Последней рассматривается клетка (4,5), куда заносится объем поставкиx45 = min{44, 44}=44.

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

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

Оптимизацию начального опорного плана осуществим методом потенциалов. При каждой итерации этого метода выполняются следующие процедуры:

1) вычисление потенциалов, согласованных с найденным опорным планом;

2) проверка плана на оптимальность с помощью потенциалов;

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

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u2 + v1 = 16; 8 + u2 = 16; u2 = 8

u2 + v2 = 17; 8 + v2 = 17; v2 = 9

u3 + v3 = 10; 0 + u3 = 10; u3 = 10

u3 + v3 = 10; 10 + v3 = 10; v3 = 0

u3 + v4 = 10; 10 + v4 = 10; v4 = 0

u4 + v4 = 0; 0 + u4 = 0; u4 = 0

u4 + v5 = 0; 0 + v5 = 0; v5 = 0

Таблица 5

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj>cij

(3;1): 10 + 8 > 13; ?31 = 10 + 8 - 13 = 5

(3;2): 10 + 9 > 11; ?32 = 10 + 9 - 11 = 8

(4;1): 0 + 8 > 0; ?41 = 0 + 8 - 0 = 8

(4;2): 0 + 9 > 0; ?42 = 0 + 9 - 0 = 9

Выбираем максимальную оценку свободной клетки (4,2).

Для этого в (4,2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 6

Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u2 + v1 = 16; 8 + u2 = 16; u2 = 8

u2 + v2 = 17; 8 + v2 = 17; v2 = 9

u4 + v2 = 0; 9 + u4 = 0; u4 = -9

u4 + v4 = 0; -9 + v4 = 0; v4 = 9

u3 + v4 = 10; 9 + u3 = 10; u3 = 1

u3 + v3 = 10; 1 + v3 = 10; v3 = 9

u4 + v5 = 0; -9 + v5 = 0; v5 = 9

Таблица 7

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj>cij

(1;3): 0 + 9 > 7; ?13 = 0 + 9 - 7 = 2

(1;4): 0 + 9 > 4; ?14 = 0 + 9 - 4 = 5

(1;5): 0 + 9 > 6; ?15 = 0 + 9 - 6 = 3

(2;3): 8 + 9 > 14; ?23 = 8 + 9 - 14 = 3

(2;4): 8 + 9 > 12; ?24 = 8 + 9 - 12 = 5

(2;5): 8 + 9 > 15; ?25 = 8 + 9 - 15 = 2

Выбираем максимальную оценку свободной клетки (1;4)

Для этого в клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 8

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 23. Прибавляем 23 к объемам грузов, стоящих в плюсовых клетках и вычитаем 23 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 9

Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u2 + v1 = 16; 8 + u2 = 16; u2 = 8

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u4 + v2 = 0; 9 + u4 = 0; u4 = -9

u4 + v4 = 0; -9 + v4 = 0; v4 = 9

u3 + v4 = 10; 9 + u3 = 10; u3 = 1

u3 + v3 = 10; 1 + v3 = 10; v3 = 9

u4 + v5 = 0; -9 + v5 = 0; v5 = 9

Таблица 10

линейный оптимальный план