Решение транспортной задачи

Рассмотрим задачу, приведенную в примере 6.8.

В качестве проектных параметров были приняты - x_ij (i=1, 2, 3, 4,; j=1, 2, 3) - количество цемента, перевозимого с i -го завода на j -ый ЖБК.

Известна Cij - стоимость перевозки единицы продукта с i -го завода на j -ый ЖБК.

Целевая функция:

Z_min =3 x ₁₁+5 x ₁₂+7 х ₁₃+11 х ₁₄+

+x ₂₁+4 x ₂₂+6 x ₂₃+3 x ₂₄+

+5 x ₃₁+8 x ₃₂+12 x ₃₃+7 x ₃₄ (6.32)

Ограничения:

x ₁₁ + x ₁₂ + х ₁₃+ х ₁₄ = 150,

x ₂₁ + x ₂₂ + x ₂₃+ x ₂₄ = 130,

x ₁₁ + x ₂₁ + х ₃₁ = 150, (6.33)

x ₁₂ + x ₂₂ + x ₃₂ = 120,

x ₁₃ + x ₂₃.+ x ₃₃ = 80,

x ₁₄ + x ₂₄.+ x ₃₄ = 50,

x_ij ³ 0 (i =1, 2, 3; j =1, 2, 3, 4).

Последовательность действий:

1. Подготовим таблицу, как показано на рис.6.17. Ячейки, содержащие целевую функцию I10 и изменяемые ячейки (проектные параметры x_ij, i =1, 2, j =1, 2, 3) D4: D6, F4: F6; Н4: Н6, J4: J6, тонированы. Для контроля счета в изменяемые ячейки введем какие-либо числа, например единицы. Эти значения проектных параметров можно рассматривать как начальное приближение решения.

2. Введем исходные данные (цены перевозок) из таблицы примера 6.8 в соответствующие ячейки рис.6.17.

3. В ячейку I10 введем целевую функцию:

I10 = СУММПРОИЗВ(C4: C6; D4: D6) +

+СУММПРОИЗВ(E4: E6; F4: F6)+

+СУММПРОИЗВ(G4: G6; Н4: Н6;)+

+СУММПРОИЗВ(I4: I6; J4: J6)

4. Подготовим таблицу ограничений. Для этого в ячейку D10 введем формулу: D10=D4+F4+H4+J4-B4, а затем скопируем ее вниз на две строки.

5. Для ввода следующих четырех ограничений воспользуемся автосуммированием. Например: D13=СУММ(D4: D6)-D7, аналогичные формулы запишем в ячейки D15: D17.

Рис.6.17. Схема решения транспортной задачи

6. Последнюю строку ограничений добавим непосредственно в окне «Поиск решения».

7. Выделим ячейку I10 (целевая ячейка) и выберем команду меню Данные\Поиск решения. В появившемся окне «Поиск решения» сделаем установки, как показано на рис.6.18. Для ввода ограничений используем кнопку Добавить.

Рис.6.18. Окно «Поиск решения»

Результат счета приведен на рис.6.19, минимальная стоимость перевозок составляет 2040 у.е.

Рис.6.19. Результаты решения транспортной задачи

Контрольные вопросы

1. Математическая постановка задач оптимизации в строительстве.

2. Классификация задач математического программирования.

3. Общая постановка задачи линейного программирования.

4. Геометрический метод решения задач линейного программирования.

5. В чем заключается идея Симплекс-метод решения задач линейного программирования.

6. Основные задач линейного программирования в сфере проектирования и управления строительным производством

Литература

1. Антонов В.И., Копелевич Ф.И. Элементарная математика для первокурсника. 1-е изд., - СПб.: Лань, 2013. – 112с.

2. Вержбицкий В.М. Вычислительная и линейная алгебра. - М.: Высшая школа, 2009. - 351с.

3. Вержбицкий В.М. Основы численных методов. - М.: Высшая школа, 2009. - 840с.

4. Гельфанд И.М. Лекции по линейной алгебре. М.: Добросвет, 2009. – 320с.

5. Горлач Б.А. Линейная алгебра: учебное пособие. – СПб.: Лань, 2012. - 480с.

6. Демидович Б.П., Марон И.А. Основы вычислительной математики. СПб.: Лань, 2007.-664с.

7. Золотов А.Б., Акимов П.А., Сидоров В.Н., Мозгалева М.Л. Информатика в строительстве (с основами численного моделирования). – М.: Архитектура – С, 2010. – 336с.

8. Кашеварова Г.Г., Пермякова Т.Б. Численные методы решения задач строительства на ЭВМ. – Пермь: ПГТУ, 2007. – 352с.

9. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах — М.: Высш. шк., 2008. — 480с.

10. Попов А. EXCEL. Практическое руководство. МГУТА, 2007. - 301с.

11. Самарский А. А. Введение в численные методы. Учебное пособие для вузов. 3-е изд., стер. — СПб.: Издательство «Лань», 2005. — 288с.

12. Турчак Л.И. Плотников П.В. Основы численных методов: Учебное пособие. 2-е изд. – М.: Физматлит, 2002. – 304с.

13. Щипачев В.С. Высшая математика. – СПб.: Лань, 2013. – 384с.

Оглавление

Предисловие. 3

Введение. 6

Глава 1.Основные понятия матричного исчисления. 16

1.1. Матрицы и векторы. 16

1.2. Матрицы специального вида. 18

1.3. Действия над матрицами. 21

1.4. Нормы матрицы и вектора. 23

1.5. Функции MS Excel для операций над матрицами. 25

Глава 2.Численные методы решения нелинейных уравнений.. 27

2.1. Первый этап. Отделение корней. 29

2.2. Второй этап. Этап уточнения корня. 33

2.2.1.Метод половинного деления (бисекции) 34

2.2.2.Метод хорд. 37

2.2.3.Метод Ньютона (метод касательных) 40

2.2.4.Модифицированный метод Ньютона. 43

2.3.Реализация численных методов решения нелинейных уравнений средствами приложения MS Excel 44

2.3.1. Решение нелинейных уравнений с использованием надстройки «Подбор параметра» 47

Глава 3.Численные методы решения систем линейных алгебраических уравнений 50

3.1. Системы линейных алгебраических уравнений. 50

3.2. Прямые методы решения систем линейных алгебраических уравнений 53

3.2.1. Метод Гаусса. 53

3.2.2. Метод прогонки. 58

3.3. Итерационные методы решения систем линейных алгебраических уравнений 60

3.3.1. Метод Якоби (простых итераций) 60

3.3.2. Метод Гаусса – Зейделя. 65

3.3.3. Условия сходимости итерационного процесса. 67

3.5. Устойчивость решения СЛАУ относительно исходных данных. 70

3.6. Примеры решения СЛАУ с использованием электронных таблиц MS Excel 74

3.6.1. Реализация метода Гаусса. 74

3.6.2. Решение СЛАУ с помощью надстройки «Поиск решения». 76

3.6.3. Реализация метода Якоби средствами приложения Excel 79

3.6.4. Реализация метода прогонки средствами приложения Excel 82

Глава 4.Численное интегрирование. 85

4.1. Квадратурные формулы прямоугольников. 88

4.2. Квадратурная формула трапеций. 91

4.3. Квадратурная формула Симпсона. 92

4.4. Реализация методов численного интегрирования средствами приложения MS Excel 95

Глава 5.Аппроксимация. 99

5.1. Задачи аппроксимации. 99

5.2. Интерполирование функций. 100

5.2.1. Постановка задачи интерполирования. 100

5.2.2. Интерполяционная формула Лагранжа. 102

5.3. Среднеквадратичное приближение функций. 105

5.3.1. Постановка задачи. 105

5.3.2. Метод наименьших квадратов. 109

5.3.3. Линейная эмпирическая формула. 110

(линейная регрессия) 110

5.3.4. Коэффициент корреляции. 113

5.3.5. Квадратичное (параболическое) приближение. 114

5.3.6. Эмпирические формулы с двумя параметрами (метод выравнивания) 115

5.4. Решение задач аппроксимации с помощью электронных таблиц Excel 118

5.4.1. Построение уравнений регрессии методом наименьших квадратов с использованием надстройки «Поиск решения» 118

5.4.2. Построение линейной эмпирической формулы с использованием встроенных функций ЛИНЕЙН и ТЕНДЕНЦИЯ 122

Глава 6.Численные методы оптимизации.. 125

6.1.Общие сведения. 126

6.1.1. Математическая модель задачи оптимизации. 126

6.1.2. Классификация задач математического программирования. 130

6.2. Постановка задачи оптимального проектирования. 132

6.3.Задачи линейного программирования. 134

6.3.1.Общая постановка задачи. 135

6.3.2.Геометрический смысл системы линейных неравенств. 137

6.3.3.Геометрический метод решения задач линейного программирования 141

6.3.4.Симплекс-метод решения задач линейного программирования.... 148

6.4. Примеры задач линейного программирования в сфере проектирования и управления строительным производством 151

Задача об оптимальном плане выпуска продукции 154