42054

Информационные технологии при решении целочисленной задачи линейного программирования

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

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

Информационные технологии при решении целочисленной задачи линейного программирования Цель работы изучить возможности табличного процессора MS Excel для решения задач целочисленного линейного программирования ЦЛП. Задача целочисленного линейного программирования Задачи оптимизации в результате решения которых искомые значения переменных должны быть целыми числами называются задачами моделями целочисленного дискретного программирования: Если то задачу называют полностью целочисленной; если же то имеем частично целочисленную...

Русский

2013-10-27

231.5 KB

44 чел.

Лабораторная работа 1_2. Информационные технологии при решении целочисленной задачи линейного программирования

Цель работы - изучить возможности табличного процессора MS Excel для решения задач целочисленного линейного программирования (ЦЛП).

Краткие теоретические сведения.

Задача целочисленного линейного программирования

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

Если , то задачу называют полностью целочисленной; если же , то имеем частично целочисленную задачу.

Наиболее часто используемым методом решения задач дискретного программирования является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel. Целочисленная оптимизация проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных  (при этом в режиме Параметры устанавливается тип задачи – линейная или нелинейная). Для этого

  •  В окне «Поиск решения» нажать кнопку «Добавить» и в появившемся окне «Добавление ограничений» ввести ограничения следующим образом:

- в поле «ссылка на ячейку» ввести адреса ячеек переменных задачи;

- в поле ввода знака ограничения установить «целое»

- подтвердить ввод ограничения нажатием кнопки «OK» (см. Рис.2.1).

  Рис.2.1. Ввод условия целочисленности всех (части) переменных

В случае целочисленной оптимизации возможен вызов только одного Отчета по результатам.

Достаточно часто при моделировании используется особый случай дискретности  задачи - булевость переменных, т.е. переменные могут принимать значения 0 или 1. Характерный пример этого случая – задача о назначениях.

Пример задачи целочисленного линейного программирования

Задача. Организация арендует баржу грузоподъемностью 200 т. На ней предполагается перевозить груз 4 типов. Вес и стоимость единицы груза равны соответственно

20, 15, 20, 14  - вес единицы груза, и

100, 80, 40, 30 – стоимость единицы груза.

Необходимо погрузить на баржу груз максимальной стоимости.

Решение. Пусть  - число предметов j-ого типа, которое следует погрузить на баржу. Тогда математическая модель задачи имеет вид:

      - целые неотрицательные.

 Текстовая форма-таблица для ввода условий задачи и исходных данных имеет вид:

 Диалоговое окно Поиск решения имеет вид:

Диалоговое окно Параметры поиска решения имеет вид:

Вид окна с окончательным решением имеет вид:

Контрольные упражнения. Варианты.

 I. Составить математические модели следующих задач при условии, что искомые неизвестные величины должны быть целочисленными.

1.В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3 м2 площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1 тыс. руб. и требует для установки 2 м2 площади; II вида – 3 тыс. руб. и 1 м2 площади.  Приобретение одного комплекта оборудования  I вида позволит увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Требуется определить, какое количество дополнительного оборудования позволит максимально увеличить выпуск продукции.

2. Три типа самолетов следует распределить между 4 авиалиниями. В таблице 1 задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы. Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Таблица 1

Тип самолета

Число самолетов

Месячный объем перевозок одним самолетом по авиалиниям

Эксплуатационные расходы на один самолет по авиалиниям

I

II

III

IV

I

II

III

IV

1

50

15

10

20

50

15

20

25

40

2

20

30

25

10

17

70

28

15

45

3

30

25

50

30

45

40

70

40

65

II. Найти решение задач целочисленного линейного программирования. Варианты.

1. 

2.

3.

4.

5.

6.

7.

8.

9.

10.

 

11.

12.

13.

14.  


 

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

27375. Мораль. Формирование морали 34 KB
  Ценность человеческой жизни меняется в зависимости от ценности вещей и статуса или других признаков человека. Ценность жизни человека определяется чувствами связанных с ним людей. Ценность человеческой жизни определяется вкладом человека в общий прогресс человечества. Главной проблемой является не следование предписаниям а отыскание смысла жизни.
27376. Профессиональные свойства и характеристики личности учителя 40.5 KB
  Как и любой вид деятельности деятельность педагога имеет свою структуру Зимняя И. Предмет педагогической деятельности. Продукт и результат педагогической деятельности. Каждый вид деятельности имеет свой предмет точно также и педагогическая деятельность имеет свой.
27377. Классный руководитель 27.5 KB
  выполняет следующие функции: 1 знакомится с семьями учащихся для того чтобы знать какое влияние оказывается на них дома и для того чтобы своевременно помочь им если это влияние оказывается неблагоприятным; 2 знакомит родителей с требованиями школы к учащимся по режиму дня приготовлению уроков привлечению учащихся к домашнему труду и др.; 3 стремится обеспечить единство требований школы и семьи; 4 для родителей регулярно устраивает лекции по отдельным вопросам где говорится о средствах и методах которыми семья может помочь школе в...
27378. Общеобразовательные цели обучения математике 19.7 KB
  ФГОС здесь все из книги по фгосам на экзамене будут фгосы доступны так что учить здесь всё не нужно наизусть: В результате изучения курса математики обучающиеся на ступени начального общего образования: научатся использовать начальные математические знания для описания окружающих предметов процессов явлений оценки количественных и пространственных отношений; овладеют основами логического и алгоритмического мышления пространственного воображения и математической речи приобретут необходимые вычислительные навыки; научатся применять...
27379. Этапы формирования представлений о числе 18.8 KB
  5 этап: изучение отрезка ряда натуральных чисел. Так же необходимо в процессе изучения отрезка натуральных чисел отрабатывать прием присчитывания и отсчитывания по одному. Моро А последовательно один за другим рассматриваются отрезки ряда натуральных чисел 12 123 123. Основные приемы: прочтение чисел счет предметов выделение нового для изучаемого числа.
27380. Изучение смысла сложения и вычетания 18.9 KB
  Этот подход легко интерпретируется на уровне предметных действий позволяя тем самым учитывать психологические особенности младших школьников. Например в учебнике М1М в качестве основного средства формирования у детей представлений о смысле действий сложения и вычитания выступают простые текстовые задачи. В основе другого подхода лежит выполнение учащимися предметных действий и их интерпретация в виде графических и символических моделей. Деятельность учащихся сначала сводится к переводу предметных действий на язык математики а затем к...
27381. Действия с величинами 23.83 KB
  Формирование у учащихся представлений о числе и о десятичной системе счисления тесно связано с изучением величин. В начальных классах у учащихся имеются некоторые интуитивные представления о величинах и об их измерении. Измерение заключается в сравнении данной величины с некоторой величиной того же рода принятой за единицу.
27382. ЗУНы для вычисления в пределах 100 (сложение и вычитание) 22.28 KB
  Остальные случаи вычислений над числами большими 100 относятся к письменным вычислениям. Рассмотрим методические особенности формирования умений складывать и вычитать числа в пределах 100 которые нашли отражение в учебниках М1М и М2М Моро. Овладение вычислительными приемами предполагает усвоение: нумерации чисел в пределах 100 разрядного состава двузначного числа табличных случаев сложения вычитания и свойств сложения и вычитания; прибавления числа к сумме вычитания числа из суммы прибавления суммы к числу вычитания...
27383. Алгоритмы: 1. Письменного сложения и вычитания 2. Письменного умножения 3. Письменного деления 20.18 KB
  Письменного деления ЗУНы для сложения и вычитания: Нумерация многозначных чисел Разрядный состав многозначных чисел Десятичный состав числа Навык сложения и вычитания чисел в пределах 20 Знание переместительного и сочетательного закона сложения Как и другие алгоритмы письменного вычисления в и – рассматриваются поэтапно: Актуализация ЗУН подготовка к изучению алгоритма подготовка и изучение алгоритма Введение самого алгоритма Усвоение алгоритма Продуктивное повторение новой темы включать новые знания в систему имеющихся Основная...