 |
Установить целевую ячейку G2
|
|
|
|
Равной минимальному значению.
Изменяя ячейки: B3:D3.
Ограничения:
B3:D3 целое,
B3:D3 ³0,
E2 £F2.
В качестве критерия используется значение разности (G2) между заказанным объемом и фактически отгруженным. На рис. 2-2б показан результат.
| склад 1 50т |
| склад 2 30т |
| склад 3 40т |
| магазин 1 40т |
| магазин 2 80т |
| 9,8 |
| 40,2 |
| 39,8 |
| 0,2 |
| Рис.2-3а |
Пусть с трех складов требуется развезти закупленные в них грузы в объемах (столбец B на рис. 2-3а) 50, 30 и 40 тонн потребителям в два магазина в объеме 40 и 80 тонн соответственно (D7 и F7). Известна цена (в тыс. руб.) доставки одной тонны груза с каждого склада в каждый пункт доставки (столбцы С и Е). Задача заключается в том, чтобы определить такие объемы перевозок со складов в магазины (области D3:D5 и F3:F5), чтобы стоимость транспортировки (G7) была минимальной. Стоимость перевозки в каждый магазин вычисляется в столбце G: G3=C3*D3+E3*F3, G4=C4*D4+E4*F4, G5=C5*D5+E5*F5. Общая сумма доставки в G7=СУММ(G3:G5). Кроме того, введем функции суммирования (Фактически доставлено) в D6=СУММ(D3:D5), F6= СУММ(F3:DF).
На рис. 2-3б показана таблица в исходном состоянии.
Далее используя Поиск решения, введем параметры:
| A | B | C | D | E | F | G | |
| Магазин 1 | Магазин 2 | Стоим. | |||||
| Грузы на складах (т) | Цена достав. | Груз (тонн) | Цена достав. | Груз (тонн) | доставки | ||
| склад 1 | 0,5 | ||||||
| склад 2 | 2,5 | ||||||
| склад 3 | 1,5 | ||||||
| Факт: | Факт: | ИТОГО: | |||||
| Нужно: | Нужно: | ||||||
| Рис.2-3б | |||||||
| склад 1 | 0,5 | ||||||
| склад 2 | 2,5 | ||||||
| склад 3 | 1,5 | ||||||
| Факт: | Факт: | ИТОГО: | |||||
| Нужно: | Нужно: | ||||||
| Рис.2-3в | |||||||
| склад 1 | 36,67 | 0,5 | 63,33 | 68,3 | |||
| склад 2 | 2,5 | 0,0 | |||||
| склад 3 | 1,5 | 33,33 | 16,67 | 21,7 | |||
| Факт: | Факт: | ИТОГО: | |||||
| Нужно: | Нужно: | ||||||
| Рис.2-3г |
Установить целевую ячейку G7
|
|
|
Равной минимальному значению.
Изменяя ячейки: D3:D5; F3:F5.
Ограничения:
грузы, вывозимые со складов:
B3=D3+F3; B4=D4+F4; B5=D5+F5
условие положительности объемов доставки:
F3:F5>=0; D3:D5>=0
условие выполнения заявок магазинов:
D7=D6; F7=F6
На рис. 2-3в таблица после оптимизации. Видим, стоимость доставки – 130 тыс.
В примере предполагалась перевозка груза, измеряемого в весовых единицах, расфасовка которого при транспортировке безразлична, например, жидкости, песка и т.д. Если же имеется в виду перевозка чего-то крупного и неделимого, например, контейнеров, следует ввести ограничения и на целочисленность перевозимых объектов:
D3:D5=целое и F3:F5=целое.
В рассмотренной задаче подразумевалось, что вес имеющегося для покупателя груза на складах равен весу запрошенного (сбалансированная задача). Это может быть в случае, когда товар предварительно отобран и закуплен у продавца именно в таких объемах на каждом из его складов. Если общий вес товара на складах превышает запрошенный и продавцу безразлично с какого из складов осуществляется его вывоз, вероятно можно найти более дешевое решение. Пусть (рис. 2-3г) на всех складах имеется товар в объемах 100т. Полученный результат равен 90т. руб. Для вычислений здесь лишь потребовалось изменить условия: B3<=D3+F3; B4<=D4+F4; B5<=D5+F5.
|
|
|
Такое решение соответствует интересам покупателя. В интересах перевозчика, наоборот, желательно увеличить транспортные расходы и сделать максимальным значение С7, т.е.
Установить целевую ячейку G7 равной максимальному значению.
Тогда затраты на перевозку составят 280 тыс. руб. и весь товар будет взят со второго склада.
Задача 4. Положим имеется неохваченный связью регион, в котором расположены пять поселков А, Б, В, Г, Д с координатами Xi, Yi. Требуется найти такие координаты Xs, Ys (клетки B7 и C7 на рис. 2-4) расположения телефонной станции, чтобы суммарное расстояние от нее до всех поселков было минимально.
Здесь надо вычислить радиусы (вспомним теорему Пифагора) от станции до каждого из поселков, а затем минимизировать их сумму (D7). После определения положения станции следует построить точечную диаграмму их расположения, где точку Xs, Ys выделить другим цветом. Затем изменить координаты каких-либо поселков и и посмотреть, что произойдет после новой оптимизации. Решите задачу самостоятельно.
| A | B | C | D | E | F | |
| Р1 | Р2 | Р3 | Р4 | |||
| И1 | ||||||
| И2 | ||||||
| И3 | ||||||
| И4 | ||||||
| Стоимость: | ||||||
| И1 | ||||||
| И2 | ||||||
| И3 | ||||||
| И4 | ||||||
| Рис.2- 6 |
Задача 5. Задача о рюкзаке. Имеется 6 предметов (А-Е), о которых известны их вес и цена. Выбрать такие из них, чтобы их вес не превышал 20 кг, а суммарная цена была максимальной. Ответ должен быть получен в двоичной форме 1/0 (выбран/не выбран). В C8 вносим формулу =СУММПРОИЗВ(D2:D7;C2:C7). В окне Поиск решений задаем параметры:
Установить целевую ячейку: C8 равной значению: 20.
Изменяя ячейки: D2:D7. Ограничения: D2:D7=двоичное.
| A | B | C | D | A | B | C | D | - | C | D | |||
| Поселки | X | Y | Радиус | Предмет | Цена | Вес | Выбор | Вес | Выбор | ||||
| А | ? | А | |||||||||||
| Б | ? | Б | |||||||||||
| В | ? | В | |||||||||||
| Г | ? | Г | |||||||||||
| Д | ? | Д | |||||||||||
| S (станция) | ? | Е | |||||||||||
| Рис.2-4 | Всего: | Рис.2-5а | Рис.2-5б |
|
|
|
На рис. 2-5а показана исходная таблица, на рис. 2-5б – после оптимизации. Видим – выбраны предметы А, В, Г, Е.
Задача 6. Задача о назначениях. Имеется (рис. 2-6) четыре вида работ (Р1-Р4) и четыре исполнителя (И1-И2). Известна стоимость выполнения каждой работы каждым из исполнителей (область B2:E5). Нужно назначить каждого работника на одну из работ так, чтобы общая стоимость работ (E7) была минимальна. Создадим таблицу назначений (A8:E11). Первоначально она пуста. Нам понадобятся функция
E7=СУММПРОИЗВ(B8:E11; B2:E5),
а также суммы по вертикали: F8÷F11 и горизонтали: B12÷E12.
В окне Поиск решения вводим параметры:
Установить целевую ячейку: E7 Равной: минимальному значению
Изменяя ячейки: B8:E11
Ограничения: B8:E11=двоичное; B12:E12=1; B8:E11=1
Условия B12:E12=1; B8:E11=1 обеспечивают назначение единственного рабочего на единственную работу.
После оптимизации видим, что общая стоимость работ составила 16 единиц.
| Задание. Найти графическое решение задачи линейного программирования (варианты см. ниже), а затем проверить его, пользуясь средствами Excel. Здесь следует определить максимальное и минимальное значения целевой функции F(А, В) и значения аргументов, при которых они получены. Для всех вариантов: А³0, В³0. |
| 1А+2В£10 | 7А+2В³14 | 3А+1В³9 | 4А+4В£16 | 2А+1В£10 | 2А+2В³4 | 4А-2В£12 | 7А+2В³14 | 2А+1В£10 | 2А+3В£18 |
| -2А+3В£6 | 5А+6В£30 | 1А+2В£8 | 1А+2В³2 | -1А+2В£2 | 6А+8В£48 | -1А+3В£6 | -1А+2В£2 | -2А+3В£6 | 1А-2В£2 |
| 4А+6В³24 | 3А+8В³24 | 1А+6В³12 | -1А+1В£-1 | 2А+4В³8 | 2А-2В£4 | 2А+4В³8 | 4А+6В£24 | 2А+4В³8 | 2А-1В³6 |
| 1А+1В=F | -2А+5В=F | 4А+6В=F | 2А+5В=F | 1А+1В=F | 5А+4В=F | 1А+2В=F | 3А-2В=F | 2А+3В=F | 4А+2В=F |
|
|
|
