Задачи по оптимизационному моделированию

Линейное программирование

Линейное программирование – дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функции на множествах, определенными линейными ограничениями (равенствами и неравенствами).

Задача 1.

Задача о рационе.

Существует 4 вида продуктов стоимостью c1,c2,c3,c4. Надо потребить в1 -белков, в2-углеводов, в3-жиров. Сколько каждого продукта(х1, х2, х3, х4- количество продуктов), чтобы стоимость рациона была наименьшей. Содержание в каждом продукте основных компонент рациона приводится в таблице:

Белки	А11	А12	А13	А14
Жиры	А21	А22	А23	А24
Углеводы	А31	А32	А33	А34

Условие задачи легко может быть переписано в виде системы неравенств

а11х1+а12х2+а13х3+а14х4<в1

а21х1+а22х2+а23х3+а24х4<в2

а31х1+а32х2+а33х3+а34х4<в3

х1*х2*х3*х4>0

l=с1х1+с2х2+с3х3+с4х4

Целевая функция l определяет стоимость рациона. Надо определить такие количества продуктов х1 х2 х3 х4 каждого вида, чтобы l приняло минимальное значение.

Если продуктов всего два, задача приобретает особенно простой вид и допускает графическое решение.

а11х1+а12х2<в1

а21х1+а22х2<в2

а31х1+а32х2<в3

х1>0 x2>0

a=c1x1+c2x2

Пусть a=const Целевая функция будет представлять собой прямую в координатных осях x1 x2. Если изменять a, то происходит смещение этой прямой параллельно самой себе. Сущность графического метода решения задачи линейного программирования состоит в поиске такого положения целевой прямой, при котором она имеет общую точку с областью допустимых значений в некоторой ее вершине, а a максимален.

Общая задача линейного программирования может быть записана следующим образом:

а11х1+….+а1nхn=в1

а21х1+… +а2nхn<в2 n>m

………………………

аm1х1+…+аm4хn<вm

x1,x2,…,xn >0

L=c1x1+….+cnxn ® max

Линейная система неопределенна, т.е. количество неизвестных больше количества уравнений (общая задача линейного программирования)

При числе измерений больше двух графическое решение задачи невозможно. Для такой задачи был разработан Симплекс-метод, представляющий собой итеративную процедуру поиска вершины области допустимых значений, проходя через которую, гиперплоскость целевой функции имеет максимальное значение a

Симплекс метод состоит в том, что общая задача приводится к каноническому виду:

Следует добиться того, чтобы целевая функция приобрела следующий вид:

Будем искать минимум этой функции. При условии, что все положительны, минимум целевой функции достигается, когда все равны нулю

Содержание Симплекс-метода представляет собой следующий алгоритм:

1) привести систему к каноническому виду

2) целевую функцию привести к такому виду, все положительны и она достигает минимума, когда

Те переменные которые не обращаются в ноль называются базисными. Значит необходимо относить к базису те переменные, при которых коэффициенты в целевой функции отрицательны и при помощи уравнение исключать их из целевой функции.

Программа для решения задачи линейного программирования модифицированным Симплекс методом.

Задачи по оптимизационному моделированию

1. Предприятие производит два вида изделий: А и Б. Выделенные ресурсы: 32 т металла, 54 тыс. кВт-ч электроэнергии. План реализации: не менее 2 тысяч изделий А и не менее 3 тысяч изделий Б. На выпуск 1 тысячи изделий А затрачивается 3 т металла, 3 тыс. кВт-ч электроэнергии. На выпуск 1 тысячи изделий Б затрачивается 1 т металла, 6 тыс. кВт-ч электроэнергии. От реализации 1 тыс. изделий А завод получает прибыль 500 тыс. руб., от реализации 1 тысячи изделий Б — 700 тыс. руб. Выпуск какого количества изделий А и Б (в тыс. штук) надо запланировать, чтобы прибыль от их реализации была наибольшей?

2. Для изготовления различных изделий A, B и C предприятие использует три различных вида сырья – I, II и III. Нормы расходов сырья на производство одного изделия каждого вида, общее количество сырья каждого вида, которое может быть использовано предприятием, и цены на изделия приведены в следующей таблице:

Виды сырья	Нормы расхода сырья на одно изделие (кг)	Общее количество сырья (кг)
A	B	C
I
II
III
цена

Какого вида изделия необходимо производить, чтобы получить наибольшую прибыль?

3. Кооператив выпускает изделия А и Б. На выпуск 1 тыс. изделий А затрачивается 3 т металла, 3 тыс. кВт-ч электроэнергии. На выпуск 1 тыс. изделий Б затрачивается 1 т металла, 6 тыс. кВт-ч электроэнергии. От реализации 1 тыс. изделий А завод получает прибыль 500 тысяч руб., от реализации 1 тыс. изделий Б - 700 тыс. руб. Кооператив намерен получать прибыль не менее 6,5 млн. руб. в год. Ему выделили 54 тыс. кВт-ч электроэнергии. Какое минимальное количество металла потребуется кооперативу, чтобы обеспечить нужную прибыль?

4. Фирма выпускает прогулочные и спортивные велосипеды. Ежемесячно сборочный цех способен собрать не более 600 прогулочных и не более 300 спортивных велосипедов. Качество каждого велосипеда проверяется на двух стендах А и В. Каждый прогулочный велосипед проверяется 0,3 ч. на стенде А и 0,1 ч — на стенде В, а каждый спортивный велосипед проверяется 0,4 ч на стенде А и 0,3 ч — на стенде В. По технологическим причинам стенд А не может работать более 240 ч в месяц, а стенд В — более 120 ч в месяц. Реализация каждого прогулочного велосипеда приносит фирме доход в 50 руб., а каждого спортивного — 90 руб. Сколько прогулочных и сколько спортивных велосипедов должна ежемесячно выпускать фирма, чтобы ее прибыль была наибольшей?

5. В городе имеются два склада муки и два хлебозавода. Ежедневно с первого склада вывозится 50 т муки, со второго — 70 т. Эта мука доставляется на хлебозаводы, причем первый получает 40 т, второй — 80 т. Допустим, что перевозка одной тонны муки с первого склада на первый завод составляет 120 руб., с первого склада на второй завод — 160 руб., со второго склада на первый завод — 80 руб. и со второго склада на второй завод — 100 руб. Как нужно спланировать перевозки, чтобы их общая стоимость за один день была минимальной?

6. Для полива трех полей колхоза используют насосную станцию. На первое поле требуется подать не менее 200 кубометров воды в сутки, на второе - не менее 300, на третье - не менее 350. Колхоз имеет право расходовать не более 1200 кубометров воды в сутки. Стоимость подачи одного кубометра воды на первое поле -1570 руб., на второе - 1720 руб., на третье - 1930 руб. сколько кубометров воды надо подать на каждое поле, чтобы затраты были наименьшими?

7. На заводе выпускаются изделия двух видов. Чтобы изготовить каждое изделие работают машины четырех типов. Сколько надо выпускать изделий типа A и типа B, чтобы от их реализации получить оптимальную прибыль, если изделие типа A стоит 4 рубля, а типа B – 6 руб.

Машины Изделия
A		0,5
B
Время работы

8. Бетон, производимый на заводах А и Б нужно развозить по трем стройплощадкам: N1, N2, N3. Потребности стройплощадок в бетоне: N1 - 200 т, N2 - 280 т, N3- 220 т. Запасы бетона на заводах: А - 320 т, Б - 380 т.

Затраты на перевозку 1 т бетона (представлены в таблице):

Завод	стройплощадка
N1 (ICU)	N2 (ICU)	N3 (ICU)
A
Б

ICU (ВЕИ) - "валютные" единицы информатики.

Требуется составить такой план перевозок, который обеспечивал бы наименьшие затраты.

9. Для изготовления различных изделий A, B и C предприятие использует три различных вида сырья – I, II и III. Нормы расходов сырья на производство одного изделия каждого вида, общее количество сырья каждого вида, которое может быть использовано предприятием, и цены на изделия приведены в следующих таблицах:

Виды сырья	Нормы расхода сырья на одно изделие (кг)	Общее количество сырья (кг)
A	B	C
I
II
III

Цена одного изделия (руб.)
A	B	C

Дата добавления: 2015-10-23