Отыскание опорного решения ОЗЛП

1. Если все свободные члены (не считая строки ) в симплекс-таблице неотрицательны, опорное решение получено.

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

3. Если в этой строке есть отрицательные элементы, то для столбца , соответствующего отрицательному элементу нужно произвести замену одной из свободных переменных на одну из базисных, причём в качестве разрешающего надо взять тот элемент этого столбца , имеющий одинаковый знак со свободным членом, для которого отношение к нему свободного члена минимально.

Поиск оптимального решенияОЗЛП

1. Если опорное решение получено, а в строке симплекс-таблицы нет ни одного отрицательного элемента, то оптимальное решение достигнуто.

2. Если в строке есть отрицательный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то оптимального решения не существует.

3. Если в этом столбце есть положительные элементы, то следует произвести замену одной из свободных переменных на одну из базисных, причём в качестве разрешающего надо взять тот элемент этого столбца, для которого отношение к нему соответствующего свободного члена минимально.

Порядок работы

1. Записать систему уравнений, соответствующую полученному варианту заданий в виде , . Дать описание всем введённым переменным.

2. Ввести добавочные переменные и представить систему в виде уравнений , .

3. Составить симплекс-таблицу и вручную найти решение поставленной задачи.

4. Выполнить контрольную проверку решения с использованием программы Excel.

5. Составить алгоритм симплекс-метода и реализовать его на языке Pascal (выбор другого языка программирования с разрешения преподавателя).

6. Найти решение задачи с использованием Вашей программы и сравнить его с полученными ранее (п.п. 3, 4).

Содержание отчёта

1. Постановка задачи.

2. Переход от словесного описания к математической модели с описанием всех переменных.

3. Ручной просчёт с использованием симплекс-таблиц.

4. Результаты, полученные с использованием Excel.

5. Результаты, выдаваемые Вашей программой.

6. Сравнение всех полученных результатов, пояснение причин расхождения, если это необходимо.

7. Словесная формулировка полученного ответа.

Варианты заданий

№ в-та	Задание
1.	Для производства двух видов изделий А и В используется три вида технологического оборудования. На изготовление одного изделия А оборудование первого типа используется в течение 5 часов, второго — в течение 3 часов и третьего — 2 часа. На производство одного изделия В, соответственно: 2 часа, 3 часа и 3 часа. В плановом периоде оборудование первого типа может быть использовано в течение 505 часов, второго — 393 часов и третьего — 348 часов. Прибыль от реализации одного изделия А равна 700 руб., В — 450 руб. Составить план производства, максимизирующий прибыль предприятия.
2.	Завод выпускает два вида редукторов. На изготовление одного редуктора первого вида расходуется 3 тонны чугуна и 1 тонна стали, а на изготовление одного редуктора второго вида — 1 тонна чугуна и 2 тонны стали. Завод располагает на месяц 180 тоннами чугуна и 120 тоннами стали и должен изготовить не менее 60 редукторов обоих видов. Составить месячный план производства редукторов, максимизирующий прибыль завода, если от сбыта одного редуктора первого вида прибыль составляет 40 тыс. рублей, а второго — 20 тыс. рублей.
3.	Для изготовления изделий А и В используется три вида сырья. На изготовление одного изделия А требуется 9 кг сырья первого вида, 6 кг сырья второго вида и 3 кг сырья третьего вида. На изготовление одного изделия В требуется соответственно 4 кг, 7 кг и 8 кг сырья. На складе запасы сырья первого вида имеются в количестве 800 кг, второго — 810 кг, третьего — 760 кг. Рыночная цена одного изделия А равна 300 рублей, изделия В — 200 рублей. Составить план производства, максимизирующий доход от реализации изделий А и В, если спрос на изделия А составляет не менее 40 штук.
4.	Для производства изделий А и В используются три вида станков. На производство одного изделия А требуется 6 часов работы станка первого вида, 4 часа работы станка второго вида и 3 часа работы станка третьего вида. На производство одного изделия В требуется 2 часа работы станка первого вида, 3 часа работы станка второго вида и 4 часа работы станка третьего вида. Месячный ресурс работы станков первого вида, имеющихся на заводе, равен 600 часов, всех станков второго вида — 520 часов, всех станков третьего вида — 600 часов. Прибыль от реализации одного изделия А равна 1200 рублей, изделия В — 1500 рублей. Составить оптимальный план производства изделий А и В.
5.	Для изготовления изделий А и В предприятие использует три вида сырья. На производство одного изделия А требуется 12 кг сырья первого вида, 10 кг сырья второго вида и 3 кг сырья третьего вида, а на производство одного изделия В — 3 кг, 5 кг и 6 кг соответственно. Производство обеспечено сырьем первого вида в количестве 680 кг, второго — 690 кг, третьего — 560 кг. Одно изделие А дает предприятию 680 рублей прибыли, а изделие В — 240 рублей. Составить план производства, максимизирующий общую прибыль предприятия.
6.	Мастерская ремонтирует трактора двух типов: I — мощностью 300 л.с. и II — мощностью 200 л.с. За неделю мастерская может отремонтировать не более 150 тракторов. За ремонт трактора I типа получают 2000 рублей, II типа — 1000 рублей. Составить недельный план ремонта тракторов, при котором мастерская получит не менее 200000 рублей и суммарная мощность отремонтированных тракторов будет наибольшей, если надо отремонтировать не менее 20 тракторов II типа.
7.	При откорме мясных свиней употребляется корм двух видов: К1 и К2. Один кг корма К1 содержит 500 единиц белка, 700 единиц углеводов и 1700 единиц жиров, а один кг корма К2 соответственно 700 ед., 200 ед. и 1300 ед. По нормам животное должно получать не менее 15500 ед. белка, 2500 ед. углеводов и не более 36500 ед. жиров. Цена 1 кг корма К1 составляет 13 рублей, корма К2 — 10 рублей. Составить наиболее дешевый рацион кормления свиней.
8.	Фермер располагает удобрениями двух видов: У1 и У2. В одной тонне удобрения У1 содержится 3000 ед. вещества В1, 6000 ед. вещества В2 и 9000 ед. вещества В3, а в 1 тонне удобрения У2 соответственно: 1000, 6000, 15000 ед. На 1 га должно быть внесено не более 20000 ед. вещества В1, 60000 ед. В2 и 120000 ед. В3. При соблюдении этих норм прибавка урожая от внесения одной тонны удобрения У1 составит 4500 кг, удобрения У2 — 3500 кг. Какие количества удобрений надо внести на 1 га, чтобы прибавка урожая была наибольшей?
9.	Фабрика выпускает вязаные костюмы и кофты, используя шерстяную и синтетическую пряжу. На один костюм идет 1300 г шерсти и 100 г синтетики, а на одну кофту — 500 г шерсти и 200 г синтетики. Фабрика имеет на неделю 75 кг шерсти и 22 кг синтетики. Общее количество выпущенных за неделю изделий не должно быть менее 50 штук. Составить план выпуска изделий, максимизирующий прибыль фабрики, если костюм стоит 50 рублей, а кофта — 25 рублей.
10.	Фирма "Морские прогулки" может приобрести большие катера вместимостью 18 человек и быстроходные глиссеры на 5 человек на сумму не более 950 000 рублей. Глиссер стоит 25 000 рублей, катер — 16 000 рублей. Ожидается, что желающих совершить прогулку будет не менее 200 человек. Сколько катеров и глиссеров должна приобрести фирма, чтобы получить наибольший доход, если билет на глиссер стоит 15 рублей, на катер — 10 рублей и фирма уже договорилась приобрести не менее 10 глиссеров?
11.	Завод выпускает обычные станки и станки с программным управлением, затрачивая на один обычный станок 200 кг стали и 200 кг цветного металла, а на 1 станок с программным управлением 700 кг стали и 100 кг цветного металла. Завод может израсходовать в месяц до 46 тонн стали и до 32 тонн цветного металла, и имеет обязательное задание выпускать в месяц не менее 80 станков. Определить оптимальный месячный план производства станков, если один обычный станок стоит 10 тыс. рублей, а станок с программным управлением 75 тыс. рублей.
12.	Для изготовления различных изделий А и В предприятие использует три вида сырья. На производство единицы изделия А требуется затратить сырья первого вида 6 кг, второго — 5 кг, третьего — 3 кг. На производство единицы изделия В — 3 кг, 10 кг и 12 кг соответственно. Производство обеспечено сырьем первого вида в количестве 910 кг, второго вида — 930 кг и третьего вида — 950 кг. Прибыль от реализации единицы готового изделия А составляет 30 рублей, а изделия В — 90 рублей. Составить оптимальный план производства изделий А и В.
13.	В регионе планируется строительство тепловых и гидроэлектростанций мощностью соостветственно 2 и 3 млн. кВт каждая. На строительство одной гидростанции требуется 1000 рабочих, 25 млн. кубометров бетона и 300 тыс. тонн железных конструкций. На строительство одной тепловой станции — 800 рабочих, 15 млн. кубометров бетона и 400 тыс. тонн железных конструкций. Регион располагает не более чем 8 тыс. рабочих, 175 млн. кубометров бетона и 4 млн. тонн железных конструкций. Составить план строительства электростанций, максимизирующий производство электроэнергии.
14.	Автозавод выпускает грузовики грузоподъемностью 3 тонны и 2 тонны. Общая грузоподъемность грузовиков, выпущенных заводом за неделю, должна быть не менее 600 т. На производство одного трехтонного грузовика затрачивается 350 человеко-часов рабочего времени и 9 тонн металла, а одного двухтонного — 500 человеко-часов и 14 тонн металла. Недельный запас ресурсов предприятия: 190 тыс. человеко-часов рабочего времени и 5 тыс. тонн металла. Найти оптимальный план выпуска автомобилей, максимизирующий доход завода, если трехтонный грузовик стоит 60 тыс. рублей, а двухтонный — 90 тыс. рублей.
15.	На складе надо разместить ящики трех типов: А, В, С. Причем типа А не менее 33 штук, типа В не менее 36 штук и типа С не менее 39 штук. Имеется возможность заказать стеллажи двух видов. На один стеллаж первого вида стоимостью 300 руб. помещается 11 ящиков типа А, 7 типа В и 4 типа С. На один стеллаж второго вида стоимостью 400 руб. помещается три ящика типа А, 5 типа В и 9 типа С. Сколько стеллажей каждого вида нужно заказать, чтобы их стоимость была наименьшей?
16.	Обувная мастерская располагает листами кожи двух типов, из которых выкраивают заготовки А и В. Из листа первого типа можно выкроить 3 заготовки А и 5 заготовок В, отходы составляют при этом 40 кв. см. Из листа кожи второго типа — 7 заготовок А и 2 заготовки В, отходы — 50 кв. см. Сколько листов каждого типа надо раскроить, чтобы отходы были минимальными, если необходимо изготовить не менее 210 заготовок А и не менее 250 заготовок В .
17.	На сортировочной станции находится 136 плацкартных вагонов по 48 мест каждый, 112 купейных вагонов по 28 мест и 80 мягких вагонов по 24 места. Можно составить 2 типа поездов: 1 тип состоит из 10 плацкартных,4 купейных и 2 мягких вагонов, 2 тип — из 2 плацкартных, 8 купейных и 6 мягких вагонов. Сколько поездов того и другого типа нужно составить, чтобы общее число пассажиров было максимальным?
18.	В инструментальном цехе изготавливается два типа приспособлений. При изготовлении приспособления первого типа затрачивается 3 часа работы токаря, 3 часа работы слесаря и 2 часа работы сварщика, а при изготовлении приспособления второго типа — 2 часа, 3 часа и 5 часов соответственно. Месячный фонд рабочего времени токарей составляет 270 часов, слесарей — 300 часов и сварщиков — 480 часов. Стоимость приспособления первого типа 550 рублей, второго типа — 500 рублей. Составить план выпуска приспособлений, максимизирующий общую стоимость продукции за месяц.
19.	На ферме разводят два вида животных А и В. В недельный рацион одного животного вида А входят 17 кг белков, 11 кг углеводов и 5 кг жиров, а для одного животного вида В эти нормы соответственно равны 13 кг, 15 кг и 7 кг. Доход от реализации одного животного вида А составляет 300 рублей, а от реализации одного животного вида В — 350 рублей. Найти план разведения животных, максимизирующий доход фермы, если ферма не может расходовать в неделю более 185 кг белков, 150 кг углеводов и 70 кг жиров.
20.	Завод выпускает два вида двигателей. На изготовление одного двигателя первого вида расходуется 2 тонны чугуна и 1 тонна стали, а на изготовление одного двигателя второго вида — 1 тонна чугуна и 3 тонны стали. Завод располагает на месяц 120 тоннами чугуна и 140 тоннами стали и должен изготовить не менее 20 двигателей обоих видов. Составить месячный план производства двигателей, максимизирующий прибыль завода, если от сбыта одного двигателя первого вида прибыль составляет 4 тыс. рублей, а второго — 6 тыс. рублей.
21.	Мастерская ремонтирует двигатели двух типов: мощностью 300 л.с. и 200 л.с. За неделю мастерская может отремонтировать не более 150 двигателей. За ремонт двигателя I типа получают 800 рублей, II типа — 500 рублей. Требуется отремонтировать не менее 50 двинателей второго типа. Составить недельный план ремонта двигателей, при котором мастерская получит не менее 50 000 рублей и суммарная мощность отремонтированных двигателей будет наибольшей.
22.	Швейная фабрика выпускает костюмы двух видов. На один костюм 1 вида идет 1,2 кг шерсти и 0,2 кг синтетики, а на костюм 2 вида — 0,8 кг шерсти и 0,4 кг синтетики. Суточные запасы шерсти и синтетики составляют 80 кг и 35 кг соответственно. Общее количество выпущенных за сутки изделий должно быть не менее 45 штук. Составить план выпуска изделий, максимизирующий прибыль фабрики, если костюм 1 вида стоит 450 рублей, а 2 вида — 300 рублей.
23.	Для изготовления изделий А и В используется три вида сырья. На изготовление одного изделия А требуется 18 кг сырья первого вида, 12 кг сырья второго вида и 10 кг сырья третьего вида. На изготовление одного изделия В требуется соответственно 8 кг, 14 кг и 16 кг сырья. На складе запасы сырья первого вида имеются в количестве 950 кг, второго — 860 кг, третьего — 810 кг. Рыночная цена одного изделия А равна 600 рублей, изделия В — 400 рублей. Составить план производства, максимизирующий доход от реализации изделий А и В.
24.	На станции находится 50 плацкартных вагонов по 48 мест каждый, 50 купейных вагонов по 28 мест и 25 мягких вагонов по 24 места. Можно составить 2 типа поездов: 1 тип состоит из 7 плацкартных, 5 купейных и 3 мягких вагонов, 2 тип — из 5 плацкартных, 8 купейных и 4 мягких вагонов. Сколько поездов обоих типов нужно составить, чтобы общее число пассажиров было максимальным?
25.	В цехе изготавливается два типа изделий. При изготовлении изделия первого типа затрачивается 6 часов работы токаря, 7 часов работы слесаря и 1 час работы сварщика, а при изготовлении изделия второго типа — 4 часа, 2 часа и 5 часов соответственно. Месячный фонд рабочего времени токарей составляет 350 часов, слесарей — 400 часов и сварщиков — 250 часов. Стоимость изделия первого типа 250 рублей, второго типа — 200 рублей. Составить месячный план выпуска изделий, максимизирующий общую стоимость продукции.
26.	Для организации перевозок фирма имеет возможность приобрести микроавтобусы на 12 человек и легковые автомобили вместимостью 4 человека на сумму не более 1 млн. рублей. Автомобиль стоит 40 тыс. рублей, а микроавтобус — 60 тыс. рублей. Предполагается, что услугами фирмы воспользуется не менее 100 человек. Легковых автомобилей должно бытьприобретено не менее 5 штук. Какое количество транспорта должна приобрести фирма с учетом получения наибольшего дохода от перевозок на автомобилях и микроавтобусах, если их тарифы составляют 40 рублей и 25 рублей соответственно?

ЛАБОРАТОРНАЯ РАБОТА № 2