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. Выводы: Выполняются студентом самостоятельно.


 

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

53392. США. Індіанці: пошуки вирішення проблеми. Контроль навичок - аудіювання 95.06 KB
  By the end of the lesson you should be able to reply and react appropriately to various statements. Beside, you will listen to some new information about the first Americans who came to Alaska from Asia crossing the Bering land bridge, which later became the Bering Strait. You will hear the text about American Indians and their problems.
53393. Методичні основи змісту навчання та виховання 143 KB
  В широкому плані особистість людини є інтегральною цілісністю біогенних соціогенних і психогенних елементів. Коменського великого чеського педагога – чітко позначені положення про те що весь процес навчання і виховання дітей необхідно будувати з урахуванням їх вікових і індивідуальних особливостей і виявляти ці особливості шляхом систематичних спостережень. Він вважав що в процесі виховання і навчання необхідно орієнтуватися на позитивні якості...
53394. У НАС В ГОСТЯХ ІНДІЯ 99.5 KB
  Мета: забезпечити засвоєння учнями знань про характерні риси економіко географічного положення Індії особливості природних умов і ресурсів розміщення населення й господарства культурноісторичні особливості країни; розвивати творчі здібності учнів логічне мислення формувати культуру спілкування; продовжити розвивати інтерес до предмета; формувати вміння працювати самостійно та в групах виховувати почуття доброти й милосердя до людей інших...
53395. ІНДУКЦІЯ – МЕТОД ПІЗНАННЯ ІСТИНИ 59 KB
  Як виховати цілісне мислення як сформувати ставлення до математики як до цілісної системи яка забезпечує світопізнання розвиток інтелекту показати практичне застосування логічних методів для встановлення істини у житті людини Покажемо це на прикладі вивчення теми “Індукціяâ€. У перекладі з латинської термін “індукція†означає â€œнаведенняâ€. Розрізняють кілька видів індуктивних міркувань: міркування за схемою “повна індукція†та міркування за схемою “неповна індукціяâ€. Це індукція шляхом переліку популярна індукція та...
53396. На шляху до сучасності: утвердження індустріального суспільства у провідних державах світу 91.5 KB
  Мета уроку: Систематизувати узагальнити та конкретизувати знання та уявлення учнів про розвиток провідних держав світу в 2 половині ХІХ ст. Тип уроку: урок узагальнення та систематизації знань умінь і навичок. Після цього уроку учні зможуть: Характеризувати процес завершення формування індустріального суспільства у провідних державах Європи та...
53397. Використання інформаційних технологій на уроках математики 1.49 MB
  Застосування компютерної техніки на уроках дозволяє зробити урок нетрадиційним яскравим насиченим наповнюючи його зміст знаннями з інших наочних областей що перетворюють математику з об'єкту вивчення в засіб отримання нових знань. Ефективність застосування нових інформаційних технологій на уроках математики обумовлена наступними факторами: 1 різноманітність форм представлення інформації; 2 висока степінь наочності; 3 можливість моделювання за допомогою комп’ютера різноманітних об’єктів і процесів; 4 звільнення від рутинної роботи...
53398. Засоби пошуку інформації в Інтернеті. Принципи функціонування веб-каталогів та пошукових систем. Стратегії пошуку інформації 1.56 MB
  Сьогодні на уроці продовжим вивчати сільське господарство, характеристику тваринництва, узагальнемо спеціалізацію сільського господарства, ознайомимось і оцінемо проблеми і перспективи розвитку сільського господарства, завершимо виконання практичної роботи №9, використовуючи знання з інформатики.
53399. Алгоритм 434 KB
  В цей час решта членів команд задіяні в перехресному опитуванні: задають один одному по 3 теоретичних питання за темою, які готували дома заздалегідь, причому, задають питання та дають відповіді різні члени команди. Оцінює команди журі, до складу якого входять 2 найбільш підготовлених студента (1 бал за кожну правильну відповідь). Вони ж здійснюють контроль часу.
53400. Засоби масової інформації 66 KB
  Good afternoon boys and girls. I’m very glad to see you. We are also pleased to see our guests today and we’ll try to make our lesson useful and interesting. Today we are having our last lesson on Mass Media and our aim is to generalize our knowledge on this question and to get to know something new concerning mass media.