Автор: Пользователь скрыл имя, 27 Марта 2014 в 09:47, контрольная работа
Построить геометрическую интерпретацию задачи линейного программирования (программу реализовывать в редакторе MS Excel или MathCad) и найти решение задачи.
Содержание
f(x) = 6х1 + 2x2 → max(min)
Решение
Необходимо найти максимальное значение целевой функции F = 6x1+2x2 → max, при системе ограничений:
x1-x2≤4 (1)
-x1+3x2≤6 (2)
x1+x2≤3 (3)
x1≥0 (4)
x2≥0 (5)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Или
Рис.1 Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рис. 2 Границы области многоугольника решений
Рассмотрим целевую функцию задачи F = 6x1+2x2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 6x1+2x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Рис. 3. Область допустимых решений max
Область допустимых решений представляет собой многоугольник.
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (4) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
x2=0
x1+x2≤3
Решив систему уравнений, получим: x1 = 3, x2 = 0
Откуда найдем максимальное значение целевой функции:
F(X) = 6*3 + 2*0 = 18
Решение получилось целочисленным.
Рассмотрим целевую функцию задачи F = 6x1+2x2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 6x1+2x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Рис. Область допустимых решений min
Область допустимых решений представляет собой многоугольник.
Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:
x2=0
x1=0
Решив систему уравнений, получим: x1 = 0, x2 = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 6*0 + 2*0 = 0
Решим задачу линейного программирования на нахождение максимального значения в форме симплекс таблиц с помощью Microsoft Excel.
По условию задачи составим начальный план в Microsoft Excel. Выделим сначала ячейки под набор ограничений, под искомые переменные коэффициенты, значение целевой функции. Необходимо задать значение целевой функции как сумму произведений искомых переменных на коэффициенты. Так же надо сделать и для набора ограничений.
Начальный план решения задачи в Microsoft Excel дан на рисунке 1.
Рисунок 1 - Начальный план решения задачи
Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ, которая вычисляет сумму попарных произведений двух или более массивов.
Рисунок 2 – Ввод зависимостей
Вызываем Поиск решения, устанавливаем ячейки, которые будут изменяться и устанавливаем ячейку целевой функции, это представлено на рисунке 3.
Рисунок 3 – Поиск решений
Вводим набор ограничений и нажимаем кнопку «выполнить».
Рисунок 5 – Результат поиска решения целевой функции max
Таким образом, получим: x1 = 3, x2 = 0
Откуда найдем максимальное значение целевой функции:
F(X) = 6*3 + 2*0 = 18
Решение получилось целочисленным.
Рассмотрим целевую функцию задачи F = 6x1+2x2 → min.
Аналогично определим минимальное значение целевой функции. Результат представлен на рис. 6.
Рисунок 5 – Результат поиска решения минимального значения целевой функции
Таким образом, получим: x2=0, x1=0
Откуда найдем минимальное значение целевой функции:
F(X) = 6*0 + 2*0 = 0
Решение получилось целочисленным.
Имеется несколько заводов - поставщиков, производящих некоторые изделия, и несколько потребителей, использующих эти изделия. Мощность поставщиков, потребности потребителей и стоимость доставки одного изделия от любого поставщика любому потребителю приведены в заданиях. Определить план перевозок, имеющих минимальную стоимость для чего:
варианта 8 |
Потребители |
Мощность | |||||
1 |
2 |
3 |
4 |
5 | |||
Завод |
1 |
4 |
21 |
12 |
9 |
11 |
210 |
2 |
17 |
1 |
11 |
5 |
3 |
210 | |
3 |
20 |
8 |
25 |
15 |
23 |
230 | |
4 |
23 |
10 |
24 |
6 |
5 |
230 | |
Заказ |
220 |
220 |
220 |
110 |
110 |
||
Решение
Создаем таблицу с формулами, которые связывают план, ограничения и целевую функцию.
Рис. 1 Исходные данные
Расчет ограничений транспортной задачи необходимо выполнять в нижеприведенной последовательности: в ячейки столбика І14:І17 и ячейки стороки D18:H18 вводим зависимость с помощью функции СУММ Мастера функций. Для этого в соответствующем диалоговом окне вводим адрес строки. На рис. 2 представлен адрес для ячейки D 18. Аналогичные расчеты следует выполнить для всех пунктов производства и потребления.
Рис. 2 Ввод ограничительных уравнений
Затем в ячейку D20 вводим целевую функцию (рис. 3).
Рис. 3. Ввод целевой функции
Затем настраиваем программу «Поиск решения» как показано на рис. 4.
Рис. 4. Этап «Поиск решения»
В появившемся окне "Поиск решения" установим курсор на кнопку "Выполнить" и щелкним левой клавишей мыши.
После того как на рабочем листе появилось решение (рис.5) в появившемся диалоговом окне "Результаты поиска решения" (рис.6) установим курсор на переключатель "Восстановить исходные значения" и щелкним левой клавишей мыши. Для завершения расчетов щелкним на кнопке ОК.
Рис. 5. Результаты этапа «Поиск решения»
Рис.6 Этап «Поиск решения»
Таким образом, мы нашли решение рассматриваемой транспортной задачи.
На рис. 7 показана диаграмму, иллюстрирующую оптимальный план перевозок.
Рис. 7 Диаграмма, иллюстрирующая оптимальный план перевозок
Согласно рисунку 7 видно, что потребителю 1 220 ед доставит завод 1 и 10 единиц завод 3. Потребителю 2 – 220 единиц отгрузит завод 3, потребителю 3 – 210 ед. отгрузит завод 2 и 10 единиц – завод 4. Потребителю 4 все 110 ед. продукции доставит завод 4, а потребителю 5 – завод 5.