45044

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

Контрольная

Информатика, кибернетика и программирование

Порядок выполнения: Составить математическую модель задачи. Проверить ограничение задачи. При Или Границы области допустимых решений Пересечением полуплоскостей будет являться область координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Русский

2013-11-15

451 KB

8 чел.

Задание 1

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

Требуется: Найти оптимальный ( по критерию максимума доходов) план загрузки судна.

Порядок выполнения:

  1.  Составить математическую модель задачи.
  2.  Построить многоугольник допустимых решений .
  3.  Найти оптимальное решение :

- сравнением значений целевой функции  во всех вершинах многоугольника допустимых решений;

- построением иперемещением линии уровня целевой функции.

4.  Проверить ограничение задачи.

5.  Сравнить полученные решение в заданиях 1 и 2  и сделать выводы.

Вариант

Регистров.

Грузоподъёмность

Судна

Объём перевозок

Удельные

Погрузочные объёмы

Время погрузки одной тонны груза

Наличие груза в порту

Плановое время погрузки судна

Доходная ставка

17

2100

2150

0.45

1.3

0.9

2.3

1110

3000

40

140

150

Решение:

  1.  Составим математическую модель .  Пусть    количество первого груза (т.) по условию  Плановое время погрузки судна 40 часов (2400 минут) , при этом время погрузки 1 т. , первого груза  0,9 мин/т. , второго 2,3 мин/т.     ,  далее объем трюмов судна = 2150 , а удельные погрузочные объемы грузов : первого груза  0,45   , второго 1,3     , а так же следуя из того что грузоподъёмность судна равна 2100 т. , а имеем в наличии первого груза 1110 т. , второго 3000 т.   . Теперь введем целевую функцию – по критерию max доходов , которая составляет    , то есть получаем целевую функцию и систему ограничений:                                                                                          .                                                                                                                                                                                                  .
  2.     Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).       

При          

  

При        

 

  

Или

Границы области допустимых решений

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений:

                       

  1.     

а)  При     

    При     

    При     

б)  Рассмотрим целевую функцию задачи F = 140x1+150x2 → max. 
Построим прямую, отвечающую значению функции F = 0: F = 140x
1+150x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

 

Равный масштаб

Область допустимых решений представляет собой треугольник.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (4) и (1), то ее координаты удовлетворяют уравнениям этих прямых:
x
2=0
1110x
1+3000x2≤2100

Решив систему уравнений, получим: x
1 = 1.89, x2 = 0
Откуда найдем максимальное значение целевой функции:

  1.  Проверим ограничение задачи.

Составим двойственную задачу к прямой задаче.

    

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Для решения двойственной задачи используем вторую теорему двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
1110*1.89 + 3000*0 = 2100 = 2100
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y
1>0).
0.45*1.89 + 1.3*0 = 0.85 < 2150
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y
2 = 0
0.9*1.89 + 2.3*0 = 1.7 < 2400
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y
3 = 0
С учетом найденных оценок, новая система примет вид:

    

Решая систему  графическим способом , находим оптимальный план двойственной задачи :

Область допустимых решений представляет собой многоугольник.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (3) и (1), то ее координаты удовлетворяют уравнениям этих прямых:
x
2=0
1110x
1≥140

Решив систему уравнений, получим: x
1 = 0.1261, x2 = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 2100*0.1261 + 0*0 = 264.86
Поскольку функция цели F(x) параллельна прямой
 (1), то на отрезке AA функция F(x) будет принимает одно и тоже минимальное значение.
Для определения координат точки A решим систему двух линейных уравнений:
x
2=0
1110x
1≥140

Решив систему уравнений, получим: x
1 = 0.1261, x2 = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 2100*0.1261 + 0*0 = 264.86
y
1 = 0.13
Z(Y) = 2100*0.13 = 264.86
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.

  1.  Решим прямую задачу линейного программирования   симплексным методом, с использованием симплексной таблицы.

Определим максимальное значение целевой функции F(X) = 140x1+150x2 при следующих условиях-ограничений.

1110x1+3000x2≤2100

0.45x1+1.3x2≤2150

0.9x1+2.3x2≤2400

1110x1 + 3000x2 + 1x3 + 0x4 + 0x5 = 2100

0.45x1 + 1.3x2 + 0x3 + 1x4 + 0x5 = 2150

0.9x1 + 2.3x2 + 0x3 + 0x4 + 1x5 = 2400

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,2100,2150,2400)

Базис

В

x1

x2

x3

x4

x5

x3

2100

1110

3000

1

0

0

x4

2150

0.45

1.3

0

1

0

x5

2400

0.9

2.3

0

0

1

F(X0)

0

-140

-150

0

0

0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (3000) и находится на пересечении ведущего столбца и ведущей строки.

Базис

В

x1

x2

x3

x4

x5

min

x3

2100

1110

3000

1

0

0

0.7

x4

2150

0.45

1.3

0

1

0

1653.85

x5

2400

0.9

2.3

0

0

1

1043.48

F(X1)

0

-140

-150

0

0

0

0

 

После преобразований получаем новую таблицу:

Базис

В

x1

x2

x3

x4

x5

x2

0.7

0.37

1

0.0003

0

0

x4

2149.09

-0.031

0

-0.0004

1

0

x5

2398.39

0.049

0

-0.0008

0

1

F(X1)

105

-84.5

0

0.05

0

0

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.37) и находится на пересечении ведущего столбца и ведущей строки.

Базис

В

x1

x2

x3

x4

x5

min

x2

0.7

0.37

1

0.0003

0

0

1.89

x4

2149.09

-0.031

0

-0.0004

1

0

-

x5

2398.39

0.049

0

-0.0008

0

1

48946.73

F(X2)

105

-84.5

0

0.05

0

0

0

 

После преобразований получаем новую таблицу:

Базис

В

x1

x2

x3

x4

x5

x1

1.89

1

2.7

0.0009

0

0

x4

2149.15

0

0.0838

-0.0004

1

0

x5

2398.3

0

-0.13

-0.0008

0

1

F(X2)

264.86

0

228.38

0.13

0

0

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис

В

x1

x2

x3

x4

x5

x1

1.89

1

2.7

0.0009

0

0

x4

2149.15

0

0.0838

-0.0004

1

0

x5

2398.3

0

-0.13

-0.0008

0

1

F(X3)

264.86

0

228.38

0.13

0

0

Оптимальный план можно записать так:

x1 = 1.89

x4 = 2149.15

x5 = 2398.3

F(X) = 140*1.89 = 264.86 руб.

Вывод:  При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x
1>0)
1110*0.13 + 0*0 + 0*0 = 140 = 140
3000*0.13 + 0*0 + 0*0 = 378.38 > 150
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x
2 = 0


 

А также другие работы, которые могут Вас заинтересовать

21889. Организация МЧС, история, этапы развития 107 KB
  Все это представляет объективную необходимость усиления внимания к решению проблем связанных с чрезвычайными ситуациями причем как показал опыт ликвидации последствий аварии на Чернобыльской АЭС землетрясения в Армении других чрезвычайных ситуаций на самом высоком государственном уровне. В целях прогнозирования предотвращения и ликвидации последствий ЧС обеспечения постоянной готовности органов государственного управления к быстрым и эффективным действиям в экстремальных условиях в 1990 году был создан Российский корпус спасателей...
21890. Пожарная профилактика 216.5 KB
  Первичные средства пожаротушения и порядок их использования 3ий вопрос Мероприятия проводимые в целях повышения противопожарной безопасности организаций объектов. Планирование противопожарных мероприятий ГО на объекте 4ый вопрос Назначение задачи и организация противопожарной службы и ее формирований Организационнометодические указания В вводной части следует обратить внимание на то что сегодня пожары превращаются в одну из главных опасностей для человечества которые приводят к массовой гибели людей и большому материальному...
21891. ПРИРОДНЫЕ (ЛАНДШАФТНЫЕ) ПОЖАРЫ 175.49 KB
  При подземных пожарах горит торф залегающий под лесными массивами. Возникновение и распространение подземных пожаров обычно связано с низовыми лесными пожарами при которых огонь отдельными очагами заглубляется в слой торфа на наиболее подсохших участках чаще всего у стволов деревьев а затем постепенно распространяется в стороны. Переход низового пожара на полог древостоя происходит в насаждениях с низко опущенными кронами в разновозрастных насаждениях а также при обильном хвойном подросте. Древостой после верхового пожара как правило...
21892. Устойчивость функционирования объектов экономики и территорий в условиях чрезвычайных ситуаций 114 KB
  Основные направления и мероприятия по повышению устойчивости функционирования народного хозяйства страны в военное время . Этот документ не отменен и сегодня и является фундаментом для построения системы современных взглядов на проблемы устойчивости в рамках созданной в 1992 г. Подготовка народного хозяйства к устойчивому функционированию в чрезвычайных ситуациях это же касается и отрасли территории территории объекта независимо от формы собственности и сферы деятельности комплекс экономических организационных мероприятий...
21893. ХАРАКТЕРИСТИКА ЧС ПРИРОДНОГО ХАРАКТЕРА 346.5 KB
  Ветровой нагон подъём уровня воды вызванный воздействием ветра на водную поверхность обычно происходящий в морских руслах крупных рек а также на больших озёрах и водохранилищах. БУРИ УРАГАНЫ И СМЕРЧИ Ураганы бури смерчи метеорологические опасные явления характеризующиеся высокими скоростями ветра. Ураган возникает когда скорость ветра превышает 33 м с 120 км ч обладает большой кинетической энергией: ломает деревья переворачивает автомобили разрушает строения. Погода при этом малооблачная сухая со слабыми ветрами.
21894. Обеззараживание. Виды обеззараживания 91.5 KB
  Моющие растворы Жировые мыла Синтетические вещества Синтетические моющие вещества обладают хорошей моющей способностью в любой среде при невысоких температурах. СПОСОБЫ И ТЕХНИЧЕСКИЕ СРЕДСТВА ОБЕЗЗАРАЖИВАНИЯ Для обеззараживания используют механический физический физикохимический и химический способы. Дезактивация Механический способ применяется для различных грунтов и включает: сметание срезание вспашка засыпка заражённого грунта удаление радиоактивной пыли...
21895. Организация государственной системы предупреждения и ликвидации ЧС 1.66 MB
  В соответствии с законом О защите населения и территорий от ЧС природного и техногенного характера в РФ функционирует Единая государственная система предупреждения и ликвидации стихийных бедствий РСЧС. Организация системы РСЧС РСЧС состоит из территориальных и функциональных подсистем и имеет 5 уровней: федеральный региональный уровень субъекта федерации местный уровень и объектовый. Территориальная подсистема РСЧС предназначена для предупреждения и ликвидации ЧС на подведомственной территории. Функциональные подсистемы РСЧС создаются в...
21896. ПРИНЦИПЫ И СПОСОБЫ ЭВАКУАЦИИ 61 KB
  ПРИНЦИПЫ И СПОСОБЫ ЭВАКУАЦИИ 1. В этих случаях почти всегда приходится прибегать к эвакуации. ПРИНЦИПЫ И СПОСОБЫ ЭВАКУАЦИИ Эвакуация в чистом виде бывает редко она как правило сочетается с другими защитными мероприятиями: укрытием проведением противорадиационных медицинских противопожарных инженерных работ. Количество людей подлежащих эвакуации каждый раз определяется местными органами власти с учетом рекомендаций штабов ГО и ЧС исходя из условий характера и масштабов чрезвычайной ситуации.
21897. АС и ДНР. Спасательные работы в очагах поражения включают 30.5 KB
  Спасательные работы в очагах поражения включают: разведку маршрутов движения и участков объектов работ; локализацию и тушение пожаров на маршрутах движения и участках объектах работ; розыск пораженных и извлечение их из поврежденных и горящих зданий загазованных и задымленных помещений завалов; вскрытие разрушенных поврежденных и заваленных защитных сооружений и спасение находящихся в них людей; подачу воздуха в заваленные защитные сооружения с поврежденной фильтровентиляционной системой; оказание первой медицинской и первой врачебной...