Моделирование и оптимизация автомобильных дорог
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ресурс рабочего времени каждого типа оборудования, то:
;; (1.4.)
Критерием оптимальности в данной задаче является прибыль, полученная от реализации продукции. Поэтому целевая функция имеет вид:
(1.5.)
2.3. Решение задачи симплекс-методом
Математическая модель задачи имеет вид:
Для упрощения расчетов заменяем ограничения (1.1.) условием неотрицательности:
Перейдем к минимизации целевой функции, изменив знаки всех ее коэффициентов на противоположные:
Выше приведенными преобразованиями исходная задача сведена к основной задаче линейного программирования:
(1.6.)
Составим таблицу, состоящую из коэффициентов целевой фикции и системы ограничений (1.6.):
Таблица 2
Базисная переменнаяСвободные членыСвободные переменныех1х2х3у1250 11900,21 4,760,20 0,950,14 0,67у2300 -1900,16 -0,760,14 -0,150,11 -0,106у3320 -2850,24 -1,140,19 -0,230,14 -0,16W0 -95208 -38,087 -7,629 -5,33
В качестве разрешающего столбца выбираем х3, разрешающий элемент 0,21 (он находится на пересечении столбца х1 и строки у1). Затем выполняются вычисление обратной величины разрешающего элемента:
Все элементы разрешающей строки, кроме разрешающего, умножаются на ?. Результаты записывают в нижней части соответствующей ячейки. Все элементы разрешающей графы, кроме разрешающего, умножаются на (-?), и результаты записывают в нижних частях соответствующих ячеек.
Подчеркивают в разрешающей строке все верхние числа (250; 0,20; 0,14), а в разрешающей графе - все нижние числа (-0,76; -1,14; -38,08).
Для каждого из элементов, не принадлежащих ни к разрешающей строке, ни к разрешающей графе, записывают в нижней части соответствующей ячейки произведения подчеркнутых чисел, стоящих в той же строке и в той же графе, что и данный элемент.
Затем переписываем таблицу, поменяв местами свободную переменную х1 и базисную у1, а элементы разрешающей строки и разрешающей графы меняют на числа, стоящие в нижних частях соответствующих ячеек, каждый из остальных элементов - на сумму чисел, стоящих в верхней и нижней частях той же ячейки (см. таблицу 3).
Таблица 3
Базисная переменнаяСвободные членыСвободные переменныеу1х2х3х11190 17734,76 7,090,95 1,420,67 1,49у2110 -7,14-0,76 - 0,03-0,01 -0,0060,004 -0,006у335 -35,7-1,14 0,14-0,04 -0,03-0,02 0,03W-9520 -6688-38,08 -26,75-0,62 -5,343,77 -5,62
Так как в строке W есть положительный элемент 3,77, то оптимальное решение еще не получено и поиск решения продолжается в вышеизложенной последовательности, начиная с отыскания разрешающего элемента. Разрешающим элементом будет 0,67, обмениваемые переменные - х2 и х1. Промежуточные расчеты приведены в табл. 4.
Таблица 4
Базисная переменнаяСвободные членыСвободные переменныеу1х2х3х111737,091,421,49у2102-0,79-0,016-0,002у30-1-0,010,01W-16208-64,83-5,96-5,62
Так как все элементы в строке W отрицательны, то оптимальное решение получено и имеет вид:
и
Значение целевой функции определяется подстановкой найденных значений переменных в выражение (1.5.):
тыс. руб.
Полученное значение есть максимальная величина прибыли, которую получит предприятие, если будет выпускать продукцию П1, при условии непревышения ресурсов времени по всем типам оборудования.
.4 Решение с использованием Excel.
В ней линейные математические модели могут быть оптимизированы через надстройку Поиск решения. Сначала задаем количество единиц продукции (см. табл. 5).
Таблица 5
ABC1x1x2x32000
Зададим выражения для определения длительности работы каждого типа оборудования (см. табл. 6).
Таблица 6
АВС3T1T2T34=0,21*А2+0,20*В2+0,30*С2=0,16*А2+0,14*В2+0,11*С2=0,24*А2+0,19*В2+0,14*С2
Далее задаем целевую функцию (см. табл. 7).
Таблица 7
АВ5W=8*А2+7*В2+9*С2
Затем заходим в сервис > выбираем поиск решения > появляется окно поиска решения:
Установить целевую ячейку: задаем $В$5;
Равной: выбираем максимальному значению;
Изменяя ячейки: задаем $A$2:$C$2;
Ограничения: задаем
$A$2>=150, $В$2>=200, $С$2>=400, $A$4<=250, $В$4<=300, $С$4<=320
Далее нажимаем Выполнить > Сохранить найденное решение нажимаем ок и получаем значения (см. табл. 8).
Таблица 8
АВС1x1x2x32428,57200,00400,003T1T2T34250,00140,57196,865W8428,57
По таблице мы видим, что максимальное значение целевой функции (суммарная прибыль от реализации продукции) 8428,6 тыс. руб. Достигается при следующих объемах выпусках продукции: П1 = 429 ед., П2 = 200 ед., П3 = 400 ед. При этом соблюдены условия выполнения плана выпуска всех видов продукции и ограничения ресурсов рабочего времени оборудования. Сравнивая результаты, делаем вывод, что более точный результат выходит с использованием программы компьютера.
3. ОПТИМИЗАЦИЯ ПЕРЕВОЗОК
.1 Исходные данные
Имеется 3 пункта, производящих некоторую продукцию. Затраты на производство единицы продукции в iом пункте равна аi , а максимально возможный объем ее выпуска составляет bi единиц в год, i = 1, 2 … m. Изготавливаемая продукция должна быть распределена между потребителями. Доставка единицы продукции от iого пункта производства к jому потребителю обходится в cij руб. j = 1, 2 …n.
(3.1.)
(3.2.)
Потребность в продукции для jого потребителя составляет di единиц в год. Требуется составить схему перевозок так, чтобы годовые затраты на производство и перевозку были минимальными.
3.2 Составление математической модели
Обозначим через yi искомый объем выпуска продукции в iом пу?/p>