Лабораторная работа: Математические программирование
– В ячейку А3 вводим формулу для ограничения: =8*с1+6*с2.
– В ячейку С1:С2 вводим начальные значения переменных (0:0).
–Выполним команду Сервис > Поиск решения.
Следовательно, план выпуска продукции, включающий изготовление 42,5 изделий В является оптимальным. При данном плане выпуска изделий полностью используется сырье 1-го вида и остаётся неиспользованным 450-237,5=212,5 тонн 2-го вида и 550-295=255 тонн 3-го вида сырья, а стоимость производимой продукции равна 170 у.е.
ЛАБОРАТОРНАЯ РАБОТА №3
по мат.программированию
«Транспортная задача»
Имеются 3 пункта поставки однородного груза А1, А2, А3 и 5 пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1-А3 находится груз соответственно в количестве а1-а3 тонн. В пункты В1-В5 требуется доставить соответственно в1-в5 тонн груза. Стоимости перевозок 1 тонны груза между пунктами поставки и пунктами потребления приведены в матрице D. Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.
|
Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | 12 | 10 | 15 | 12 | 13 | 350 |
| А2 | 16 | 14 | 17 | 10 | 8 | 150 |
| А3 | 15 | 10 | 13 | 14 | 15 | 280 |
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
Математическая модель задачи
Математическая модель транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений
при которых целевая функция
F=12*x11+10*x12+15*x13+12*x14+13*x15+16*x21+14*x22+17*x23+10*x24+8*x25+15*x31+10*x32+13*x33+14*x34+15*x35
принимает минимальное значение.
Опорный план найдем методом северо-западного угла.
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
Для проверки плана на оптимальность необходимо построить систему потенциалов. Для построения системы потенциалов используем условие Ui+Vj=Cij
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2= | V3= | V4= | V5= | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2= | V3= | V4= | V5= | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2= | V3= | V4= | V5= | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2= | V3= | V4= | V5= | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2= | V3= | V4= | V5= | ||
| А1 | 350 | |||||
| А2 | 150 | |||||
| А3 | 280 | |||||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
| Пункты поставки | Пункты потребления | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| Потенциалы | V2=5 | V3=8 | V4=7 | V5=8 | ||
| А1 | 100 | 40 | 160 | 50 | 350 | |
| А2 | 150 | 150 | ||||
| А3 | 80 | 200 | 280 | |||
| Потребн. | 100 | 120 | 200 | 160 | 200 | |
Все незанятые клетки удовлетворяют условию Ui+Vj<=Cij.
Общая стоимость плана составляет
S=100*12+40*10+12*160+13*50+8*150+10*80+13*200=8770 у.е.
Решение задачи на компьютере
| Объём перевозок | ||||||
| 12 | 10 | 15 | 12 | 13 | ||
| 16 | 14 | 17 | 10 | 8 | ||
| 15 | 10 | 13 | 14 | 15 | ||
| Объём перевозок | Всего поставлено | |||||
| 100 | 40 | 0 | 160 | 50 | 350 | |
| 0 | 0 | 0 | 0 | 150 | 150 | |
| 0 | 80 | 200 | 0 | 0 | 280 | |
| 100 | 120 | 200 | 160 | 200 | Всего получено | |
| Затраты на перевозки | ||||||
| 1200 | 400 | 0 | 1920 | 650 | ||
| 0 | 0 | 0 | 0 | 1200 | ||
| 0 | 800 | 2600 | 0 | 0 | 8770 | |
| Microsoft Excel 10.0 Отчет по результатам | |||
| Рабочий лист: [Книга1]Лист2 | |||
| Отчет создан: 17.12.2004 9:44:11 | |||
| Целевая ячейка (Минимум) | |||
| Ячейка | Имя | Исходное значение | Результат |
| $G$13 | 0 | 8770 | |
| Изменяемые ячейки | |||
| Ячейка | Имя | Исходное значение | Результат |
| $A$6 | Объём перевозок | 0 | 100 |
| $B$6 | 0 | 40 | |
| $C$6 | 0 | 0 | |
| $D$6 | 0 | 160 | |
| $E$6 | 0 | 50 | |
| $A$7 | Объём перевозок | 0 | 0 |
| $B$7 | 0 | 0 | |
| $C$7 | 0 | 0 | |
| $D$7 | 0 | 0 | |
| $E$7 | 0 | 150 | |
| $A$8 | Объём перевозок | 0 | 0 |
| $B$8 | 0 | 80 | |
| $C$8 | 0 | 200 | |
| $D$8 | 0 | 0 | |
| $E$8 | 0 | 0 | |