Используя условия рассмотренной задачи и данные предлагаемых вариантов, составить экономико-математическую модель задачи и решить задачу методом потенциалов.
№
Значения по вариантам:
а1=280
а2=250
а3=430
в1=180
в2=210
в3=400
в4=170
а1=150
а2=200
а3=100
в1=100
в2=150
в3=100
в4=100
а1=200
а2=350
а3=300
в1=150
в2=100
в3=300
в4=300
а1=340
а2=280
а3=260
в1=180
в2=220
в3=180
в4=350
а1=430
а2=270
а3=350
в1=200
в2=320
в3=180
в4=350
а1=250
а2=170
а3=140
в1=200
в2=160
в3=140
в4=60
а1=200
а2=250
а3=190
в1=130
в2=220
в3=150
в4=140
а1=300
а2=210
а3=200
в1=190
в2=110
в3=180
в4=230
а1=350
а2=270
а3=210
в1=280
в2=240
в3=170
в4=140
а1=350
а2=200
а3=300
в1=250
в2=200
в3=150
в4=250
а1=210
а2=170
а3=300
в1=180
в2=150
в3=120
в4=230
а1=300
а2=250
а3=200
в1=170
в2=230
в3=200
в4=150
а1=120
а2=200
а3=200
в1=100
в2=160
в3=130
в4=130
а1=200
а2=450
а3=100
в1=160
в2=200
в3=140
в4=250
а1=260
а2=200
а3=310
в1=130
в2=170
в3=220
в4=250
а1=270
а2=330
а3=450
в1=250
в2=180
в3=220
в4=400
а1=290
а2=450
а3=210
в1=220
в2=340
в3=280
в4=110
а1=300
а2=210
а3=320
в1=200
в2=250
в3=280
в4=100
а1=190
а2=230
а3=310
в1=150
в2=220
в3=200
в4=160
а1=290
а2=210
а3=300
в1=220
в2=180
в3=210
в4=190
Вопросы для самоконтроля
1. Как в общем виде можно сформулировать постановку транспортной задачи?
2. Каким образом можно математически записать ограничения по наличию груза в пунктах отправления?
3. Каким образом можно математически записать ограничения по удовлетворению потребности пунктов потребления в грузе?
4. Приведите запись транспортной задачи в структурной форме.
5. В каком случае транспортная задача считается открытой?
6. В каком случае транспортная задача считается закрытой?
7. Каким образом открытая транспортная задача может быть приведена к закрытому типу?
8. Каков критерий оптимальности в решенной Вами транспортной задаче?
9. Для записи каких значений в таблице для решения транспортной задачи предназначены строка Vj и столбец Ui?
10. Какой способ построения первого опорного плана транспортной задачи Вы использовали?
11. В чем сущность распределения объема перевозок методом северо-западного угла?
12. Каким образом для каждого опорного плана определяется значение целевой функции?
13. Какому значению должно быть равно количество заполненных клеток в каждом опорном плане?
20. Расскажите алгоритм перехода от одного опорного плана к следующему.
21. Раскройте правила построения замкнутого контура, по вершинам которого будут перемещаться объемы грузоперевозок для улучшения опорного плана.
22. Раскройте правила перемещения объемов грузоперевозок по вершинам замкнутого контура.
23. О чем свидетельствует наличие в оптимальном плане нулевых характеристик свободных клеток?
2. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ MICROSOFT EXCEL
Пример решения задачи по оптимизации использования ресурсов
Сельскохозяйственное предприятие специализируется на производстве зерна, сахарной свеклы и подсолнечника. Для возделывания этих сельскохозяйственных культур может быть выделено до 3 200 га пашни, дизельного топлива в объеме до 200 000 кг и минеральных удобрений в объеме до 400 000 кг действующего вещества. Требуется найти такое сочетание посевных площадей, которое обеспечило бы получение максимума прибыли.
Следует также учесть, что:
- площадь посева технических культур (сахарной свеклы и подсолнечника) не должна превышать 20% общей площади пашни;
- предприятием заключен договор на продажу зерна в объеме 105 000 ц.
Входная информация, необходимая для разработки экономико-математической модели приведена в таблице 13.
Таблица 13. Входная информация для разработки экономико-математической модели
Показатели
Сельскохозяйственные культуры
зерновые
сахарная
свекла
подсолнечник
Урожайность, ц/га
Цена реализации 1 ц продукции, руб./ц
Выход товарной продукции с 1 га, тыс. руб.
19,2
57,0
20,4
Затраты на 1 га:
материально-денежных средств, тыс. руб.
9,8
42,5
10,1
дизельного топлива, кг
минеральных удобрений, кг д. в-ва
90,0
360,0
Прибыль с 1 га, руб.
9,4
14,5
10,3
За неизвестные примем площади посева сельскохозяйственных культур по видам:
X1 - зерновых культур;
X2 - сахарной свеклы;
X3– подсолнечника.
Для построения экономико-математической модели задачи необходимо учесть все условия. В данном случае по этим условиям можно составить пять ограничений:
- сумма площадей посева сельскохозяйственных культур не должна превышать площади, имеющейся в предприятии (3 200 га). Коэффициенты при неизвестных характеризуют расход пашни на возделывание 1 га соответствующей сельскохозяйственной культуры. В правой части ограничения указывается объем площади пашни
1) Х1+Х2+Х3<=3 200;
- сумма площадей посева технических культур не должна превышать площади, которая может быть отведена для этой цели (3200·20%=640 га). Коэффициенты при неизвестных характеризуют расход пашни, отводимой под технические культуры, на возделывание 1 га соответствующей технической культуры. В правой части ограничения указывается объем площади пашни, которая может быть отведена под технические культуры.
2) Х2+Х3<=640;
- третье и четвертое ограничения гарантируют, что использование ресурсов не превысит их наличия. То есть сумма произведений затрат ресурсов на 1 га на площади посева соответствующих сельскохозяйственных культур не должна превышать объемов ресурсов, имеющихся в предприятии. Коэффициенты при неизвестных характеризуют расход соответствующего ресурса на возделывание 1 га соответствующей сельскохозяйственной культуры. В правой части ограничений указывается наличие этих ресурсов в хозяйстве:
3) 50Х1+ 124Х2+68Х3<=200 000;
4) 90Х1+360Х2+120Х3<=350 000;
- пятое ограничение гарантирует производство запланированного объема реализации зерна. В качестве коэффициентов при переменных выступает выход зерна с 1 га площади посева зерновых культур. В правой части указывается запланированный объем реализации зерна
5) 40Х1>=105 000.
В результате получена система пяти линейных неравенств с тремя неизвестными. Требуется найти такие неотрицательные значения этих неизвестных Х1>=0; Х2>=0; Х3>=0, которые бы удовлетворяли данной системе неравенств и обеспечивали получение максимума прибыли:
Zmax = 9,4Х1+14,5Х2+10,3Х3.
В качестве коэффициентов при неизвестных в целевой функции выступает прибыль, получаемая с 1 га площади посева сельскохозяйственных культур.
Поскольку данная задача решается с помощью MS Excel, то и подготовку всей входной информации для построения экономико-математической модели целесообразно осуществлять также с использованием этого табличного процессора. Эти расчеты представлены на листе «Исходные» файла MS Excel (рисунок 1). Это не только облегчает расчеты, связанные с подготовкой входной информации, но и дает возможность в дальнейшем автоматически обновлять параметры экономико-математической модели при реализации различных вариантов.
Рисунок 1. Входная информация для разработки экономико-математической модели
Экономико-математическая модель по оптимизации структуры посевных площадей в матричном виде заполняется на листе «Модель» файла MS Excel, уже содержащего лист «Исходные» (рисунок 2). Технико-экономические коэффициенты, оценки целевой функции (столбцы D, E, F), объемы ограничений (столбец I) рекомендуется определять через ссылки на соответствующие ячейки листа «Исходные». На рисунке 2 показано, каким образом произошло заполнение ячейки F9, описывающей затраты минеральных удобрений на 1 га посева подсолнечника (смотри строку «fx» рисунка 1).
Рисунок 2. Экономико-математическая модель по оптимизации
структуры посевных площадей
В столбцы А (№), В (Ограничения), С (Единицы измерения) и H (Тип ограничений) вводятся соответствующие данные в текстовом формате. Они не используются в расчетах и служат для информативности и облегчения понимания содержания модели.
Для искомых величин переменных Х1, Х2, Х3 необходимо оставить пустые ячейки соответственно D5, E5, F5. Столбец G (Сумма произведений), предназначен для определения суммы произведений значений искомых неизвестных (ячейки D5, E5, F5) и технико-экономических коэффициентов по соответствующим ограничениям (строки 6-10) и целевой функции (строка 11). Формула нахождения суммы произведений для строки с целевой функцией (для ячейки G11) приведена в верхней строке рисунка 3.
То есть, в столбце G будет определяться:
· количество используемых ресурсов (ячейка G6 – общей площади пашни; G7 – пашни, которая может быть использована под посевы технических культур; G8 – трудовых ресурсов; G9 – минеральных удобрений);
· количество произведенного зерна (ячейка G10);
· величина прибыли (ячейка G11).
Таким образом, построен опорный план и получено первое допустимое решение. Значения неизвестных Х1, Х2, Х3 равны нулю (ячейки D5, E5, F5-пустые ячейки), ячейки столбца G «Сумма произведений» по всем ограничениям (строкам 6-10) и целевой строке (строка 11) также имеют нулевые значения.
Рисунок 3. Экономико-математическая модель по оптимизации
структуры посевных площадей
Для оптимизации имеющегося плана воспользуемся инструментом Поиск решения, который находится в меню Сервис. Если нет такой команды в меню Сервис, необходимо в пункте Надстройка поставить галочку напротив Поиск решения. После этого данная процедура станет доступной в меню Сервис.
После выбора команды Поиск решения появится диалоговое окно.
Рисунок 4. Диалоговое окно команды Поиск решения
Поскольку в качестве критерия оптимизации нами выбрана максимизация прибыли, в поле Установить целевую ячейку необходимо ввести ссылку на ячейку, содержащую формулу расчета прибыли. В нашем случае это ячейка $G$11.
Рисунок 5. Диалоговое окно команды Поиск решения
Чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель необходимо установить в положение Равной максимальному значению.
В поле Изменяя ячейки необходимо ввести ссылки на изменяемые ячейки, разделяя их запятыми, либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($D$5:$F$5).
Рисунок 6. Диалоговое окно команды Поиск решения
В поле Ограничения необходимо ввести все ограничения, накладываемые на поиск решения.
В разделе Ограничения диалогового окна команды Поиск решения необходимо выбрать функцию Добавить. Появится следующее диалоговое окно.
Рисунок 7. Диалоговое окно команды Добавление ограничения
Добавление ограничений рассмотрим на примере всех ограничений. В поле Ссылка на ячейку необходимо ввести адрес одной ячейки (совокупности ячеек), на которую накладываются ограничения. В нашем случае это ячейки $G$6:$G$9, в которых находятся формулы расчета количества используемых ресурсов. Затем из раскрывающегося списка условных операторов необходимо выбрать необходимый знак, который должен располагаться между ссылкой на ячейку и ограничением. В нашем случае, это <=. В поле Ограничение необходимо ввести ссылки на ячейки, в которых находятся значения, характеризующие наличие ресурсов. В нашем случае это ячейки $I$6:$I$9.
В результате диалоговое окно примет следующий вид.
Рисунок 8. Диалоговое окно команды Добавление ограничения
После подтверждения добавления описанных ограничений (необходимо нажать кнопку Добавить), аналогично добавляется ограничение по обеспечению минимального объема производства зерна (строка 10).
Рисунок 9. Диалоговое окно команды Добавление ограничения
После описания последнего ограничения необходимо вернуться в диалоговое окно команды Поиск решения, нажав виртуальную кнопку OK.
Рисунок 10. Диалоговое окно команды Добавление ограничения
В случае внесения изменения в какое-либо из ограничений, необходимо выделить его в списке Ограничения и выбрать команду Изменить. Аналогичным способом можно удалить ненужное ограничение.
После добавления ограничений описываются параметры поиска решения. Для этого в диалоговом окне команды Поиск решения выбирается команда Параметры(рисунок 11).
Опция Линейная модель в диалоговом окне команды Параметры поиска решения служит для ускорения поиска решения линейной задачи оптимизации.
ОпцияНеотрицательные значения позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение.
Остальные параметры можно оставить без изменений либо установить необходимые параметры, используя опцию Справка.
Выбор параметров подтверждается нажатием виртуальной кнопки ОК
Рисунок 11. Диалоговое окно команды Параметры поиска решения
Для запуска задачи на решение необходимо нажать виртуальную кнопку Выполнить диалогового окна команды Поиск решения.
Рисунок 12. Диалоговое окно команды Результаты поиска решения
Для сохранения найденного решения на листе необходимо выбрать в диалоговом окне Результаты поиска решения опцию Сохранить найденное решение.
Для восстановления исходных данных применяется опция Восстановить исходные значения диалогового окна Результаты поиска решения.
Прерывание поиска решения осуществляется нажатием клавиши ESC.
В результате решения и сохранения результатов поиска модель примет вид, представленный на рисунке 13.
В ячейках D5:F5получены значения искомых неизвестных (площади посева равны: зерновых ‑ 2 625,0 га, сахарной свеклы – 186,5 га, подсолнечника – 388,5 га), в ячейках G6:G9 определены объемы используемых ресурсов (общей площади пашни – 3200 га; площади пашни, которая будет использоваться под посевы технических культур, – 575 га; дизельного топлива – 180 791,7 кг; минеральных удобрений – 350 000 кг д. в-ва), в ячейке G10 найдено количество зерна, которое может быть реализовано, ‑ 105 000 ц). При этом величина прибыли достигает 31 380,6 тыс. руб. (ячейка G11).
Рисунок 13. Экономико-математическая модель по оптимизации структуры посевных площадей с результатами решения
В случае если в результате поиска не было найдено решение, удовлетворяющее заданным условиям, в диалоговом окне Результаты поиска решенияпоявится соответствующее сообщение
Рисунок 14. Диалоговое окно команды Результаты поиска решения
Одной из наиболее часто встречающихся причин невозможности найти оптимальное решение является невыполнение одного или нескольких ограничений. Сохранив найденное решение, требуется построчно сравнить полученные значения столбцов «Сумма произведений» и «Объем ограничений» и проверить, удовлетворяет ли отношение между ними ограничению, стоящему в столбце «Тип ограничений». Найдя, таким образом, невыполняемые ограничения, необходимо найти и ликвидировать причины, обусловливающие невозможность соблюдения данного конкретного условия (это может быть, например, слишком большие или, наоборот, очень маленькие запланированные объемы ограничений и т.п.).
Пример решения транспортной задачи
В агрохолдинге имеется четыре склада, на которых хранится 1 350 т дизельного топлива, которое необходимо доставить в пять механизированных отрядов. Общая потребность механизированных отрядов в дизельном топливе составляет 1 300 т.
Информация о наличии дизельного топлива в разрезе складов и потребность в дизельном топливе в разрезе механизированных отрядов приведены в таблице 14.
Таблица 14. Информация о наличии и потребности в дизельном топливе, т
Склады
Имеется дизельного топлива
Механизированные отряды
Требуется
дизельного топлива
Склад №1
Мехотряд №1
Склад №2
Мехотряд №2
Склад №3
Мехотряд №3
Склад №4
Мехотряд №4
Мехотряд №5
Всего имеется
1 350
Всего требуется
1 300
Требуется определить, с какого склада, сколько и в какой механизированный отряд поставлять дизельное топливо, чтобы объем грузооборота был минимальным.
Информация о расстояниях между складами и механизированными отрядами приведена в таблице 15.
Таблица 15. Информация о расстояниях между складами и
механизированными отрядами, км
Поставщики
Потребители
Мехотряд №1
Мехотряд №2
Мехотряд №3
Мехотряд №4
Мехотряд №5
Склад №1
Склад №2
Склад №3
Склад №4
На пересечении столбца конкретного механизированного отряда со строкой склада находится информация о расстояниях между этим пунктом доставки и складом. Например, расстояние между мехотрядом №1 и складом №3 равно 16 км.
Исходные данные для решения транспортной задачи представлены на листе «Транспортная задача» файла MS Excel (рисунок 15).
Рисунок 15. Исходные данные для решения транспортной задачи
После формирования таблицы с исходными данными необходимо сформировать в матричной форме экономико-математическую модель транспортной задачи, которая представлена на рисунке 16.
Каждое значение в ячейках (диапазон ячеек C12:G15) на пересечении столбца конкретного пункта потребления и строки склада означает количество тонн, поставляемых с этого склада в данный пункт потребления. Поэтому в первом опорном плане эти ячейки заполняются нулями.
Рисунок 16. Исходные данные для решения транспортной задачи
Ячейки B12:B15 (Вывезено со склада) определяются суммированием элементов соответствующих строк. Например, ячейка B12=СУММ(C12:G12).
Ячейки C16:G16 (Доставлено потребителю) определяются суммированием элементов соответствующих столбцов. Например, ячейка C16СУММ(C12:C15).
В 18-ой строке в ячейках C18:G18 определим грузооборот по каждому пункту потребления. Грузооборот определяется как сумма произведений расстояний от конкретного пункта потребления до каждого из складов и объемов перевозок груза в этот пункт потребления с каждого склада. Пример формулы расчета ячейки С18 приведен в строке fx на рисунке 16.
В ячейке В18 по формуле СУММ(С16:G16) будет вычисляться общий объем грузооборота дизельного топлива. В первом опорном плане все объемы грузоперевозок равны нулю.
Для решения транспортной задачи воспользуемся процедурой Поиск решения, которая находится в меню Сервис.
После выбора данной процедуры появится диалоговое окно команды Поиск решения(рис.17).
Рисунок 17. Диалоговое окно команды Поиск решения
Поскольку в качестве критерия оптимальности выбрана минимизация грузооборота, в поле Установить целевую ячейку: необходимо ввести ссылку на ячейку, содержащую формулу расчета общего объема грузооборота дизельного топлива. В нашем случае это ячейка $B$18.
Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению.
В поле Изменяя ячейки: необходимо ввести ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($С$12:$G$15). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с С12 по G15, то есть будет изменяться количество груза, перевезенного по конкретному маршруту (рис. 18).
Рисунок 18. Диалоговое окно команды Поиск решения
В поле Ограничения: необходимо ввести все ограничения, накладываемые на поиск решения.
В разделе Ограничения: диалогового окна команды Поиск решения необходимо выбрать функцию Добавить. Появится следующее диалоговое окно (рис.19).
Рисунок 19. Диалоговое окно команды Добавление ограничения
Экономический смысл ограничений в данной задаче состоит в следующем:
· с каждого склада должно быть вывезено дизельного топлива не больше, чем на нем есть;
· потребности каждого потребителя должны быть удовлетворены полностью;
· объем грузоперевозок не может быть отрицательным.
То есть:
B12≤B5, B13≤B6, B14≤B7, B15≤B8 или $B$12:$B$15<=$B$5:$B$8;
C16=C4, D16=D4, E16=E4, F16=F4, G16=G4 или $C$16:$G$16=$C$4:$G$4
После ввода первого ограничения следует нажать кнопку Добавить и ввести второе ограничение. По окончании его ввода необходимо нажать на виртуальную кнопку ОК.
После выполнения вышеперечисленных инструкций диалоговое окно команды Поиск решениябудет иметь следующий вид (рис. 20).
Обратите внимание, условие неотрицательности переменных в системе ограничений не описывается. Это условие будет задано при описании параметров решения данной задачи.
Рисунок 20. Диалоговое окно команды Поиск решенияс заполненными полями
В случае внесения изменения в какое-либо из ограничений, необходимо указать его в списке Ограничения диалогового окна команды Поиск решения и выбрать команду Изменить. Аналогичным способом можно удалить ненужное ограничение. После добавления ограничений описываются параметры поиска решения. Для этого в диалоговом окне команды Поиск решения выбирается команда Параметры. Диалоговое окно команды Параметры поиска решения приведено на рисунке 21.
Опция Линейная модель в диалоговом окне команды Параметры поиска решения служит для ускорения поиска решения линейной задачи оптимизации.
Рисунок 21. Диалоговое окно команды Параметры поиска решенияс заполненными полями
ОпцияНеотрицательные значения позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение. Остальные параметры можно оставить без изменений, либо установить необходимые параметры, используя опцию Справка. Выбор параметров поиска подтверждается нажатием виртуальной кнопки ОК.
Для запуска задачи на решение необходимо нажать виртуальную кнопку Выполнить диалогового окна команды Поиск решения.
Для сохранения найденного решения на листе, необходимо выбрать в диалоговом окне Результаты поиска решения опцию Сохранить найденное решение(рис. 22). Для восстановления исходные данные, необходимо выбрать в диалоговом окне Результаты поиска решения опцию Восстановить исходные значения.
Рисунок 22. Диалоговое окно команды Результаты поиска решения
Прерывание поиска решения осуществляется нажатием клавиши ESC.
В результате решения и сохранения результатов поиска решения модель примет вид, представленный на рисунке 23.
Рисунок 23. Результаты поиска решения
В результате решения потребность всех механизированных отрядов удовлетворена полностью. Потребность в дизельном топливе механизированного отряда №1 (150 т) удовлетворяется полностью за счет запасов, имеющихся на складе №4. С этого же склада 170 т дизельного топлива доставляется в мехотряд №5. Еще 80 т, необходимые данному мехотряду, будут доставлены со склада №3.
Со склада №3 15 т дизельного топлива будут доставлены в мехотряд №2. Остальная потребность этого мехотряда (235 т) будет покрыта за счет дизельного топлива, хранящегося на складе №1. Потребность в дизельном топливе мехотряда №3 будет покрыта со склада №1 (13 т) и склада №2 (170 т). Вся потребность мехотряда №3 будет покрыта за счет доставки дизельного топлива со склада №2.
Со склада №3 остались невывезенными 50 т дизельного топлива.
Суммарный объем грузоперевозок составил 9 500 тонно-километров.
