Моделирование и оптимизация автомобильных дорог

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

ресурс рабочего времени каждого типа оборудования, то:

 

;; (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>