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

в общем виде  , где

в нашей задаче 

 

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

Суммарная мощность поставщиков ед Суммарная мощность потребителей

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

 

4. Запишем систему ограничений:

По потребителю: мощности поставщиков меньше мощности потребителей, следовательно, кто-то из потребителей получит груза меньше, чем его потребность .

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

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

                                                  

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

                    ;       

Прямые ограничения .

 

Этап 2.

1. Подготовим форму для ввода исходных данных (Рис 15.),

В нашем примере матрица затрат по доставке груза с конкретной станции  отправления каждому потребителю  вводится в ячейки блока В3:E5. В ячейках В6:E6  указываются потребности в пунктах назначения , мощности поставщиков записаны в блоке F3:F5.

Рис. 15 Ввод исходных данных.

 

2. Зарезервируем изменяемые ячейки, в которых после решения задачи будет находиться оптимальный план перевозок . Размерность этого массива обязательно должна совпадать с размерностью матрицы затрат: выделим блок ячеек I3:L5 (можно ввести в эти ячейки  «1» ) (рис. 16).

 

Рис 16. Создание формы для ввода условий задачи.

 

3.  Введем зависимость для целевой функции (рис. 17). Оптимальное значение целевой функции будет помещено в ячейке В8:
• Курсор в ячейку В8 .
• Мастер функций / Математические / СУММПРОИЗВ (В3:E5; I3:L5)

 

Рис. 17 Ввод зависимости для целевой функции

 

4. Введем зависимости ограничений, стоящие в левых частях ограничений.

- вводим условия реализации  мощностей поставщиков (рис 18.):

• Курсор в ячейку М3.
• Мастер функций / Математические / СУММ (I3:L3)
• Курсор в ячейку М3.
• Растянуть (копировать) ячейку М3 в ячейки М4 и М5.

 

Рис. 18. Ввод зависимостей ограничений  по поставщикам.

- вводим зависимостей ограничений по потребителям (рис. 19):

• курсор в ячейку I6. ;
• Мастер функций / Математические / СУММ (I3:I5)
• Курсор в ячейку I6.
• Растянуть (копировать) ячейку I6 в ячейки J6, K6 и L6.

 

Рис. 19. Ввод зависимостей ограничений  по потребителям.

 

На этом ввод зависимостей закончен.

 

Этап 3. Запуск программы Поиск решений

После выбора команд Поиск решения появится диалоговое окно Поиск решения.

• Назначение целевой ячейки: курсор в поле Установить целевую ячейку. . Левой кнопкой мыши щелкнуть на ячейке В8.
• Ввести направление целевой функции: минимальному значению.
• Ввести адреса искомых переменных: курсор в поле  Изменяя ячейки. . Выделить мышью адреса ячеек I3:L5.
• Ввести ограничения:
• курсор в поле Ограничения .  Выбрать режим Добавить .
• курсор в поле  Ссылка на ячейку
• выбрать мышью ячейки I6:L6
• ввести знак ограничения <=
• курсор в правое окно Ограничение .
• указать мышью адреса В6:E6 
•    

Остальные ограничения ввести аналогично. В результате этих действий окно Поиск решений будет выглядеть, как представлено на рис 20.

Рис. 20. Введены все ограничения.

• Выбрать параметры модели: рис 4.

  

    Этап 4. Выполнить.

 На экране диалоговое окно  Результат поиска решения (рис.18.) .

 

Рис.21. Решение найдено.

 

Найденный план перевозок означает, что общая стоимость перевозок составит 235 ден.ед., если

ед. груза перевести со станции 1 потребителю 3;

ед. груза перевести со станции 2 потребителю 1;

ед. груза перевести со станции 2 потребителю 3;

ед. груза перевести со станции 2 потребителю 4;

ед. груза перевести со станции 3 потребителю 2.

Неудовлетворены будет потребители и , т.к. их потребности составляют 35 и 40 ед. груза соответственно (ячейки С6 и D6), а получат они 20 и 35 ед. (ячейки J6 и К6). Остальные потребители удовлетворены полностью. 

 

Задача  3. Решение задачи о назначениях в среде Excel.

 

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

 

Прода- вец	средний дневной объем продаж продуктов по торговым точкам, у.е.
	56	60	58	63
	35	38	-	45
	40	42	47	45
	62	70	68	67

 

(назначение продавца  на торговую точку недопустимо по медицинским показаниям, т.е. в матрице эффективностей знаком «-» проставлен запрет назнвчений).

 

Решение.

 

Этап 1.

Построим математическую модель  задачи о назначениях.

1.  Введем управляющие переменные:

- факт назначения ресурса  на работу :

, если кандидат  назначен на работу ,

, если кандидат  не назначен на работу .

 

2. Объем продаж  -го продавца на -ой торговой точке равны , , .

   Функция цели - объем продаж по всем продавцам и всем торговым точкам - определяется выражением:

, или

 

 

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

4. Построим систему ограничений.

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

     или

 

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

, или 

Добавим ограничение  - двоичные переменные.

  Кроме того, в задаче имеется дополнительное ограничение: запрет назначения продавца  на торговую точку , которое реализуется ограничением

 

Этап 2.

1. Подготовим форму для ввода исходных данных (Рис. 22.).

В нашем примере матрица эффективности назначений продавцов по торговым точкам вводится в ячейки блока В3:E6.

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

        

        

Рис. 22. Создание формы для ввода условий задачи.

 

2. Введем зависимость для целевой функции (рис. 23).

Оптимальное значение целевой функции  будет помещено в ячейке В8

• Курсор в ячейку В8 .
• Мастер функций / Математические / СУММПРОИЗВ (В3:E5; I3:L5)

Рис. 23 Ввод зависимости целевой  функции

 

2. Введем зависимости ограничений (рис 24.).

- вводим условия по продавцам:

• курсор в ячейку L3. ;
• Мастер функций / Математические / СУММ (H3:K3)
• Скопировать ячейку L3 в L4, L5 и L6.

 

- вводим условия удовлетворения  запросов по торговым точкам:

• курсор в ячейку Н7. ;
• Мастер функций / Математические / СУММ (Н3:Н6);
• Скопировать ячейку Н7 в I7,  J7 и  K7.

                     

Рис 24. Ввод формул для вычисления левых частей ограничений.

 

Этап 3. Запуск программы Поиск решений

• Назначение целевой ячейки: курсор в поле Установить целевую ячейку. Левой кнопкой мыши щелкнуть на ячейке В8.
• Ввести направление целевой функции: максимальному значению.
• Ввести адреса искомых переменных: курсор в поле  Изменяя ячейки. . Выделить мышью ячейки Н3:К6.
• Ввести ограничения:
• курсор в поле Ограничения .  Выбрать режим Добавить .
• курсор в поле  Ссылка на ячейку
• выбрать мышью ячейки в L3: L6
• ввести знак ограничения =
• курсор в правое окно Ограничение .
• Ввести 1
• Выбрать режим Добавить
• курсор в поле  Ссылка на ячейку
• выбрать мышью ячейки в Н7: К7
• ввести знак ограничения =
• курсор в правое окно Ограничение .
• Ввести 1
• Добавим ограничение - двоичные переменные .

 

В результате окно Поиск решения будет выглядеть как показано на рисунке:

        

• Выбрать параметры модели: рис 4.

                    

Этап 4. Выполнить (рис.25.).

 

На экране диалоговое окно  Результат поиска решения.

 

 

Рис.25. Решение найдено.

 

Найденный план назначений означает, что суммарный объем продаж будет  максимальным и  составит 218 у.е., если:

- продавец  назначен на торговую точку ;

- продавец  назначен на торговую точку ;

- продавец назначен на торговую точку ;

- продавец  назначен на торговую точку .

Все ограничения при этом выполнены.