Задачи линейного программирования

Задачи линейного  программирования.

 

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

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

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

1. нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);
2. оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
3. определение оптимального рациона (оптимизация состава химической смеси);
4. транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
5. задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции);
6. задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

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

1. использования планов большой размерности (т. е. с большим количеством варьируемых переменных);
2. задания ограничений сложного вида;
3. отыскания оптимального из допустимых решений;
4. генерирования множества различных решений, сохраняемых в дальнейшем в виде сценариев;
5. автоматического создания отчета по решению задачи.

Теоретической основой  надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам. «Поиск решения» является дополнением Excel, т. е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой Сервис®Надстройки®Поиск решения.

В качестве примера рассмотрим решение следующей задачи.

Задача 1.Для откорма животных на ферме в их ежедневный рацион необходимо включить не менее 33 единиц питательного вещества А, 23 единиц вещества В и 12 единиц вещества С. Для откорма используется 3 вида кормов. Данные о содержании питательных веществ и стоимости весовой единицы каждого корма даны в таблице 1.

Таблица 1

	А	В	С	Стоимость
Весовая единица корма I	4 ед.	3 ед.	1 ед.	20 к.
Весовая единица корма II	3 ед.	2 ед.	1 ед.	20 к.
Весовая единица корма III	2 ед.	1 ед.	2 ед.	10 к.

Требуется составить  наиболее дешёвый рацион, при котором  каждое животное получило бы необходимые количества питательных веществ А, В и С.

Решение. Пусть х₁, х₂, х₃ – количества кормов I, II, III видов, включаемые в ежедневный рацион (х_i³0, i=1, 2, 3). Тогда должно быть:

(1)

При этом линейная функция (стоимость рациона)

f=20х₁+20х₂+10х₃®min.  (2)

При решении задачи с  помощью надстройки Поиск решения необходимо:

1. Открыть окно Microsoft Excel;
2. сделаем первый столбец А – столбцом заголовка, т.е. заполним ячейки A1¸А4 таблицы обозначениями х₁, х₂, х₃ и min соответственно;
3. активизируйте ячейку В4 и запишите в неё формулу (2), см. рис. 16.1;
4. в область ячеек А7¸С9 запишите систему (1), см. рис. 16.2;

Рис. 16.1       Рис. 16.2

5. для решения поставленной задачи в меню Сервис выполните нажатие ЛКМ на Поиск решения…;

6. в появившемся окне в поле «Установить целевую» нажатием ЛКМ выделите ячейку В4; в поле «Изменяя ячейки» выделите область В1¸В3; нажатием ЛКМ установите флажок в поле «минимальному значению» (см. рис. 16.3).

7. У нас осталось незаполненным поле «Ограничения», поэтому ЛКМ нажмем на копке Добавить;
8. после того, как появилось окно Добавление ограничения активизируйте поле «Ссылка на ячейку» и выполните нажатие ЛКМ на ячейке А7. В следующем поле выберите знак « >= », затем в поле «Ограничения» выполните нажатие ЛКМ на ячейке С7 (см. рис. 16.4);

Рис. 16.4

9. аналогично описанному в предыдущем пункте добавьте ограничения, записанные в область ячеек А8¸С9;
10. помимо ограничений, введённых нами в электронную таблицу, в задаче есть ещё одно ограничение, которое мы тоже должны внести (х_i³0). Поэтому мы должны добавить ещё одно ограничение: $B$1:$B$3>=0.
11. Теперь все ограничения нами учтены и мы можем нажать лкм на ОК, после чего мы снова попадаем в диалоговое окно Поиск решения, где лкм нажимаем на Выполнить.
12. Появляется диалоговое окно Результаты поиска решения, в котором компьютер предлагает по умолчанию сохранить найденное решение. Если вы согласны с полученными результатами, то лкм нажмите на кнопке ОК. Результат полученных вычислений представлен на рис. 16.5.

Рис. 16.5

Задача 2. На товарных станциях С₁ и С₂ имеется по 30 комплектов мебели. Известно, что перевозка одного комплекта со станции С₁ в магазины М₁, М₂, М₃ стоит 1р., 3р., 5р., а стоимость перевозки со станции С₁ в те же магазины – 2р., 5р., 4р. необходимо доставить в каждый магазин по 20 комплектов мебели. Составить план перевозок так, чтобы затраты на транспортировку мебели были наименьшими.

Решение. Количество комплектов мебели, перевозимых со станции С₁ в магазины М₁, М₂, М₃ обозначим через х₁, х₂, х₃, а со станции С₂ – через х₄, х₅, х₆. Тогда схема перевозок буде выглядеть следующим образом:

Таблица 2

	В М1	В М2	В М3	Всего отправлено
Из С1	х1,	х2	х3	30
Из С2	х4	х5	х6	30
Всего получено	20	20	20	60

В соответствии с условием задачи х_i³0 (i=1, 2, …, 6). Задача сводится к тому, чтобы найти такое неотрицательное решение системы (3)

  (3)

при котором линейная функция (стоимость перевозок)

  (4)

имеет наименьшее значение.

Далее приступим к  решению задачи в программе Microsoft Excel. Для этого:

13. сделайте столбец F – столбцом заголовка, т.е. заполните ячейки F1¸ F7 таблицы обозначениями х₁, х₂, х₃ х₄, х₅, х₆ и min соответственно;
14. выполните действия, аналогичные действиям, описанным в пунктах 3–11, меняя только ссылки на ячейки, в результате чего окно Поиск решения будет выглядеть так как представлено на рис. 16.6, а решение задачи – на рис. 16.7.

 

Рис. 16.6

Рис. 16.7

 

Задания для  самостоятельной работы.

Задача №1. Для участия в командных соревнованиях по лёгкой атлетике спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по бегу, прыжкам в высоту и прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, в прыжках в высоту – не более 10. Количество очков, гарантируемое спортсмену каждого разряда по каждому виду, указано в таблице:

Разряд	Бег	Прыжки в  высоту	Прыжки в  длину
I	4	5	5
II	2	3	3

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

 

Задача №2. Три завода производят одно и то же изделие, которое отправляется четырем потребителям. Известно, что I завод поставляет 90 вагонов изделий, II – 30 вагонов, III

 – 40 вагонов. Для  потребителей требуется: первому  – 70 вагонов, второму – 30, третьему – 20 и четвёртому – 40. Стоимость (в руб.) перевозки одного вагона между каждым поставщиком и потребителем указаны в следующей таблице:

 

Потребители Поставщики	1	2	3	4
I	18	20	14	10
II	10	20	40	30
III	16	22	10	20

Определить минимальный  по стоимости план перевозок.

 

Задача №3. Груз, хранящийся на складах, в каждом соответственно 60, 80 и 106 машин, требуется перевезти в четыре магазина. В первый магазин требуется 44 машины, во второй – 70, в третий – 50, в четвёртый – 82. Стоимость прогона одной машины за 1 км составляет 10 коп. расстояния между складами и магазинами указаны в таблице:

 

Магазины Склады	1	2	3	4
1	13	17	6	8
2	2	7	10	41
3	12	18	2	22

Составить оптимальный  по стоимости план перевозки груза  из складов в магазины.