Результаты применения надстройки Поиск решений

Ответ. Для получения максимальной прибыли необходимо произвести: 10 002 шт. наборов мебели вида 1; 10 000 шт. наборов мебели вида 2; 10 490 шт. наборов мебели вида 3; 4000 шт. тумб под телевизор. Книжные полки в этом месяце производить не нужно.

1.5.2. Транспортная задача и ее реализация в среде Excel

Транспортная задача является одной из наиболее распространенных задач линейного программирования и нахо­дит широкое практическое приложение.

Постановка транспортной задачи. Некоторый однородный про­дукт, сосредоточенный у т поставщиков A_i в количестве a_i (i = 1, …, т) единиц, необходимо доставить п потребителям B_j в количе­стве b_j (j = 1, …, п) единиц. Известна стоимость c_ij перевозки единицы груза от поставщика i к потребителю j. Составить план перевозок, позволяющий с минимальными затратами вывести все грузы и полностью удовлетворить потребителей.

Сформулируем экономико-математическую модель транспортной задачи. Обозначим через х_ij количество единиц груза, запланиро­ванных к перевозке от поставщика i к потребителю j. Так как от поставщика i к потребителю j запланировано перевезти x_ij единиц груза, то стоимость перевозки составит c_ijx_ij.

Транспортная задача относится к двухиндексным задачам ли­нейного программирования, так как в результате решения задачи необходимо найти матрицу X с компонентами x_ij.

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

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

i = 1, …, m;

б) все потребности должны быть удовлетворены, т.е.

j = 1, …, n.

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

(1.6)

при ограничениях

i = 1, …, m; (1.7)

j = 1, …, n; (1.8)

x_ij 0, i = 1, …, m; j = 1, …, n. (1.9)

В рассмотренной модели предполагается, что суммарные за­пасы равны суммарным потребностям, т.е.

(1.10)

Транспортная задача, в которой суммарные запасы и потреб­ности совпадают, т.е. выполняется условие (1.10), называется за­крытой моделью; в противном случае - открытой. Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности

б) суммарные потребности превышают суммарные запасы

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

при ограничениях:

в случае «а»

i = 1, …, m,

j = 1, …, n, x_ij 0;

в случае «б»

i = 1, …, m,

j = 1, …, n; x_ij 0.

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

В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_п+1, потребность которого описывается формулой

b_{п+1 =} ,

а для случая «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик А_т+1, запасы которого описываются формулой

a_{m+1 =} .

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

Транспортная задача имеет п + т уравнений с тхп неизвест­ными. Матрицу перевозок Х = (Х_ij)_тп, удовлетворяющую услови­ям (1.7)-(1.9), называют планом перевозок транспортной задачи, a x_ij - перевозками.

План X*, при котором целевая функция (1.6) обращается в минимум, называется оптимальным.

Применение транспортных моделей к решению некоторых экономических задач

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономичес­ких задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов С_ij имеют различный смысл в зависимости от конкретной экономической задачи. К таким за­дачам относятся [8]:

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

• Оптимальные назначения, или проблема выбора. Имеется т ме­ханизмов, которые могут выполнять п различных работ с про­изводительностью С_ij. Задача позволяет определить, какой ме­ханизм и на какую работу надо назначить, чтобы добиться максимальной производительности.

• Задача о сокращении производства с учетом суммарных рас­ходов на изготовление и транспортировку продукции.

• Задача о закреплении самолетов за воздушными линиями.

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

Решение транспортной задачи с помощью средства Excel Поиск решения

Исходные данные транспортной задачи приведены схематически: внутри прямоугольника заданы удельные транс­портные затраты на перевозку единицы груза c_ij, слева указаны мощности поставщиков a_i а сверху - мощности потребителей b_j. Найти оптимальный план закрепления поставщиков за потре­бителями x_ij.

В данной задаче суммарные запасы равны суммарным потребностям, т.е.

= 550.

Транспортная задача, в которой суммарные запасы и потреб­ности совпадают, является закрытой[4].

Ввод условий задачи состоит из следующих шагов.

1. Создание формы для решения задачи.

Этот шаг предполагает создание матрицы перевозок. Для этого необходимо выполнить резервирование изменяемых ячеек, поэтому в блок ячеек ВЗ:Е6 вводятся «1» — так резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку груза.

2. Ввод исходных данных.

В конкретном примере осуществляется ввод мощностей четырех поставщиков (ячейки А10:А13), потребности регионов в их продук­ции (В9:Е9), а также удельные затраты по доставке нефтепродуктов от конкретного поставщика потребителю (блок В10:Е13) (рис. 1.26).

3. Ввод граничных условий.

3.1. Вводим условия реализации мощностей поставщиков

,

где a_i - мощность поставщика i;

x_ij - объем поставки груза от поставщика i к потребителю j;

п - количество потребителей.

Для этого необходимо выполнить следующие операции:

• поместить курсор в ячейку A3;

• выбрать знак ;

• выделить необходимые для суммирования ячейки ВЗ:ЕЗ;

• нажать ENTER для подтверждения ввода формулы для сум­мирования.

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

• поместить курсор в ячейку A3;

• выбрать команду Копировать, т.е. скопировать в буфер фор­мулу, введенную для ячейки A3;

• выделить ячейки А4:А6;

• выбрать команду Вставить, тем самым из буфера будет встав­лена формула для суммирования в А4:А6.

3.2.Вводим условия удовлетворения запросов потребителей, т.е.

,

где b_i - мощность потребителя j;

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

• поместить курсор в ячейку В7;

• выбрать знак X, при этом автоматически выделяется весь столбец ВЗ:В6;

• нажать ENTER для подтверждения суммирования показате­лей выделенного столбца.

Эту же последовательность действий выполнить для ячеек С7 и Е7 или же проделать следующие действия:

• поместить курсор в ячейку С7;

• выбрать команду Копировать;

• выделить ячейки С7:Е7;

• выбрать команду Вставить.

Таким образом, введены ограничения для всех поставщи­ков и всех потребителей.

4. Назначение целевой функции.

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

где c_ij - стоимость доставки единицы груза от поставщика i к потребителю j;

x_ij - объем поставки груза от поставщика i к потребителю j.

Для этого необходимо произвести следующие действия:

• поместить курсор в ячейку В15 (после решения задачи в дан­ной ячейке будет находиться значение целевой функции);

• запустить Мастер функций (значок f_x);

• в окне Категория выбрать Математические;

• в окне Функция при помощи спинера выбрать СУММПРОИЗВ;

• нажать кнопку ОК;

• в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.

В задаче целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек В10+E13) и объемов поставок для каждого потребителя (содержимое ячеек В3+Е6). Для этого надо:

• в поле Массив 1 указать адреса В10:Е13;

• в поле Массив 2 указать адреса ВЗ:Е6;

• нажать кнопку ОК - подтверждение окончания ввода адресов массивов.

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

5. Ввод зависимостей из математической модели.

Для этого необходимо выполнить следующие действия:

• выбрать Сервис => Поиск решения;

• поместить курсор в поле Установить целевую (ячейку);

• ввести адрес $В$15 (тем самым мы резервируем ячейку куда после решения задачи помещается значение целевой функции) или поместить курсор в В15, а затем выбрать Поиск решения. При этом в поле адреса целевой ячейки будет автоматически введен адрес $В$15;

• установить направление изменения целевой функции, равное Минимальному значению;

• ввести адреса изменяемых ячеек ВЗ+Е6. Для этого необходимо:

• выбрать Изменяя ячейки;

• ввести адреса $В$3:$Е$6 или щелкнуть на красной стрелке рядом с этим полем, выйти в таблицу с матрицей перевозок, выделить блок ячеек ВЗ+Е6, щелкнуть на красной стрелке и вернуться в блок Поиск решения. Такая последовательность действий приводит к тому, что будут введены нужные адреса.

6. Ввод ограничений задачи.

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

• выбрать Добавить ограничения;

• в поле Ссылка на ячейку ввести адреса $А$3:$А$6;

• в среднем поле установить знак «=». Для этого щелкнуть спинер и выбрать необходимый знак «=»[5];

• в поле Ограничение установить адреса $А$10:$А$13;

• для подтверждения введенного условия нажать кнопку ОК. Далее вводится ограничение, которое реализует условие удов­летворения мощностей всех потребителей (рис. 1.29). Для этого необходимо:

• выбрать Добавить ограничения;

• в поле Ссылка на ячейку ввести адреса $В$7:$Е$7;

• в поле знака выбрать при помощи спинера знак «=»;

• в поле Ограничение установить адреса $В$9:$Е$9;

• нажать кнопку ОК;

• после этого надо вернуться в поле Поиск решения;

• после ввода всех ограничений ввести ОК. На экране появится окно Поиск решения с введенными ограничениями (рис. 1.30).

7. Ввод параметров.

С помощью окна Параметры можно вводить условия для реше­ния оптимизационных задач. В нашей задаче следует установить флажок Неотрицательные значения и флажок Линейная модель. Нажать кнопку ОК. Опять появится диалоговое окно Поиск решения. Далее необходимо:

• щелкнуть по кнопке Параметры;

• выбрать переключатель Линейная модель;

• выбрать переключатель Неотрицательные значения (так как объе­мы поставок груза не могут быть отрицательными);

• нажать кнопку ОК. После этого произойдет переход в поле Поиск решения;

• нажать кнопку Выполнить.

Решение

Решение задачи выполняется сразу же после ввода данных, когда на экране находится диалоговое окно Поиск решения. Нажать кноп­ку Выполнить. На экране появится диалоговое окно Результаты поиска решения (рис. 1.31).

В результате нами был получен оптимальный план перевозок:

План перевозок означает, что:

Х₁₃ = 80 ед. груза следует перевезти от поставщика 1 потре­бителю 3;

Х₂₁ = 200 ед. груза следует перевезти от поставщика 2 потре­бителю 1;

Х₂₃ = 70 ед. груза следует перевезти от поставщика 2 потреби­телю 3;

Х₂₄ = 50 ед. груза следует перевезти от поставщика 2 потребите­лю 4;

Х₃₂ ⁼ 100 ед. груза следует перевезти от поставщика 3 потреби­телю 2;

Х₄₁ = 50 ед. груза следует перевезти от поставщика 4 потребите­лю 1;

Х₄₂ = 0 (2.13Е - 14 = 0) ед. груза следует перевезти от поставщи­ка 4 потребителю 2.

Общая стоимость перевозок = 3200.

1.5.3. Задача о назначениях

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

Исходные параметры задачи о назначениях (табл. 1.10):

n - количество ресурсов;

т - количество работ;

а_i = 1 - единичное количество ресурса A_i, i = 1, …, п (напри­мер: один работник, одно транспортное средство, одна научная тема и т.д.);

b_j = 1 - единичное количество работы B_j, j = 1, …, т (напри­мер: одна должность, один маршрут, одна лаборатория);

c_ij — характеристика качества выполнения работы B_j с помо­щью ресурса A_i (например: компетентность работника i при работе на должности j; время, за которое транспортное средство i пере­везет груз по маршруту j; степень квалификации лаборатории i при работе над научной темой j).

Искомые параметры:

x_ij - факт назначения или неназначения ресурса А_i на ра­боту B_j:

x_ij = 0, если ресурс i не назначен на работу j,

1, если ресурс i назначен на работу j;

- общая (суммарная) характеристика качества распреде­ления ресурсов по работам.

Таблица 1.10

Общий вид транспортной матрицы задачи о назначениях

Ресурсы	Работы	Количество ресурсов
	B1	B2	…	Bm
А2	c11	c12	…	c1m
А2	c21	c22	…	C2m
…	…	…	…	…	…
Аn	cn1	cn1	…	Cnm
Количество работ			...

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

i= 1, …, n,

j= 1, …, m,

x_ij=0 i= 1, …, n,j= 1, …, m.

По сравнению с транспортной задачей процесс приведения задачи о назначениях к сбалансированному виду имеет свои осо­бенности (принимают значение «0» или «1»). Для этого необходимо при вводе ограничений указать тип переменных Двоичное (рис. 1.32).

При решении задач о назначении в Excel необходимо учиты­вать, что переменные x_ij являются булевыми.

1.6. ВОЗМОЖНЫЕ ОШИБКИ ПРИ ВВОДЕ УСЛОВИЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Таблица 1.11