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


 

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

12028. Анализ действующей практики предоставления услуг коммерческими банками в Республики Казахстан 670 KB
  СОДЕРЖАНИЕ ВВЕДЕНИЕ Теоретические аспекты предоставления услуг коммерческими банками Сущность банковских услуг и продуктов Классификация банковских услуг Анализ действующей практики предоставления услуг коммерческ
12029. ПУТИ СОВЕРШЕНСТВОВАНИЯ КРЕДИТНЫХ РЕСУРСОВ В СБЕРБАНКЕ РФ 637.5 KB
  СОДЕРЖАНИЕ ВВЕДЕНИЕ 5 1 ИСТОЧНИКИ И ЗНАЧЕНИЕ КРЕДИТНЫХ 11 РЕСУРСОВ В ДЕЯТЕЛЬНОСТИ БАНКА 1.1 Понятие кредитных ресурсов факторы определяющие 11 их объем и структуру 1.2 Особенности формирования кредитных ресурсов 29 в Сбербанке РФ 2 АНАЛИЗ ПРАК
12030. Расчетно-кассовое обслуживание предприятий коммерческими банками 570.5 KB
  Дипломная работа на тему: Расчетно-кассовое обслуживание предприятий коммерческими банками СОДЕРЖАНИЕ: [1] Введение [2] Глава 1. Безналичные расчеты [3] 1.1. Основы организации безналичных рас...
12031. АНАЛИЗ ОРГАНИЗАЦИИ МЕЖБАНКОВСКИХ РАСЧЕТОВ НА ПРИМЕРЕ СВЕРДЛОВСКОЙ ОБЛАСТИ И РКЦ ГОРОДА КАМЫШЛОВА 572.5 KB
  СОДЕРЖАНИЕ. СУЩНОСТЬ И ЗНАЧЕНИЕ МЕЖБАНКОВСКИХ РАСЧЕТОВ Место и роль безналичных расчетов в экономической системе Специфика организации межбанковских расчетов. Развитие межба
12032. Изучение подходов к анализу кредитоспособности и инвестиционной привлекательности на базе изучения отечественного и зарубежного опыта 543.5 KB
  Закладка не определена. ВВЕДЕНИЕ Задачи улучшения функционирования кредитного механизма выдвигают необходимость использования экономических методов управления кредитом ориентированных на соблюдение экономических границ кредита. Это
12033. Учет и анализ платежеспособности и финансовой устойчивости предприятия 524.5 KB
  PAGE 2 ДИПЛОМНАЯ РАБОТА Тема: Учет и анализ платежеспособности и финансовой устойчивости предприятия. ВВЕДЕНИЕ Термин Анализ буквально означает расчленение разложение изучаемого объекта на части элемен...
12034. Использование корреспондентских международных банковских счетов в Туран-Алем банке 483.5 KB
  СОДЕРЖАНИЕ [1] ВВЕДЕНИЕ [2] ГЛАВА I. МЕЖБАНКОВСКИЕ КОРРЕСПОНДЕНТСКИЕ ОТНОШЕНИЯ КАК ОСНОВА ОРГАНИЗАЦИИ И ОСУЩЕСТВЛЕНИЯ РАСЧЕТОВ МЕЖДУ БАНКАМИ. [3] Значение необходимость банков и виды банковкорреспонденто