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


 

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

36857. Чрезвычайные ситуации. Действия в ЧС 215.59 KB
  Поражающий фактор источника ЧС — составляющая опасного явления или процесса физического, химического или биологического (бактериального) характера, вызываемого источником ЧС и приводящего к поражению людей, сельскохозяйственных животных и растений, хозяйственных и иных объектов, элементов окружающей природной среды.
36858. Построение двумерных графиков 396 KB
  plotxy[xcpycpcption] x массив абсцисс; y массив ординат; xcp ycp cptionподписи осей X Y и графика соответственно. Затем воспользуемся функцией plotxy для построения кривой и выведем с ее же помощью подписи координатных осей X Y а также имя графика plot function y=sincosx Листинг 4. Построение графика функции y = sincosx с помощью функции plot x=2pi:0.
36859. РАБОТА СО СВОДНЫМИ ТАБЛИЦАМИ В MS EXCEL 88.5 KB
  РАБОТА СО СВОДНЫМИ ТАБЛИЦАМИ В MS EXCEL Цель работы: рассмотреть возможности обработки больших массивов данных средствами MS Excel научиться создавать сводные таблицы и управлять данными. Установите курсор в диапазоне ячеек содержащих значения заголовки строк и столбцов В любую заполненную данными ячейку таблицы Чтобы создать сводную таблицу на вкладке Вставка в группе Таблицы выберите раздел Сводная таблица а затем пункт Сводная таблица. На экран будет выведено диалоговое окно Создание сводной таблицы. На отдельном листе будет...
36860. Функция plot2d 690.5 KB
  Функция plot2d plot2d[logflg]xy[key1=vlue1key2=vlue2. Следует отметить что вовсе не обязательно использовать полную форму записи функции plot2d со всеми ее параметрами. В простейшем случае к ней можно обратиться кратко как и к функции plot. Создавать массив Y необязательно следует лишь в качестве аргумента функции plot2d указать математическое выражение функции.
36861. Форматирование графиков функций 724 KB
  Visibility отображение графика переключатель принимающий значения on и off. Figure nme имя графика это последовательность символов которые выводятся в строке заголовка графического окна. По умолчанию графическому окну присваивается имя Scilb Grphic d где d это порядковый номер графика Figure id.
36862. Word: Работа с таблицами 80 KB
  Выполните подготовительные действия для работы с таблицами: выполните команду меню Таблица и в меню этой команды установите команду Отображать сетку если в этой строке установлена команда Скрыть сетку то выделите эту строку и нажмите на левую кнопку мыши после чего там появится команда Отображать сетку; выведите на экран панель инструментов Таблицы и границы что проще всего сделать нажатием на кнопку Панель границ на Стандартной панели инструментов но можно также или использовать контекстное меню в области панелей...
36863. Работа со сводными таблицами. Создание сводных таблиц 681.5 KB
  Сохраните документ в своей папке под именем Сводные таблицы. Установите курсор в диапазоне ячеек содержащих значения заголовки строк и столбцов В любую заполненную данными ячейку таблицы Выберите команду Данные Сводная таблица. Во втором диалоговом окне проверьте правильно ли выделен диапазон данных для создания сводной таблицы или задайте диапазон данных если диапазон не был выбран Рис. Третье диалоговое окно предлагает выбрать лист для размещения сводной таблицы оставьте принятую по молчанию установку Новый лист Рис.
36864. Исследование недвоичных счетчиков 72.5 KB
  При построении счетчиков с дешифратором состояния наиболее целесообразно использовать счетчики интегрального состояния например 74191 см. Счетчик с дешифратором состояния. D; счетный вход ─ CLK; вход направления счета ─ U суммирование активен высоким уровнем ─ D вычитание активен низким уровнем; вход управления предварительной установкой ─ LOD; выход переноса ─ RCO выход дешифратора состояния активен низким уровнем при достижении последнего состояния счетчика. При выполнении этой части работы необходимо снимать временные диаграммы...
36865. Построение трехмерных графиков в Scilab 676.5 KB
  Функции plot3d и plot3d1 В Scilb поверхность можно построить с помощью функций plot3d или plot3d1. Их отличие состоит в том что plot3d строит поверхность и заливает ее одним цветом а plot3d1 поверхность каждая ячейка которой имеет цвет зависящий от значения функции в каждом соответствующем узле сетки. Обращение к функциям следующее: plot3dxyz[thetlphlegflgebox][keyn=vluen] plot3d1xyz[thetlphlegflgebox][keyn=vluen] здесь x векторстолбец значений абсцисс; y векторстолбец значений ординат; z матрица значений...