10663

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

Лабораторная работа

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

Лабораторная работа 13 Решение задач линейного программирования. Цель работы. Научиться решать одну из задач оптимизации: исходя из конкретной ситуации составить совокупность линейных ограничений в виде системы неравенств а также функцию цели. Для этой фун

Русский

2013-03-30

708 KB

4 чел.

Лабораторная  работа  13

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

Цель работы.  Научиться решать одну из задач оптимизации: исходя из конкретной ситуации, составить совокупность линейных ограничений в виде системы неравенств, а также функцию цели. Для этой функции найти оптимальное решение.

Теоретические положения. Если записать зависимость критерия    от варьируемых параметров  , а также записать определенные ограничения на допустимую область их изменения, то мы придем к некото-рой математической модели задачи оптимизации:  

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

                          (1)

и доставляют данной функции

                                              (2)

наименьшее (или наибольшее) значение.

Здесь:

 -   называется  целевой функцией,

- условия  (1) – ограничениями,

- каждый набор переменных, удовлетворяющий (1), называ-ется допустимым решением,

- допустимое решение, минимизирующее или максимизирующее функцию  , называется оптимальным.  

Если все функции:   - линейны, то имеем задачу линейного програм-мирования. Для простоты иллюстрации рассмотрим  наборы допустимых решений, состоящие  только из двух переменных  .  

Порядок выполнения работы.   

- переписать задание в соответствием со своим вариантом,

- исходя из условия, составить систему ограничительных неравенств,

- в зависимости от конечного результата задания записать функцию цели ,

- в координатной плоскости  построить все линии, входящие в систему неравенств,

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

- построить линию уровня  функции ,

- перемещая эту линию в направлении ее возрастания (или убывания), найти последнюю (или первую) точку, через которую пройдет линия уровня  и которая еще будет принадлежать многоугольнику допустимых решений,

- найти координаты    и   этой точки, соответствующей пересечению двух прямых,

- подставив эти координаты в функцию цели , найдем ее значение, которое должно соответствовать максимальному доходу (или минимальным затратам – в зависимости от содержания задачи),

- если рядом с оптимальной точкой имеются другие – “ подозрительные“, найти их координаты, подставить в функцию цели и сравнить результаты с первым,

- сделать выводы по работе.

Исходные  данные к работе.  

       Для  вариантов:  1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.

Задача о выпуске продукции.  

 

    1.  Изготовление продукции двух видов   и   требует использования четырех видов сырья:    и  . Запасы сырья составляют соответст-венно    и   условных единиц.. Количество единиц сырья,  необхо-димое для изготовления единицы каждого из видов продукции известно и задается таблицей:

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=22.1

=1.8

=2.9

=14.3

=1.9

=1.0

=14.0

=0

=3.0

=17.2

=3.3

=0.2

Доход

=7.6

=4.9

Здесь  есть количество сырья вида  , необходимое для изготовления продукции вида  ;   - доход, полученный предприятием от реализации единицы каждого вида продукции. Требуется составить такой план выпуска продукции   и  , при котором   доход предприятия от реализации всей продукции оказался бы   максимальным.

        Для  вариантов:  2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.

   Задача о рационе питания.

     2.   При откорме животное должно получить не менее    и   единиц питательных веществ видов    и   . Для составления рациона использу-ются два вида корма:    и   . Содержание количества единиц  питатель-ных веществ в каждом корме, а также стоимость  1 кГ корма приводятся в таблице:

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.6

=3.2

=1.2

=7.4

=1.1

=2.4

=13.1

=1.2

=6.5

Стоимость

=5.4

=7.1

Здесь  есть количество питательного вещества  вида    содержащееся в корме  ;    - стоимость 1 кГ корма. Необходимо составить дневной  рацион  из  кормов    и    нужной питательности, чтобы при этом затраты оказались минимальными. 

3.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=38.2

=4.4

=6.2

=26.4

=4.1

=1.3

=30.3

=0

=5.9

=35.0

=5.9

=0

Доход

=16.2

=11.3

4.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=17.4

=5.7

=2.0

=15.2

=1.9

=3.8

=22.1

=2.1

=11.7

Стоимость

=7.9

=13.2

5.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=18.6

=1.7

=2.8

=12.4

=1.8

=0.8

=14.7

=0.2

=2.6

=17.2

=2.4

=0

Доход

=6.6

=4.7

6.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.2

=3.0

=1.1

=8.3

=1.2

=2.3

=12.1

=1.2

=6.3

Стоимость

=4.4

=6.3

7.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=24.4

=3.3

=2.4

=15.6

=2.4

=1.2

=16.1

=1.1

=3.6

=19.8

=3.6

=0.7

Доход

=4.9

=8.2

8.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=4.6

=1.6

=0.7

=4.1

=0.6

=1.1

=6.2

=0.7

=3.2

Стоимость

=1.8

=3.1

9.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=9.4

=1.3

=1.5

=6.6

=1.1

=0.6

=7.2

=0

=1.9

=8.9

=1.7

=0.1

Доход

=5.6

=7.9

10.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=34.8

=11.6

=4.1

=30.5

=3.8

=7.7

=41.3

=4.4

=23.1

Стоимость

=15.2

=27.1

11.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=19.2

=1.3

=1.5

=12.8

=2.7

=1.2

=14.6

=0

=3.1

=18.4

=2.9

=0

Доход

=8.8

=3.7

12.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=7.2

=2.6

=0.7

=6.4

=0.7

=1.9

=11.1

=0.8

=5.4

Стоимость

=3.7

=5.7

13.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=37.4

=4.7

=6.2

=28.1

=5.1

=1.6

=29.2

=0

=7.1

=33.3

=6.4

=0

Доход

=14.9

=11.2

14.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=14.1

=5.1

=1.4

=12.7

=1.3

=3.6

=21.4

=1.5

=11.2

Стоимость

=7.2

=12.1

15.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=6.6

=0.7

=1.2

=4.1

=0.8

=0.3

=5.1

=0

=1.2

=6.4

=1.1

=0

Доход

=2.7

=1.9

16.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=3.6

=1.3

=0.4

=3.2

=0.3

=0.9

=5.7

=0.4

=2.7

Стоимость

=1.9

=2.6

17.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=13.2

=1.5

=2.5

=8.6

=1.7

=0.7

=10.2

=0

=2.4

=12.4

=2.3

=0

Доход

=5.6

=3.7

18.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.1

=3.1

=1.3

=8.3

=1.2

=2.2

=11.9

=1.1

=6.4

Стоимость

=4.7

=6.9

19.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=4.7

=0.7

=0.7

=3.3

=0.6

=0.3

=3.6

=0

=0.9

=4.5

=0.8

=0

Доход

=2.9

=3.9

20.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=12.7

=4.4

=1.7

=11.5

=1.5

=3.1

=17.6

=1.5

=9.1

Стоимость

=6.6

=9.5

21.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=12.2

=1.6

=1.2

=7.8

=1.2

=0.6

=8.2

=0.5

=1.8

=9.6

=1.8

=0

Доход

=2.7

=4.1

22.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=6.4

=2.1

=0.8

=10.7

=0.8

=1.6

=8.8

=0.9

=4.6

Стоимость

=3.5

=4.7

23.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=19.1

=2.2

=3.1

=13.2

=2.1

=0.6

=15.2

=0

=2.7

=17.2

=2.8

=0

Доход

=7.4

=5.8

24.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=19.1

=6.5

=2.5

=21.7

=2.3

=4.7

=26.3

=2.4

=13.7

Стоимость

=10.1

=14.2

25.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=16.2

=1.7

=2.6

=11.0

=1.8

=0.9

=12.4

=0

=2.3

=15.6

=2.4

=0

Доход

=6.6

=4.2

26.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.6

=3.2

=1.2

=10.4

=1.1

=2.3

=13.2

=1.1

=6.8

Стоимость

=5.1

=7.1

27.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=21.4

=2.3

=3.5

=14.7

=2.1

=1.2

=17.2

=0

=3.3

=20.4

=3.4

=0

Доход

=8.3

=6.9

28.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=12.7

=4.4

=1.7

=11.5

=1.5

=3.1

=17.6

=1.6

=9.1

Стоимость

=6.6

=9.5

29.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=10.7

=1.1

=1.7

=7.6

=1.0

=0.5

=8.1

=0

=1.7

=10.2

=1.8

=0

Доход

=6.6

=4.2

30.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=7.1

=2.6

=0.7

=6.8

=0.6

=1.8

=11.1

=0.8

=5.6

Стоимость

=3.6

=6.1

         Пример расчета.   

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

При откорме животное должно получать не менее b1, b2 и b3 единиц питательных веществ видов:  V1, V2 и V3. Для составления рациона используют два вида корма:  K1 и K2. Содержание количества единиц питательных веществ в каждом корме, а также стоимость 1 кг корма приведены в таблице:

питательные

требуемое количество

Содержание питательных веществ в кормах

вещества

питательных веществ

К1

К2

V1

b1=4,6

a11=1,6

a12=0,7

V2

b2=4,1

a21=0,6

a22=1,1

V3

b3=6,2

a31=0,7

a32=3,2

Стоимость

c1=1,8

c2=3,1

Необходимо составить дневной рацион из кормов K1 и K2 нужной питательности, чтобы при этом затраты оказались минимальными.

  1.  Ограничительные условия вытекают из системы неравенств:

                                         

  1.  Функция цели:

                                        

    5.Строим многоугольник допустимых решений и линию уровня F=0:

  1.  Из построения видно, что оптимальной точкой, обеспечивающей минимальные затраты является точка А. Ищем ее координаты из системы уравнений, включающих данную точку:

выражаем               

подставляем    в другое уравнение и получаем, что

  

тогда       

7.Определяем   минимальное,  подставляя координаты точки  А в уравнение линии уровня:

8. Выводы: Выполняются студентом самостоятельно.


 

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

15755. РУССКИЙ РОК: К ПРОБЛЕМЕ НАУЧНОЙ ДЕФИНИЦИИ 75.5 KB
  О.Э. НИКИТИНА Тверь РУССКИЙ РОК: К ПРОБЛЕМЕ НАУЧНОЙ ДЕФИНИЦИИ Изучение русского рока как национального варианта общекультурного феномена является сравнительно новой сферой научного интереса. Большинство исследований в этой области посвящено решению проблем час
15756. КАМЧАТКА КАК СОСТОЯНИЕ ДУШИ: К ВОПРОСУ О МЕТОДАХ ИССЛЕДОВАНИЯ РУССКОЙ РОК-ПОЭЗИИ 62 KB
  С.А. ПЕТРОВА СанктПетербург КАМЧАТКА КАК СОСТОЯНИЕ ДУШИ: К ВОПРОСУ О МЕТОДАХ ИССЛЕДОВАНИЯ РУССКОЙ РОКПОЭЗИИ Как известно романтизм третьей волны1 не смог бы образоваться без своих предшественников. И при исследовании литературных творений этой традиции конц
15757. ЕКОНОМІЧНА ЕФЕКТИВНІСТЬ РОСЛИННИЦЬКИХ ГАЛУЗЕЙ ТА ШЛЯХИ ЇЇ ПІДВИЩЕННЯ ТОВ «НАТАЛКА» ЯМПІЛЬСЬКОГО РАЙОНУ 676.5 KB
  Питаннями підвищення економічної ефективності виробництва сільськогосподарської продукції займається велика група науковців. Ними розроблені стратегічні аспекти зміцнення сільськогосподарського виробництва в країні, структурної перебудови галузі, підвищення економічної ефективності використання земельних, матеріально-технічних і трудових ресурсів, ціноутворення, формування і функціонування ринків зерна.
15758. История Советской архитектуры 113.5 KB
  Социалистическая революция уничтожила частную собственность на землю и средства производства. Впервые в истории архитектуры не на словах, а на деле стала архитектурой для всего народа, архитектор – государственным деятелем, что в корне изменило социально-идеологическую направленность, а следовательно, и все ценностные критерии архитектуры.
15759. Особенности работы школы по формированию гражданской идентичности младших школьников 199.5 KB
  На основе анализа психолого-педагогической литературы определить теоретическое значение понятия “гражданская идентичность”. Проанализировать психологические особенности младших школьников в контексте развития гражданских качеств личности. Рассмотреть формирование гражданских и патриотических качеств младших школьников как основы гражданской идентичности на уроках.
15760. Объект, предмет, метод и организация статистики промышленности 43 KB
  Тема 1. Объект предмет метод и организация статистики промышленности. Промышленность является основой экономики. Она создает материальнотехническую базу научнотехнического прогресса и средства производства для других отраслей производит большую часть продуктов...
15761. Статистика продукции промышленности 70 KB
  Тема 2. Статистика продукции промышленности Экономический потенциал страны определяется масштабом развития ее промышленности. Цель деятельности любого промышленного предприятия производство продукции. 2.1. Под продукцией промышленности понимают прямой полезный р...
15762. СТАТИСТИКА ЧИСЛЕННОСТИ РАБОТНИКОВ И ИСПОЛЬЗОВАНИЯ РАБОЧЕГО ВРЕМЕНИ 73.5 KB
  ТЕМА 3. СТАТИСТИКА ЧИСЛЕННОСТИ РАБОТНИКОВ И ИСПОЛЬЗОВАНИЯ РАБОЧЕГО ВРЕМЕНИ Персонал предприятия фирмы это совокупность физических лиц отношения которых с предприятием регулируются договором найма. Согласно общероссийскому классификатору профессии рабочих должн
15763. СТАТИСТИКА ПРОИЗВОДИТЕЛЬНОСТИ ТРУДА 76.5 KB
  Тема 4. СТАТИСТИКА ПРОИЗВОДИТЕЛЬНОСТИ ТРУДА. Под производительностью труда понимают результативность живого конкретного труда его способность производить в единицу времени определенное количество продукта. На практике уровепроизводительности труда ха