4769

Решение задач линейного программирования с помощью инструмента Поиск решения

Контрольная

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

Решение задач линейного программирования с помощью инструмента Поиск решения Рассмотрим следующую задачу распределения ресурсов. Для производства двух типов продукции (x1=Прод.1, x2=Прод.2) требуется два вида ресурсов количество которых ограничено...

Русский

2012-11-25

184 KB

8 чел.

Решение задач линейного программирования с помощью инструмента «Поиск решения»

Рассмотрим следующую задачу распределения ресурсов. Для производства двух типов продукции (x1=Прод.1, x2=Прод.2) требуется два вида ресурсов количество которых ограничено (Ресурс 1≤1700, Ресурс 1≤1600), причем для продукции первого типа  необходимо 3 единицы

первого  ресурса и две единицы второго, а для продукции второго типа необходимо 4 единицы первого ресурса и 5 единиц второго ресурса. Прибыль, получаемая от реализации продукции первого и второго типа , составляет две и четыре единицы соответственно. Требуется максимизировать общую прибыль от реализации двух видов продукции.

Математическая формулировка поставленной задачи имеет следующий вид:

 F=2x1+4Nx2→max   (ЦФ)  - целевая функция

     3*Nx1+4x2≤1700     (ОГ)   - ограничения

     (2+N)x1+5x2≤1600

     x1≥0, x2≥0           (УН)  - условия неотрицательности.

На рабочем листе (Рис.1.1), соответствующем рассматриваемой задаче, в ячейки В5:С5 введены коэффициенты целевой функции, а в ячейки В8:С9 – коэффициенты ограничений. Искомым значениям Прод.1, Прод.2 соответствуют изменяемые ячейки B3:C3, а целевой функции – целевая ячейка D3, в которую введена формула =СУММПРОИЗВ(B3:C3,В5:С5), позволяющая вычислять значение целевой функции при заданных значениях Прод.1, Прод.2. В ячейки B8,B9

введены формулы =СУММПРОИЗВ(B3:C3,В8:С8), =СУММПРОИЗВ(B3:C3,В9:С9), позволяющие вычислять значения левых частей ограничений (ОГ), правым частям которых соответствуют ячейки F8,F9.

 

    Рис. 1.1

Для ввода формулы, например,  в целевую ячейку D3 необходимо после установки курсора в этой  ячейке щелкнуть мышью по кнопке Мастер функций, выбрать в категориях – математические функции и функцию – СУММПРОИЗВ, в появившемся диалоговом окне (Рис.1.2) в массив 1 ввести B3:C3, а в массив 2 ввести B5:C5, после чего нажать  кнопку Готово.  Во все диалоговые окна адреса ячеек удобно вводить протаскивая мышь по ячейкам, чьи адреса следует ввести. Что бы ввести соответствующие формулы в ячейки B8,   B9 достаточно скопировать в них  целевую ячейку.

    Рис. 1.2

В диалоговом окне Поиск решения (Рис.1.3) в поле Установить целевую ячейку введен адрес целевой ячейки $D$3, выделен переключатель Максимальному значению, в окне Изменяя ячейки введены адреса изменяемых ячеек $B$3:$C$3, в окне Ограничения введены ограничения $B$3:$C$3>=0, $D$8:$D$9<=$F$8:$F$9, соответствующие (УН), (ОГ). Ввод ограничений осуществляется после нажатия кнопки Добавить, в окне  диалога Добавить ограничения (Рис.1.4).

    Рис. 1.3

    Рис. 1.4

    Рис. 1.5

После установки в диалоговом окне Параметры поиска решения (Рис.1.5) флажка Линейная модель, обеспечивающего применение симплекс метода, определение задачи с помощью инструмента Поиск решения завершено. На (Рис.1.6) показано диалоговое окно Результаты поиска решения и приведены результаты решения исходной задачи, в соответствии с которыми оптимальным значениям Прод.1=300, Прод.2 =200 соответствует максимальное значение целевой функции равное 1400.

    Рис. 1.6

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

После выделения в окне Отчеты диалогового окна Результаты поиска решения отчетов Результаты, Устойчивость, Пределы и нажатия кнопки ОК на одноименных листах рабочей книги создаются соответствующие отчеты.

Целевая ячейка (Макс)

Ячейка

Имя

Исходно

Результат

$D$3

Значения ЦФ

0

1400

Изменяемые ячейки

Ячейка

Имя

Исходно

Результат

$B$3

Значения Прод. 1

0

300

$C$3

Значения Прод. 2

0

200

Ограничения

Ячейка

Имя

Значение

Формула

Состояние

Разница

$D$8

Ресурс 1 левая часть

1700

$D$8<=$F$8

связанное

0

$D$9

Ресурс 2 левая часть

1600

$D$9<=$F$9

связанное

0

$B$3

Значения Прод. 1

300

$B$3>=0

не связан.

300

$C$3

Значения Прод. 2

200

$C$3>=0

не связан.

200

    Рис. 2.1

Отчет по результатам (Рис.2.1) состоит из трех таблиц:

- таблица Целевая ячейка содержит сведения о целевой функции до начала вычисления     - (столбец Исходно) и после вычислений (столбец Результат);

- таблица Изменяемые ячейки содержит значения искомых переменных до начала вычисления (столбец Исходно) и после вычислений (столбец Результат);

- таблица Ограничения содержит информацию о выполнении ограничений (ОГ) и (УН).

Для ограничений в столбце Формула содержатся зависимости, введенные в диалоговом окне Поиск решения; в столбце Значение содержатся величины использованного ресурса; в столбце Разница содержатся величины неиспользованного ресурс; в столбце Состояние указывается статус ограничения. Если ограничение выполняется как равенство то оно – связанное, а если как неравенство то - несвязанное.

 Изменяемые ячейки

Результ.

Редуц.

Целевой

Допустимое

Допустимое

Ячейка

Имя

значение

стоимость

Коэффициент

Увеличение

Уменьшение

$B$3

Значения Прод. 1

300

0

2

1

0,4

$C$3

Значения Прод. 2

200

0

4

1

1,333333333

Ограничения

Результ.

Теневая

Ограничение

Допустимое

Допустимое

Ячейка

Имя

значение

Цена

Правая часть

Увеличение

Уменьшение

$D$8

Ресурс 1 левая часть

1700

0,285714286

1700

700

420

$D$9

Ресурс 2 левая часть

1600

0,571428571

1600

525

466,6666667

Отчет по устойчивости состоит из двух таблиц. В таблице Изменяемые ячейки содержатся следующие значения для переменных:

  •  оптимальные значения (столбец Результ. значение);
  •  редуцированные стоимости (столбец Редуц. стоимость), т.е. дополнительные двойственные переменные, которые показывают, насколько изменяется целевая функция при принудительном включении единицы соответствующей продукции в оптимальное решение;
  •  коэффициенты целевой функции (столбец Целевой коэффициент);
  •  предельные значения приращения коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение (столбцы Допустимое Увеличение, Допустимое Уменьшение);

В таблице Ограничения содержатся следующие значения для ограничений:

  •  величина использованных ресурсов (столбец Результ. значение);
  •  теневые цены (столбец Теневые цены), т.е. двойственные оценки, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;
  •  значения приращений ресурсов, при которых сохраняется набор переменных, входящих в оптимальное решение.

Целевое

Ячейка

имя

Значение

$D$3

Значения ЦФ

1400

Изменяемое

Нижний

Целевой

Верхний

Целевой

Ячейка

имя

Значение

предел

результат

предел

Результат

$B$3

Значения Прод. 1

300

0

800

300

1400

$C$3

Значения Прод. 2

200

0

600

200

1400

    Рис. 2.3

Отчет по пределам (Рис.2.3) содержит информацию о том, в каких пределах может изменятся выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:

  •  приводятся значения Прод.1, Прод.2 в оптимальном решении (столбец Значения);
  •  приводятся нижние и верхние пределы изменения Прод.1, Прод.2 (столбцы Нижний предел, Верхний предел);
  •  значения целевой функции при выпуске данного типа продукции на нижнем и верхнем пределах (соответствующие столбцы Целевой результат).

Например, если Прод.1= 0 (нижний предел), то F=20+4200=800, а если Прод.1=300 (верхний предел) ), то F=2300+4200=1400.

3. Параметрический анализ

Под параметрическим анализом понимается решение задачи оптимизации при различных значениях того параметра, который ограничивает улучшение целевой функции. На Рис. 3.1 приведены результаты параметрического анализа при следующих значениях первого ресурса: 1280, 1500, 1700, 2000, 2400

Рис. 3.1

Структура сценария

Текущие значения:

Рес .1=1280

Рес.1=1500

Рес .1=1700

Рес.1=2000

Рес.1=2400

Изменяемые ячейки:

$B$3

800

0

157,1428571

300

514,2857143

800

$C$3

-1,77636E-14

320

257,1428571

200

114,2857143

-1,77636E-14

Ячейки результата:

$D$3

1600

1280

1342,857143

1400

1485,714286

1600

$D$8

2400

1280

1500

1700

2000

2400

$D$9

1600

1600

1600

1600

1600

1600

Примечания: столбец ''Текущие значения'' представляет значения изменяемых ячеек в

момент создания Итогового отчета по Сценарию. Изменяемые ячейки для каждого

сценария выделены серым цветом.

Рис. 3.2

 Результаты решения задачи при каждом значении изменяемого параметра можно сохранить как отдельный сценарий. Используя следующую последовательность команд  Сервис, Сценарии, Отчет, Структура, ОК, создается итоговый сценарий (Рис.3.2).

4. Решение транспортной задачи

Рассмотрим следующую транспортную задачу. В трех пунктах отправления (ПО1, ПО2,ПО3) имеются запасы однородного груза в количествах 210, 100, 600 единиц соответственно. Этот груз требуется перевести в пять пунктов назначения (ПН1, ПН2, ПН3, ПН4, ПН5) соответственно в количествах 150, 160, 200, 100, 300 единиц. Тарифы перевозок единицы груза указаны в ячейках C2:G5 (Рис.4.1). Например, стоимость перевозки единицы груза из ПО1 в ПН1 равна 6. Требуется найти минимальный по стоимости план перевозок, обеспечивающий вывоз имеющегося груза из всех пунктов отправления и доставку необходимого груза во все пункты назначения, причем обратные перевозки исключаются.

    Рис. 4.1

    Рис. 4.2

Искомым значениям соответствуют изменяемые ячейки С9:G11, целевой функции – ячейка H12 c формулой =СУМПРОИЗВ(С3:G5,C9:G11). Условиям баланса соответствуют ячейки B9:B11, C12:G12 в которые введены следующие формулы:

B9:    =СУМM(C9:G9)  D12:  =СУМM(D9:D11)

B10:  =СУМM(C10:G10)  E12:   =СУМM(E9:E11)

B11:  =СУМM(C11:G11)  F12:   =СУМM(F9:F11)

C12:  =СУМM(C9:C11)  G12:  =СУМM(G9:G11)

После ввода соответствующих ограничений в диалоговом окне Поиск решения (Рис.4.2) и выполнения Поиска решений получается окончательное решение задачи (Рис.4.3)


 

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

20959. Національно-культурне піднесення 1920-1930-х рр.. Українська культура в період тоталітаризму 1.42 MB
  Початок 1920-х років було для української культури позбавленим світлих перспектив. Розділ Україні між сусідніми державами гальмував національну інтеграцію, в тому числі і в сфері культури. Культурний потенціал Україні був підірваний руйнівними наслідками громадянської війни, часткової окупацією країни. Військове лихоліття не тільки знищило духовні і матеріальні цінності, а й основного творця культурних цінностей - інтелігенцію.
20960. ПАРОЛЬНИЙ ЗАХИСТ 101 KB
  Текст програми include iostream include fstream include conio.h include string include iomanip include windows.h using namespace std; string decrypt string str { for unsigned int i=0; i str.size; i if str[i]=' ' str[i]=charabsshortstr[i]255; return str; } string encrypt string str { for unsigned int i=0; i str.
20961. Шифрування та дешифрування даних за допомогою алгоритмів перестановки (збивання) 141.09 KB
  У якості інформації використовувати копію файлу з розробленою програмою програма дешифрування інформації повернення початкового вигляду файла; Індивідуальні завдання: Метод €œспутаної шини€ Текст програми: DEFINT IN: DEFSTR S RANDOMIZE 231 CLS: LOCATE 1 1 Lot = 5 s = FOR i=1 TO 64:s=sCHR6525RND:NEXT PRINT s; text : sav = s s = FOR i=1 TO 192: s=sCHR255RND: NEXT 'шифрование FOR i = 0 TO Lot sc=MIDss1I3232 l=2^i:sl= : r= FOR j = 1 TO 32 kg=ASCMIDsc j 1 kl=ASCMIDs j 1...
20962. Шифрування та дешифрування даних за допомогою алгоритмів підстановки (заміна) 69.72 KB
  Програма дешифрування інформації повернення початкового вигляду файла; а також оцінити правильність процедури €œшифрування – дешифрування€ відсутність зміни результату відносно початкового файлу. Підготовка даних полягає в: Введення вихідного тексту; Створення тимчасового текстового файлу файл 1 та занесення в нього вихідного тексту; Створення тимчасового текстового файлу файл 2 для подальшого занесення в нього результатів роботи програми; Введенні або автоматичному виборі ключа; Для режиму дешифрування якщо ключ...
20963. Шифрування та дешифрування даних з використанням режиму шифрування 98.95 KB
  Індивідуальні завдання: алгоритм Counter Mode CTR Текст програми AutoSeededRandomPool prng; SecByteBlock keyAES::DEFAULT_KEYLENGTH; prng.size ; byte ctr[ AES::BLOCKSIZE ]; prng.GenerateBlock ctr sizeofctr ; string plain = CTR Mode Test ; string cipher encoded recovered; try { cout plain text: plain endl; CTR_Mode AES ::Encryption e; e.size ctr ; The StreamTransformationFilter adds padding as required.
20964. Шифрування та дешифрування даних за допомогою алгоритмів гамування 30.38 KB
  Індивідуальні завдання : конгруэнтные генераторы Линейными конгруэнтными генераторами являются генераторы следующей формы: в которых это nый член последовательности а предыдущий член последовательности. Период такого генератора не больше чем m. Если a b и m подобраны правильно то генератор будет генератором с максимальным периодом и его период будет равен m. Например для линейного конгруэнтного генератора b должно быть взаимно простым с m.
20965. Використання алгоритмів шифрування з відкритими ключами 45.99 KB
  Постановка задачі Необхідно розробити і налагодити дві програми: Програма шифрування інформації з використанням визначених алгоритмів. Програма дешифрування інформації повернення початкового вигляду файла; а також оцінити правильність процедури €œшифрування – дешифрування€ відсутність зміни результату відносно початкового файлу.09 funkcja f dla kazdej rundy czynniki pierwsze klucz zakryty p1 4 = 0 q1 4 = 0 p = 19; q = 23; n = pq; M = random n; print Message = M; print Cryptogram = C; C = M^2 n; m1= C ^...
20966. Використання односпрямованих хеш-функцій 170.04 KB
  І КІТ39 Практична робота №26 €œВикористання односпрямованих хешфункцій€ за курсом €œЗахист інформації у комп’ютерних системах та мережах€ Ціль роботи : cтворення програм генерації дайджесту повідомлення за допомогою хешфункцій. Індивідуальні завдання: алгоритм HAVAL HAVAL однонаправленная хешфункция разработанная Yuliang Zheng англ. Для произвольного входного сообщения функция генерирует хешзначение называемое дайджестом сообщения которое может иметь длину 128 160 192 224 или 256 бит. Висновок: за час виконання практичноъ...
20967. Понятие мировоззрения, его структура и уровни. Формы мировоззрения: мифологическое, религиозное и философское 480 KB
  Систематизирует в самом общем виде представления человека о мире и самом себе. Антропоцентризм тип философского мировоззрения в центре которого стоит проблема человека Европа эпохи Возрождения нового и новейшего времени современные философские школы. Теоретическое мышление посредством абстракций обобщений сравнений идеализациий преодолевает границы образночувственного восприятия вскрывает существенные связи и отношения мира и человека выявляет новые горизонты познания и осмысления действительности. Поэтому осмысление проблем...